브라우저에서 하노이의 탑 퍼즐을 무료로 즐기세요.
세 개의 기둥 중 첫 번째 기둥에 크기 순서대로 쌓인 원반을 세 번째 기둥으로 모두 옮기는 것이 목표입니다. 한 번에 원반 하나만 이동 가능하고, 큰 원반을 작은 원반 위에 놓을 수 없습니다. 원반을 클릭해 선택한 뒤 이동할 기둥을 클릭하면 됩니다. n개의 원반을 완성하는 데 필요한 최소 이동 횟수는 2의 n제곱 빼기 1입니다. 3개 원반은 7번, 4개는 15번, 5개는 31번이 최솟값입니다.
하노이의 탑은 재귀 알고리즘의 교과서적 예제입니다. 핵심 패턴은 가장 큰 원반을 목표 기둥으로 옮기기 위해 나머지 원반들을 보조 기둥에 먼저 쌓는 것입니다. 구체적으로는 상위 n-1개 원반을 보조 기둥으로 옮기고, 가장 큰 원반을 목적지로 이동시킨 뒤, 보조 기둥의 n-1개 원반을 다시 목적지로 옮깁니다. 이 과정을 반복하면 어떤 크기의 퍼즐도 풀 수 있습니다. 처음 접하는 분은 3개 원반부터 시작해 패턴을 익히는 것이 좋습니다.
하노이의 탑은 1883년 프랑스 수학자 에두아르 뤼카가 고안했습니다. 전설에 따르면 64개 원반을 옮기는 브라흐마 사원의 승려들이 작업을 마치는 날 세상이 끝난다고 하는데, 초당 1번 이동한다고 해도 약 5,849억 년이 걸립니다. 컴퓨터 과학에서는 재귀 함수, 분할 정복, 스택 자료 구조를 가르칠 때 빠지지 않는 예제로, 알고리즘 수업 첫 번째 퍼즐로 자주 등장합니다.
이 게임은 원반을 3개에서 8개까지 설정할 수 있고, 이동 횟수 카운터가 당신의 기록을 최적값인 2의 n승 빼기 1과 비교한다. 원반 3개는 7번이면 되지만, 원반을 하나 더할 때마다 최소값이 대략 두 배가 된다. 4개는 15번, 5개는 31번, 6개는 63번, 7개는 127번, 8개는 255번이 필요하다. 가장 작은 원반이 항상 두 수마다 같은 상대적 기둥으로 돌아오는 패턴을 몸에 익히려면 3개나 4개로 시작하라. 이동 횟수가 꾸준히 최적값과 맞아떨어지면 개수를 하나씩 올려라. 재귀적 리듬이 자동으로 느껴지기도 전에 곧장 8개로 뛰어들면 보통 수백 번의 헛된 이동과 절반쯤 정리되다 멈춘 더미만 남는다.
가장 자주 하는 실수는 가장 작은 원반을 일관되지 않은 방향으로 옮기는 것이다. 깔끔하게 풀려면 맨 위 원반이 매 주기 항상 같은 방향으로 움직여야 한다. 원반이 짝수 개면 세 기둥을 한 방향으로 순환하고, 홀수 개면 반대 방향으로 순환한다. 또 머릿속에서 가장 작은 원반을 더 큰 원반 밑에 묻어 두고는 그것이 먼저 움직여야 한다는 걸 잊어버려 막히기도 한다. 또 다른 함정은 목표 기둥에 너무 일찍 매달리는 것이다. 가운데 기둥은 필수적인 임시 보관처라, 그것을 쓰지 않으려 하면 불법적인 배치로 내몰린다. 게임이 작은 원반 위에 큰 원반을 올리는 수를 막으므로, 불법 클릭은 그냥 아무 일도 일어나지 않는다. 헛클릭이 나온다면 작은 원반의 교대 리듬을 따르지 않고 구조와 싸우고 있다는 신호다.
최소값은 2의 원반 개수 제곱에서 1을 뺀 값입니다. 기본인 원반 4개는 15번, 8개는 255번입니다. 카운터가 이 최적 목표와 함께 당신의 이동 횟수를 보여 주므로, 당신의 풀이가 얼마나 효율적이었는지 정확히 알 수 있습니다.
옮기려는 원반이 있는 기둥을 클릭해 선택한 뒤 목적지 기둥을 클릭하세요. 선택한 기둥의 맨 위 원반만 움직입니다. 같은 기둥을 다시 클릭하면 선택이 취소됩니다. 작은 원반 위에 큰 원반을 올릴 수는 없습니다.
게임은 작은 원반 위에 큰 원반을 올리려는 수를 모두 거부하므로 아무 일도 일어나지 않습니다. 빈 기둥을 선택하는 것도 거부합니다. 클릭해도 반응이 없다면, 목적지의 맨 위 원반이 당신이 올리려는 원반보다 작은 것입니다.
있습니다. 두 종류의 수를 번갈아 두세요. 먼저 가장 작은 원반을 정해진 방향으로 한 칸 옮기고, 그다음 가능한 단 하나의 다른 합법적인 수를 두는 것입니다. 풀릴 때까지 반복하세요. 이 간단한 두 단계 반복이 어떤 원반 개수든 아무 계획 없이 최적의 해법을 만들어 냅니다.
아닙니다. 규칙은 어떤 원반 개수에서도 동일합니다. 한 번에 원반 하나씩, 작은 원반 위에 큰 원반은 절대 금지, 그리고 맨 오른쪽 기둥에 전체 더미를 다시 쌓는 것입니다. 원반을 더할수록 최소 이동 횟수와 걸리는 시간만 늘어납니다.