하노이의 탑 푸는 법에서 외울 것은 두 가지 순서뿐이에요. 이것을 번갈아 되풀이하면 원판이 몇 개든 가장 적은 수로 탑을 옮길 수 있어요. 이 기사에서는 왼쪽 기둥의 탑을 오른쪽 기둥으로 옮기는 경우로 설명해요(규칙은 하노이의 탑이란?을 보세요). 원판은 작은 것부터 차례로 1, 2, 3…번이라고 불러요.

푸는 법은 두 가지 순서의 되풀이

  1. 홀수 번째 수(1번째·3번째·5번째…): 가장 작은 원판(1)을 정해진 방향으로 옆 기둥으로 하나 움직인다.
  2. 짝수 번째 수(2번째·4번째·6번째…): 1이 아닌 원판 중에서 움직일 수 있는 수를 둔다. 움직일 수 있는 수는 언제나 하나뿐이에요.

이게 전부예요. 1은 한 수 걸러 움직이고, 그 사이에 1이 아닌 원판이 한 번씩 움직여요.

작은 원판을 돌리는 방향 정하기

1을 움직이는 방향은 원판 개수로 정해져요. 기둥 3개를 고리처럼 이어져 있다고 생각하고, 끝까지 오면 반대쪽 끝으로 돌아요. 왼쪽 탑을 오른쪽으로 옮길 때는 다음 순서예요.

원판 개수1을 움직이는 순서
홀수 개(3·5·7…)왼쪽→오른쪽→가운데→왼쪽…
짝수 개(4·6·8…)왼쪽→가운데→오른쪽→왼쪽…

외우는 법은 “홀수 개라면 첫 수에서 1을 옮기려는 기둥에 곧바로 놓는다”예요. 짝수 개라면 첫 수는 옮기려는 기둥이 아닌 쪽(가운데)에 놓아요. 방향을 정했으면 끝까지 바꾸지 않아요.

가운데 기둥으로 옮기고 싶을 때는 표의 “오른쪽”과 “가운데”를 바꿔서 생각해요.

원판 3개로 확인하기

3개(홀수)이니 1은 “왼쪽 → 오른쪽 → 가운데 → 왼쪽” 순서로 돌아요. 금색 원판이 그 수에서 움직인 원판이에요.

  1. 321 처음
  2. 321 1번째 수 1번을 오른쪽으로
  3. 321 2번째 수 2번을 가운데로
  4. 321 3번째 수 1번을 가운데로
  5. 213 4번째 수 3번을 오른쪽으로
  6. 123 5번째 수 1번을 왼쪽으로
  7. 132 6번째 수 2번을 오른쪽으로
  8. 321 7번째 수 1번을 오른쪽으로

1번째·3번째·5번째·7번째 수는 1이 돌고 있을 뿐이고, 2번째·4번째·6번째 수는 “1이 아닌 것 중 움직일 수 있는 단 하나의 수”가 되는 것을 알 수 있어요.

짝수 번째 수가 하나로 정해지는 이유

짝수 번째 수에서는 1이 놓여 있지 않은 두 기둥의 맨 위 원판끼리 비교해요. 작은 쪽을 큰 쪽 위(또는 빈 기둥)로 움직일 수밖에 없어요.

  • 1 위에는 어떤 원판도 놓을 수 없어요(1보다 작은 원판이 없기 때문).
  • 남은 두 기둥에서는 큰 원판을 작은 원판 위에 놓을 수 없어요.

그래서 움직일 수 있는 수는 언제나 하나뿐이에요. 헷갈리는 것은 홀수 번째의 1의 방향뿐이고, 그것도 처음에 정해 버리면 나머지는 생각하지 않아도 손이 나아가요.

“위를 치우고, 큰 것을 옮긴다”는 생각

순서를 외우는 것과는 별도로, 왜 이렇게 풀리는지 생각하는 방법도 있어요. 원판 n개의 탑을 왼쪽에서 오른쪽으로 옮기려면,

  1. 위의 n−1개를 가운데로 치운다.
  2. 가장 큰 원판을 오른쪽으로 옮긴다.
  3. 가운데의 n−1개를 오른쪽으로 옮긴다.

의 세 가지로 나누면 된다는 생각이에요. 1과 3은 “1개 적은 탑을 옮기는” 문제이니 같은 생각을 한 번 더 쓸 수 있어요. 원판 4개라면 “3개를 치운다 → 4를 옮긴다 → 3개를 되돌린다”, 3개를 치우려면 “2개를 치운다 → 3을 옮긴다 → 2개를 되돌린다”… 이렇게 작은 문제로 나눠 갈 수 있어요. 이 생각에서 수가 2ⁿ−1번이 되는 것도 알 수 있어요(최소 수 공식).

도중에 헷갈렸을 때 다시 세우는 법

순서를 잊어서 흩어진 배치가 되어 버려도 괜찮아요. 다음 생각으로 어디서든 다시 세울 수 있어요.

  1. 아직 오른쪽 기둥에 올바르게 쌓지 못한 원판 중 가장 큰 것을 찾아요. 이것이 다음에 옮길 원판이에요.
  2. 그 원판을 오른쪽으로 옮기려면 그보다 작은 원판을 모두 지금 있는 기둥도 오른쪽 기둥도 아닌 남은 한 기둥에 모아 둬야 해요.
  3. 작은 원판을 모으는 것도 같은 생각의 되풀이예요. 모을 곳을 “목표 기둥”이라고 생각하고 처음부터 다시 해요.

큰 원판부터 차례로 목적지를 정해 가는 것이 요령이에요. 앱의 “문제” 모드(흩어진 원판을 본보기 모양으로 맞추는 놀이 방식)도 이 생각으로 풀 수 있어요.

공략 요령

  • 수를 세요: 홀수 번째에는 반드시 1을 움직이니, 몇 번째 수인지 알면 다음에 움직일 원판을 헷갈리지 않아요.
  • 큰 원판일수록 움직이지 않아요: 1은 전체의 절반의 수에서 움직이지만, 가장 큰 원판은 1번만 움직여요. 큰 원판을 여러 번 움직이고 있다면 멀리 돌아가고 있는 거예요.
  • 처음에는 원판 3개나 4개로: 두 가지 순서가 몸에 익을 때까지는 적은 개수로 여러 번 되풀이하는 것을 추천해요. 익숙해지면 5개, 7개로 늘려요.

원판 개수별 순서

원판 개수별 순서와 도중 모양의 표지는 다음 기사에 정리해 두었어요.

놀면서 해 보기

아래 판에서 두 가지 순서를 해 보세요. 기둥을 누르면 맨 위 원판을 들어 올리고, 다른 기둥을 누르면 거기에 놓아요. 처음에는 원판 4개(짝수)이니 첫 수는 1을 가운데로 움직여요.

4321
0수 (최단 15수)

왼쪽 탑을 오른쪽 기둥으로 그대로 옮기세요. 기둥을 탭하면 맨 위 원판을 듭니다.