하노이의 탑

하노이의 탑 하는 방법

1. 원하는 원반 수(3~8개)를 고르세요. 원반은 모두 기둥 1에 쌓여 있고, 가장 큰 것이 아래, 가장 작은 것이 위에 있어요.
2. 기둥을 눌러 맨 위 원반을 집고, 옮기고 싶은 기둥을 누르세요. 원반을 다른 기둥으로 끌어도 돼요.
3. 한 번에 원반 하나만 옮기고, 작은 원반 위에 큰 원반을 놓지 마세요.
4. 탑 전체가 다른 기둥으로 옮겨지면 이겨요. 카운터에 내 이동 횟수와 가능한 최소 횟수가 표시돼요. 막히면 풀이 버튼으로 가장 짧은 해법을 볼 수 있어요.

논리와 재귀의 고전 퍼즐

하노이의 탑은 1883년 프랑스의 에두아르 뤼카가 만든 수학 퍼즐이에요. 원반이 n개일 때 최소 이동 횟수는 2의 n제곱에서 1을 뺀 값이에요. 3개면 7번, 4개면 15번, 5개면 31번, 8개면 255번이에요. 원반이 하나 늘 때마다 작업량은 두 배에 1을 더한 만큼 늘어요.

체계적으로 푸는 방법이 있어요. n개짜리 탑을 옮기려면 먼저 위의 n−1개를 남는 기둥으로 옮기고, 가장 큰 원반을 목적지로 옮긴 다음, n−1개를 그 위로 옮기면 돼요. 재귀의 대표적인 예예요. 또 다른 요령은 가장 작은 원반이 홀수 번째 이동마다 항상 같은 방향으로 움직인다는 거예요. 원반이 홀수 개면 1에서 3으로, 3에서 2로, 2에서 1로 가고, 짝수 개면 1에서 2로, 2에서 3으로, 3에서 1로 가요. 짝수 번째 이동에서는 나머지 두 기둥 사이에서 가능한 이동이 하나뿐이에요.

전설에 따르면 수도승들이 황금 원반 64개로 된 탑을 옮기고 있다고 해요. 1,800경 번이 넘는 이동이 필요하고, 1초에 한 번씩 옮겨도 수천억 년이 걸려요. 모든 것이 브라우저 안에서 이뤄지고 아무것도 서버로 전송되지 않아요. 최고 기록만 기기에 저장돼요.

알아 두세요

• 기록(최소 이동 횟수)은 원반 수별로 이 브라우저에만 저장돼요. 사이트 데이터를 지우면 사라져요.
• 풀이를 사용하면 그 게임은 기록에 반영되지 않아요. 이 버튼은 처음이 아니라 지금 위치에서 가장 좋은 해법을 계산해요.
• 원반 8개는 최소 255번을 옮겨야 해요. 자동 풀이는 적당한 속도로 재생되고, 언제든 멈출 수 있어요.

자주 묻는 질문