하노이의 탑은 어떻게 하나요?
왼쪽 기둥에 크기 순서대로 쌓인 원판을 한 번에 하나씩 옮겨 오른쪽 기둥에 똑같이 다시 쌓으면 이기는 퍼즐입니다. 큰 원판을 작은 원판 위에 올려서는 안 됩니다.
1883년 프랑스 수학자 에두아르 뤼카가 만든 퍼즐로, 지금도 수학과 프로그래밍 수업에서 재귀를 배울 때 가장 먼저 나오는 예제입니다.
규칙은 무엇인가요?
- 한 번에 한 개: 기둥 맨 위에 있는 원판 하나만 옮길 수 있습니다.
- 작은 것이 위: 원판은 빈 기둥이나 자기보다 큰 원판 위에만 놓을 수 있습니다.
- 목표: 원판 전부를 3번(오른쪽) 기둥에 처음과 같은 모양으로 쌓으면 끝납니다.
- 별 평가: 최소 이동 수 그대로면 별 셋, 최소의 1.5배 안이면 별 둘, 그보다 많으면 별 하나입니다.
최소 이동 수는 몇 번인가요?
원판이 n개이면 최소 이동 수는 2n - 1번입니다. 원판 3개는 7번, 10개는 1,023번입니다.
이유는 가장 큰 원판을 생각하면 쉽습니다. 가장 큰 원판을 오른쪽으로 옮기려면 그 위의 작은 원판 n - 1개를 먼저 가운데 기둥으로 모두 치워야 합니다. 그다음 큰 원판을 한 번 옮기고, 치워 둔 n - 1개를 다시 그 위로 가져옵니다. 그래서 원판 n개에 드는 횟수는 (n - 1개를 옮기는 횟수) × 2 + 1입니다. 1개는 1번이니 2개는 3번, 3개는 7번, 4개는 15번으로, 원판이 하나 늘 때마다 두 배에 1을 더한 수가 되고 이것을 정리하면 2n - 1입니다. 큰 원판은 작은 원판들이 모두 비켜 있어야만 움직일 수 있으므로 이보다 적게 옮기는 방법은 없습니다.
| 원판 수 | 최소 이동 수 |
|---|---|
| 3개 | 7번 |
| 4개 | 15번 |
| 5개 | 31번 |
| 6개 | 63번 |
| 7개 | 127번 |
| 8개 | 255번 |
| 9개 | 511번 |
| 10개 | 1,023번 |
최소 이동 수로 푸는 요령은?
- 첫 수는 원판 수로 정하세요. 원판이 홀수 개면 가장 작은 원판을 목표 기둥(3번)으로, 짝수 개면 가운데 기둥(2번)으로 먼저 옮깁니다.
- 가장 작은 원판은 한 수 걸러 한 번씩 움직입니다. 그리고 늘 같은 방향으로 돌아갑니다.
- 작은 원판을 옮기지 않는 차례에는 할 수 있는 수가 딱 하나뿐입니다. 작은 원판이 없는 두 기둥 사이에서 놓을 수 있는 쪽으로 옮기면 됩니다.
- 막히면 가장 큰 원판을 떠올리세요. 큰 원판을 옮기려면 그 위의 원판을 모두 다른 한 기둥에 모아야 한다고 생각하면 길을 잃지 않습니다.
자동 풀이는 어떻게 움직이나요?
지금 놓인 모양에서 시작해 가장 적은 수로 끝까지 풀어 보여 줍니다. 속도는 1배부터 16배까지 바꿀 수 있고, 처음부터 누르면 정확히 2n - 1번 만에 끝납니다.
자동 풀이는 위에서 말한 방법 그대로입니다. 가장 큰 원판이 아직 목표 기둥에 없으면 작은 원판들을 남는 기둥으로 치우고, 큰 원판을 옮기고, 작은 원판들을 다시 가져옵니다. 작은 원판들을 옮기는 일도 같은 방법을 한 단계 작게 되풀이합니다.
전설에서는 원판 64개짜리 탑을 다 옮기면 세상이 끝난다고 합니다. 264 - 1번은 약 1,800경 번으로, 1초에 한 번씩 옮겨도 약 5,850억 년이 걸립니다. 자동 풀이를 쓴 판은 최고 기록에 남지 않으며, 원판 수별 최고 기록은 이 브라우저에 저장됩니다.