하노이의 탑 게임 방법

하노이의 탑은 기둥 세 개와 크기가 모두 다른 원반 더미로 하는 퍼즐입니다. 프랑스의 수학자 에두아르 뤼카가 1883년에 발표했습니다. 익히는 데 1분쯤 걸리며, 이 페이지가 그 1분입니다.

목표

처음에는 모든 원반이 왼쪽 기둥 A에 가장 큰 원반이 아래, 가장 작은 원반이 위로 쌓여 있습니다. 목표는 똑같은 더미를 오른쪽 기둥 C에 다시 쌓는 것입니다.

가운데 기둥 B는 장식이 아니라 작업 공간입니다. 원반이 두 개 이상인 게임에서는 도중에 반드시 여기에 원반을 세워 두게 됩니다.

시작. 모든 원반이 A 기둥에 있고 가장 큰 원반이 맨 아래에 있습니다. 기둥 맨 위에 있는 것은 원반 1뿐이므로, 지금 이 순간 움직일 수 있는 원반은 원반 1 하나입니다.

목표. 같은 더미를 같은 순서로 C 기둥에. B 기둥은 다시 비어 있습니다. 처음부터 작업 공간이었을 뿐이니까요.

A, B, C

왼쪽부터 오른쪽으로 놓인 기둥 세 개. 판에는 기둥 아래에 글자가 적혀 있고, 이 사이트의 모든 이동 목록이 이 글자를 씁니다.

원반 1

가장 작은 원반. 번호는 크기와 함께 커지므로, 원반 5개짜리 판에서는 원반 5가 맨 아래의 가장 큰 원반입니다.

A → C

한 번의 이동: A 기둥 맨 위의 원반을 집어 C 기둥에 놓는 것. 아래 표처럼 원반 번호를 함께 적는 경우가 많지만, 글자 두 개만으로도 충분합니다. 한 기둥에서 움직일 수 있는 원반은 언제나 하나뿐이기 때문입니다.

세 가지 규칙

1. 한 번에 원반 하나만 옮깁니다.
2. 기둥의 맨 위 원반만 옮길 수 있습니다. 다른 원반 아래에 깔린 원반은 위가 치워질 때까지 움직이지 않습니다.
3. 큰 원반을 작은 원반 위에 놓을 수 없습니다. 원반은 빈 기둥이나 자기보다 큰 원반 위에만 놓을 수 있습니다.

• 놓을 수 있음원반 2를 원반 3 위에. 들고 있는 원반이 내려앉을 원반보다 작으므로 더미의 순서가 유지됩니다. 완전히 빈 기둥에 놓는 것도 언제나 됩니다.

• 놓을 수 없음원반 3을 원반 1 위에. 들고 있는 원반이 내려앉을 원반보다 큽니다. 판은 이 이동을 거부하고 이유를 알려 준 뒤 원반을 원래 자리에 돌려놓습니다. 잃는 것은 없습니다.

규칙은 이것이 전부입니다. 같은 원반을 두 번 연달아 옮기면 안 된다는 규칙도, 시간제한도, 이동 횟수 제한도 없습니다. 질 수가 없는 게임입니다. 신경 쓸 것은 내 이동 횟수뿐입니다.

원반 옮기는 법

한 번의 이동은 두 동작으로 이루어집니다. 원반을 들고, 다른 기둥에 놓는 것이죠. 판에서는 세 가지 방법으로 할 수 있습니다.

• 누르기·클릭. 기둥을 누르면 맨 위 원반이 들립니다. 원반이 떠올라 손에 들고 있음을 보여 주고, 놓을 수 있는 기둥이 밝아집니다. 목적지를 누르면 놓이고, 같은 기둥을 다시 누르면 되돌려 놓습니다.
• 끌기. 마우스나 트랙패드로 기둥을 눌러 원반을 다른 기둥으로 끌어갑니다. 포인터 아래의 기둥이 원반을 받을 수 있는지 보여 줍니다. 휴대폰에서는 누르기를 쓰세요. 손가락이 끌고 있는 원반을 가려 버리기 때문입니다.
• 키보드. Tab 키로 판으로 이동한 뒤 1, 2, 3으로 A, B, C 기둥에서 들고 놓습니다. 화살표 키도 됩니다. ←와 →로 기둥을 고르고, ↑로 들고 ↓로 놓습니다. Esc는 원반을 되돌려 놓습니다.

목적지에 더 작은 원반이 있으면 이동이 거부됩니다. 기둥이 깜박이고, 원반은 출발한 기둥으로 돌아가며, 짧은 메시지가 이유를 알려 줍니다. 거부된 이동은 세지 않습니다.

해 보기: 원반 3개

이 판은 진짜 판과 똑같은 규칙으로 움직입니다. 세 번째 규칙을 어겨 보세요. 큰 원반을 작은 원반 위에 올려 보고 어떻게 되는지 확인한 다음, 게임을 끝까지 풀어 보세요.

3

2

1

A

B

C

기둥을 누르면 맨 위 원반이 들립니다.

이것이 게임의 전부입니다.원반을 더 늘려 하노이의 탑 하기 →

예시: 원반 3개 게임

원반 3개는 일곱 번이면 됩니다. 재생을 누르거나 한 수씩 넘겨 보세요. 표가 판을 따라 움직이고, 행을 클릭하면 그 수로 바로 넘어갑니다. 원반 1이 가장 작고 원반 3이 가장 큽니다.

3

2

1

A

B

C

A 기둥에 원반 3개. 남은 수는 7번입니다.7단계 중 0단계

원반 3개 게임의 일곱 수

수	원반	출발	도착
1	1	A	C
2	2	A	B
3	1	C	B
4	3	A	C
5	1	B	A
6	2	B	C
7	1	A	C

이기는 조건

모든 원반이 원래 순서대로 C 기둥에 놓이는 순간 이깁니다. 판은 두는 동안 이동 횟수를 세고, 원반 개수마다 가장 좋은 기록을 브라우저에 저장합니다.

• 힌트는 다음 수를 가리키기만 합니다. 두는 것은 나이므로, 힌트를 쓴 게임도 최고 기록이 될 수 있습니다.
• 한 수와 자동으로 풀기는 나 대신 수를 둡니다. 게임은 그래도 끝나지만 최고 기록을 덮어쓰지는 않습니다.

최소 이동 횟수

원반 n개의 완벽한 게임은 2ⁿ − 1번이며, 이보다 짧은 풀이는 없습니다. 원반이 하나 늘 때마다 게임 길이는 두 배에 한 번을 더한 만큼이 됩니다.

판은 원반 15개, 곧 32,767번까지 할 수 있습니다. 전설 속 64개까지 그 밖의 개수는 최소 이동 횟수 계산기에서 확인하세요.

다음으로 볼 것

• 하노이의 탑 하기 — 원반 3개로 시작해 한 번 이기면 하나를 더하세요.
• 공략법 — 모든 크기를 푸는 하나의 생각과, 다음 수를 아는 요령.
• 해답기 — 게임 도중 막혔나요? 원반 위치를 알려 주면 남은 모든 수를 보여 줍니다.
• 최소 이동 횟수 계산기 — 어떤 원반 개수든 이동 횟수와 걸리는 시간.
• 가르치기 — 시간 배분이 담긴 45분 수업안, 인쇄용 활동지, 판지로 도구를 만드는 방법.

자주 묻는 질문

판에서 이동이 안 되는 이유는 무엇인가요?

거부되는 이동은 두 가지뿐입니다. 빈 기둥을 먼저 누르면 들 원반이 없어서 거부됩니다. 원반을 더 작은 원반 위에 놓으려 해도 거부되며, 판은 원반을 원래 자리로 돌려놓습니다. 두 경우 모두 판이 이유를 알려 주고, 어느 쪽도 이동으로 세지 않습니다.

가운데 기둥을 꼭 써야 하나요?

네, 원반이 두 개 이상인 모든 게임에서 그렇습니다. 가장 큰 원반이 C 기둥에 가려면 더 작은 원반이 모두 그 위에서 치워지고, 그중 어느 것도 C에 있지 않아야 합니다. 그때 작은 원반들이 갈 곳은 B 기둥뿐입니다. 가운데 기둥은 돌아가는 길이 아니라 게임의 대부분이 벌어지는 곳입니다.

원반 몇 개로 시작하는 게 좋나요?

세 개입니다. 일곱 번이면 끝나서 전체 패턴을 한눈에 볼 수 있습니다. 첫 게임은 원반 개수를 3으로 두고, 이길 때마다 하나씩 늘려 보세요. 원반이 하나 늘 때마다 게임 길이가 대략 두 배가 됩니다.

원반을 방금 가져온 기둥에 바로 돌려놓아도 되나요?

됩니다. 규칙에서 금지하지 않고 판에서도 할 수 있습니다. 다만 두 번을 쓰고도 판이 그대로이므로, 효율적으로 풀려는 게임에서는 늘 낭비되는 한 쌍의 이동입니다.

최소 이동 횟수보다 많이 두면 지는 건가요?

아닙니다. 몇 번이 걸리든 모든 원반이 C 기둥에 모이는 순간 이깁니다. 최소 횟수(2ⁿ − 1, 원반 3개면 7번)는 노려 볼 목표일 뿐 이기는 조건이 아닙니다.