캐스트 큐비 (Cast Cuby) [분석]

 캐스트 큐비는 길찾기퍼즐(Route-Finding Puzzle)에 속하기 때문에 이전의 캐스트 플레이트(Cast Plate)처럼 지도를 그려서 분석하고자 합니다. 즉, State Diagram을 그려보도록 하겠습니다.

 

 

1.관찰

 

 

 캐스트 큐비는 은색 상자와 금색 반달모양 조각으로 이루어져있습니다. 목적은 이 금색 조각을 은색 상자로부터 탈출시키는 것입니다. 상자에는 ㄷ자 모양의 구멍이 각 면에 평균 6개씩 있습니다. 이 구멍들이 State Diagram의 각 점을 차지하게됩니다. 점끼리 서로 이어진다는 것은 금색 조각이 움직일 수 있는가로 표시하겠습니다.

 ㄷ자 구멍의 수를 새면 모두 37개가 되는데, 이 많은 구멍들중에서 딱 한군데만에 금색 조각을 빠져나게합니다. 그 이유는 금색 조각에 입술모양의 돌기가 붙어있어서 다른 구멍들은 통과를 못하는데 오직 한 구멍만이 조금 크기가 더 커서 돌기를 통과시키기때문입니다.

 

 

 

 2. 움직임

 

 

 

 상식에 맞게 은색 상자를 고정하고, 금식 반달조각을 움직이도록 하겠습니다.

일반성을 잃지않고 한쪽 ㄷ자 구멍에 금색 조각이 위치한다고 가정하면 이 구멍에서 3가지 움직임이 가능합니다. 1번은 직선운동이고, 2,3번은 모두 회전운동입니다. 반달모양의 곡면이 2개 있으므로 회전운동도 2번 가능한 것입니다. 특기할것은, 3번처럼 움직일 때 돌기에 살짝 걸릴 수도 있는데, 반드시 돌 수 있으니 다시 시도하면 좋겠습니다.

 

 

 

 3. 표기법

 

 

 은색 상자에는 눈이 새겨져있습니다. 이걸 이용하면 상자를 한 방향으로 규정하기 쉽겠죠? 눈이 새겨진 면을 위로 올리고 몸쪽으로 둡니다. 이제 위 아래 면을 U와 D로, 좌우면을 R과 L로, 앞뒤면을 F와 B로 표기합니다. 예상하셨다싶이 각 알파벳은 Up & Down, Left & Right, Back & Front의 머릿글자입니다. (이 표기법은 루빅스큐브에 대한 싱마스터(Singmaster)표기법을 참고한것입니다.)

 

 

 

 어떤 ㄷ자 구멍이 R면에 있다면 그 구멍은 R로 시작하는 표기를 받게 됩니다. 이제 더 자세하게 들어가겠습니다. R면에 있는 구멍이 위 방향으로 있으면 RU를, 앞으로 있으면 RF를, 그렇게 RD, RB를 표기합니다. 한 방향에는 2개의 구멍이 있을 수 있는데, 이를 숫자 1와 2로 구분합니다. 시계방향으로 1시 방향부터 1,2,1,2,... 이렇게 배치합니다. 1과 2의 의미는 State Diagram이 그려지면 자세히 설명하겠습니다.

 

 

 4. State Diagram

 먼저 시작점과 도착점을 파악합니다. 시작점은 RU1입니다. FU2의 구멍은 막혀있기때문입니다. 도착점은 어디인가? 도착점은 다른 구멍들과 다른게 눈에 띕니다. RU1 바로 옆에 있는 RU2가 바로 그 도착점입니다. RU2의 구멍이 조금 크기때문에 금색조각의 돌기가 통과할 수 있을 것입니다.

 

 각 구멍은 2.움직임 항목에서 보았듯이 모두 3개의 움직일 가능성을 가지고 있습니다. 즉 그래프에서 각 점이 3개의 edge를 가질 수 있다는 뜻인데, 이렇게 되면 엄청나게 복잡한 State Diagram이 나옵니다. 하지만 정말 다행스럽게도, 정~말~ 다행스럽게도 3개의 edge를 가지는 점은 캐스트 큐비에 없습니다. 그래도 막상 그리려면 일단 마음먹고 시작해야 됩니다. 점이 37개나 되니까요.

 

 그렇게 37개의 구멍에 대한 노가다작업을 시작하면...

 

 다음과 같은 다소 복잡한 State Diagram을 얻게됩니다.

 

 잘 보면, 이 그래프에는 루프(loop) 3개가 절묘한 길이로 섞여있습니다. 이 때문에 뭣모르고 설렁설렁 움직여보면 계속 같을 자리를 맴돌며 수렁의 길로 쉽게 빠지는 것입니다.

 

 State Diagram을 쉽게 읽는 법은 앞머리의 알파벳만 읽는 것입니다. 가령 RU1-UR2-FR1-...로 이어지는 길을 간다면, R-U-F-...로 보고 오른족(right) 면-윗(up) 면-앞(front) 면-... 순으로 금색조각을 움직이면됩니다.

 

  이제 숫자 1과 2의 의미가 보입니다. 금색조각의 입술모양 돌기를 봅시다. 입술의 왼족이 찌르는 구멍은 1, 입술의 오른쪽이 찌르는 구멍은 2가 됩니다. 조각은 입술의 왼쪽, 오른쪽을 번갈아 움직이기때문에 1,2,1,2 순으로 움직이는 것입니다. (어떤 그래프가 방금과같이 2가지로 구분될 때 bipartite라고 합니다. 참고로 어떤 그래프가 bipartite하다는 사실은 그 그래프가 2-colorable하다는 사실과 동치입니다. Bipartite의 정확한 정의는 링크 참조 : http://mathworld.wolfram.com/BipartiteGraph.html)

 

 State Diagram을 통해 캐스트 큐비의 최소길이해법은 14번 움직인다는 것을 쉽게 알 수 있습니다. 길은 RU1-UR2-FR2-... 로 시작하는 길과 RU1-LU2-FU1-...로 시작하는 길로 총 2개가 있습니다. 두 길 모두 RF1에서 만나 출구인 RU2까지 같은 길을 걷게됩니다.

 

 

 

 5. 마지막 즐거움.

 퍼즐의 두 조각을 분리시켰다면 이제 다시 밀어넣아야겠죠? 그런데 혹시나 빼내는데에 집중한 나머지 출발지점을 잊어버리진 않으셨나요? 캐스트 큐비는 매우 깜찍한 방법으로 이 출발지점을 표시해놓았습니다. 바로 얼굴을 완성시키는 것입니다. 금색 조각에 입술이 있고, 은색 상자에 눈이 있으므로 둘이 정확하게 위치하면 익살맞은 얼굴이 나타나게 됩니다. (정확히는 RU1과 FU2 사이입니다.)