하노이의 탑 최소 이동 횟수 2ⁿ−1, 손으로 푸는 순서까지

하노이의 탑은 규칙이 두 줄입니다. 한 번에 맨 위 원반 하나만 옮기고, 큰 원반을 작은 원반 위에 올리지 않습니다. 그런데 원반이 하나 늘 때마다 필요한 이동 횟수는 두 배가 넘게 늘어납니다. 막히는 이유는 대부분 머리가 아니라 순서입니다. 어느 원반을 먼저 어디로 옮길지만 알면 8개짜리도 손이 알아서 풉니다.

아래 값은 게임의 규칙과 풀이 순서를 그대로 돌려서 얻은 것입니다. 3개부터 8개까지 모든 판에서 최소 이동으로 끝까지 풀어 세었고, 화면에 보이는 이동 수·최소 횟수와 같습니다.

한눈에 보기

게임이 제공하는 원반 수는 3개부터 8개까지이고, 첫 화면은 4개입니다. 별 3개는 최소 이동 이하, 2개는 최소의 1.5배를 올림한 횟수 이내, 그보다 많으면 1개입니다. 힌트를 한 번이라도 쓴 판은 최소로 풀어도 별이 2개까지만 나옵니다. 최고 기록은 원반 수마다 따로 저장되고, 무르기로 되돌린 이동은 횟수에서 빠집니다.

왜 2ⁿ−1번인가

가장 큰 원반을 옮기는 순간을 생각하면 됩니다. 맨 아래 큰 원반은 위에 아무것도 없고 도착 기둥이 비어 있을 때만 움직일 수 있습니다. 즉 그 위의 원반 n−1개가 전부 가운데 기둥에 쌓여 있어야 합니다. 그래서 순서는 세 덩어리입니다.

1. 위의 n−1개를 가운데 기둥으로 옮긴다 (최소 횟수를 T(n−1)이라고 하면 T(n−1)번)
2. 가장 큰 원반을 오른쪽으로 옮긴다 (1번)
3. 가운데에 있던 n−1개를 오른쪽으로 옮긴다 (T(n−1)번)

그래서 T(n) = 2×T(n−1) + 1이고, 원반 1개는 1번이니 T(2)=3, T(3)=7, T(4)=15로 이어집니다. 이 식을 풀면 2ⁿ−1입니다. 가장 큰 원반이 움직이는 순간이 정확히 한가운데(2ⁿ⁻¹번째)에 오는 것도 이 구조 때문입니다. 위 표의 4번째, 8번째, 16번째가 그 자리입니다.

더 적게 옮기는 방법은 없습니다. 가장 큰 원반이 한 번은 움직여야 하고, 그 순간에는 나머지가 전부 가운데에 있어야 하기 때문에 앞뒤로 T(n−1)번씩이 반드시 필요합니다.

원반별로 몇 번 움직이나

최소 순서에서 원반 k는 정확히 2ⁿ⁻ᵏ번 움직입니다. 엔진으로 8개짜리를 처음부터 끝까지 돌려 세면 작은 것부터 128, 64, 32, 16, 8, 4, 2, 1번이고, 합은 255번입니다. 4개짜리는 8, 4, 2, 1번으로 합이 15번입니다.

이 비율이 손 순서의 열쇠입니다. 가장 작은 원반이 전체 이동의 절반을 차지합니다. 최소 순서에서는 홀수 번째 이동(1, 3, 5…번째)이 전부 가장 작은 원반이고, 짝수 번째 이동은 그 외의 원반 중 옮길 수 있는 단 하나입니다. 3개부터 8개까지 모두 이 규칙이 그대로 맞습니다.

손 순서: 두 줄이면 끝난다

기둥을 왼쪽(A), 가운데(B), 오른쪽(C)이라고 하겠습니다.

1. 홀수 번째 이동: 가장 작은 원반을 같은 방향으로 한 칸씩 돌립니다. 원반 수가 홀수(3, 5, 7개)면 A→C→B→A 순서, 짝수(4, 6, 8개)면 A→B→C→A 순서입니다.
2. 짝수 번째 이동: 가장 작은 원반을 뺀 나머지 중에서 규칙상 옮길 수 있는 원반은 딱 하나뿐입니다. 그것을 옮깁니다. 고민할 필요가 없습니다.

원반 3개의 전체 순서는 이렇게 7번입니다. 쓰는 방법은 "출발 기둥 도착 기둥"입니다.

가장 작은 원반이 1, 3, 5, 7번에 움직이고 가운데 번호는 모두 다른 원반입니다. 4개짜리 15번은 AB AC BC AB CA CB AB AC BC BA CA BC AB AC BC이고, 원반이 짝수라 처음에 가운데로 갑니다. 처음 방향을 틀리면 어떻게 되는지는 아래에서 봅니다.

실수 한 번의 비용

처음에 가장 작은 원반을 반대 기둥으로 보내면 어떻게 될까요. 원반 3개는 오른쪽이 맞는데 가운데로 보내고, 4개는 가운데가 맞는데 오른쪽으로 보낸 경우를 게임의 힌트 계산(지금 모양에서 가장 빠른 다음 한 수)으로 끝까지 따라가 세어 보면 이렇게 나옵니다.

처음 한 수를 반대로 보낸 것은 1번만 손해입니다. 위의 별 기준으로는 3개는 별 2개(8~11번), 4개와 5개도 별 2개입니다. 다만 이 값은 그 뒤로 힌트의 최단 경로를 따라 끝냈을 때입니다. 별 3개를 노린다면 틀린 수를 알아챈 즉시 무르기로 되돌리는 쪽이 낫습니다. 무르기로 되돌린 이동은 횟수에서 빠지기 때문입니다.

큰 판으로 가는 요령

• 원반 수를 하나 늘리면 순서 전체를 두 번 쓴다. 5개를 풀 수 있으면 6개는 "5개를 가운데로 → 큰 것을 오른쪽으로 → 5개를 오른쪽으로"입니다. 5개가 31번이니 6개는 31+1+31=63번입니다.
• 목표 기둥은 원반마다 다르다. 큰 원반 기준으로는 오른쪽이지만, 한 단계 위의 덩어리를 옮길 때는 가운데가 목표가 됩니다. 8개짜리에서 헷갈리면 "지금 못 움직이는 가장 큰 원반이 어디로 가야 하나"만 먼저 생각하고 그 위를 비우는 쪽으로 가면 됩니다. 힌트 기능이 계산하는 것도 이 규칙입니다.
• 8개짜리 255번은 마라톤이다. 한 수에 1초씩이면 4분 15초입니다. 흐름을 놓쳤다면 가장 작은 원반이 방금 어디에 있었는지 보세요. 그 원반만 맞으면 나머지는 하나로 정해집니다.

64개 전설은 얼마나 걸리나

원반 64개짜리 이야기에서는 승려들이 원반 64개를 옮기고 다 옮기면 세상이 끝난다고 합니다. 최소 이동은 2⁶⁴−1 = 18,446,744,073,709,551,615번이고, 한 번에 1초씩이면 약 5,845억 년입니다(1년을 365.25일로 계산). 게임에서 원반 수가 3개씩 늘 때마다 횟수가 8배로 느는 이유가 이 지수 증가입니다.

정리

• 최소 이동은 2ⁿ−1번이고, 3개 7번부터 8개 255번까지가 게임에서 고를 수 있는 범위입니다.
• 순서는 두 줄입니다. 홀수 번째에는 가장 작은 원반을 일정한 방향으로 한 칸, 짝수 번째에는 나머지 중 움직일 수 있는 하나.
• 처음 방향만 원반 수의 홀짝에 맞게 고르면 별 3개는 어렵지 않습니다. 틀리면 무르기가 힌트보다 먼저입니다.

이 글의 숫자는 어디서 왔나

최소 이동 횟수와 별 기준, 힌트의 동작은 하노이의 탑 게임 페이지의 설명과 화면(이동 수, 원반 수별 최고 기록)에서 확인할 수 있습니다. 원반별 이동 횟수와 순서, 실수 비용은 게임이 쓰는 규칙과 풀이 순서를 3~8개 전부에 대해 실행해 센 값입니다.

비슷하게 규칙 하나로 푸는 퍼즐로는 페그 솔리테어, 불 끄기, 소코반이 있습니다.