퍼즐1~10분
하노이의 탑
원반을 하나씩, 작은 것 위에 큰 것은 금지
게임 방법
- 1위쪽 숫자 버튼으로 원반 개수(3~8개)를 고르세요. 처음이라면 3개나 4개부터 시작해 보세요.
- 2원반을 옮길 기둥을 누르면 맨 위 원반이 들려요. 놓을 기둥을 누르면 그 기둥 맨 위에 놓여요. 같은 기둥을 다시 누르면 내려놓아요.
- 3작은 원반 위에 큰 원반은 올릴 수 없어요. 빈 기둥이나 더 큰 원반 위에만 놓을 수 있어요.
- 4모든 원반을 오른쪽 기둥에 옮기면 완성이에요. 최소 횟수면 별 3개, 최소의 1.5배 이내면 2개, 그 이상이면 1개예요.
- 5막히면 힌트로 다음에 옮길 원반을 볼 수 있어요. 지금 상태에서 가장 빠른 길을 알려 주고, 힌트를 쓴 판은 별이 최대 2개예요.
조작
- 클릭 / 탭
- 기둥 고르기 (들기, 놓기)
- 숫자 1~3
- 왼쪽·가운데·오른쪽 기둥 바로 고르기
- ← → 방향키 + Enter·스페이스바
- 판의 기둥을 한 번 누르거나 Tab으로 들어간 뒤 기둥을 옮기고 고르기
- 무르기 버튼 / Z·Backspace
- 한 번 무르기
- 힌트 버튼 / H
- 다음에 옮길 원반 표시
공략
- 가장 작은 원반은 두 번에 한 번꼴로 움직여요. 최소 횟수로 풀면 가장 작은 원반이 홀수 번째 이동마다 움직이고, 짝수 번째 이동은 작은 원반이 아닌 원반 가운데 옮길 수 있는 단 하나예요.
- 원반 개수가 홀수면 가장 작은 원반을 처음에 오른쪽 기둥으로, 짝수면 가운데 기둥으로 옮기세요. 그다음부터 가장 작은 원반은 늘 같은 방향으로 한 칸씩 돌면 돼요.
- 큰 원반을 옮길 때를 기준으로 생각하세요. 맨 아래 원반을 오른쪽으로 옮기려면 그 위의 원반들이 전부 가운데 기둥에 있어야 해요.
- 원반 수를 하나 늘리면 최소 횟수는 '전 단계의 두 배 더하기 1'이 돼요. 4개를 15번에 풀 수 있게 되면 5개 31번도 같은 방법으로 풀려요.
하노이의 탑은 어떤 게임인가요
기둥 세 개 가운데 왼쪽 기둥에 크기가 다른 원반이 큰 것부터 쌓여 있어요. 원반을 하나씩 다른 기둥으로 옮겨서 같은 모양 그대로 오른쪽 기둥에 다시 쌓으면 성공이에요. 규칙은 두 가지예요. 한 번에 맨 위 원반 하나만 옮길 수 있고, 큰 원반을 작은 원반 위에 올릴 수 없어요.
1883년 프랑스 수학자 에두아르 뤼카가 소개한 퍼즐이에요. 원반이 n개일 때 가장 적게 옮기는 횟수는 2를 n번 곱하고 1을 뺀 수라서, 3개면 7번, 4개면 15번, 8개면 255번이에요. 원반 하나가 늘 때마다 횟수가 두 배 넘게 늘어나는 걸 직접 손으로 느껴 볼 수 있어요.
답을 외우지 않아도 규칙 하나만 알면 어떤 크기든 풀 수 있어요. 맨 아래 큰 원반을 옮기려면 그 위의 원반들을 먼저 다른 기둥에 통째로 옮겨 두어야 하고, 그 작은 탑을 옮기는 방법도 똑같아요. 이렇게 큰 문제를 같은 모양의 작은 문제로 나누는 생각을 재귀라고 하는데, 하노이의 탑은 그 대표적인 예로 자주 쓰여요.
자주 묻는 질문
최소 횟수는 어떻게 정해져요?
원반이 n개면 2ⁿ−1번이에요. 3개 7번, 4개 15번, 5개 31번, 6개 63번, 7개 127번, 8개 255번이에요. 이보다 적게 옮기는 방법은 없다는 것이 증명되어 있어요.
중간에 이상하게 옮겨도 힌트가 돼요?
네. 힌트는 처음부터의 정답 순서를 보여 주는 게 아니라, 지금 원반이 놓인 모양에서 오른쪽 기둥으로 가는 가장 빠른 다음 한 수를 계산해서 알려 줘요.
기록은 어떻게 남아요?
원반 개수마다 가장 적게 옮긴 횟수가 따로 저장돼요. 무르기로 되돌린 이동은 횟수에서 빠져요. 기록은 이 브라우저에만 남아요.
64개 원반 전설은 뭐예요?
뤼카가 퍼즐을 소개하며 붙인 이야기로, 사원의 승려들이 원반 64개를 옮기고 있고 다 옮기면 세상이 끝난다는 전설이에요. 1초에 한 번씩 옮겨도 2⁶⁴−1초, 약 5,800억 년이 걸려요.