하노이의 탑: 자주 묻는 질문

요령이 있습니다. 그것도 영리함보다는 기계적인 요령입니다. 홀수 번째 이동에서는 가장 작은 원반을 늘 같은 방향으로 한 기둥씩 옮깁니다. 원반 개수가 홀수면 왼쪽, 짝수면 오른쪽이고 끝에 닿으면 반대편으로 넘어가므로, 원반이 3개일 때 첫 수는 A에서 C로 넘어갑니다. 짝수 번째 이동에서는 가장 작은 원반을 건드리지 않는 올바른 수가 언제나 하나뿐이니 생각할 필요 없이 그 수를 둡니다. 둘을 번갈아 하면 한 걸음도 미리 계획하지 않고 완벽한 게임이 됩니다. 공략법 페이지에서 자세히 다룹니다.

왼쪽 기둥에 가장 작은 원반이 위로 오도록 더미 전체를 둔 상태에서 시작합니다. 목표는 같은 더미를 오른쪽 기둥에 만드는 것입니다. 규칙은 셋입니다. 한 번에 하나씩, 늘 기둥 맨 위의 원반만, 큰 원반을 작은 원반 위에 두지 않기. 원반 3개의 가장 짧은 게임은 세 묶음으로 된 일곱 번입니다. A→C, A→B, C→B로 작은 두 원반을 가운데 기둥에 쌓고, A→C로 가장 큰 원반을 건너보내고, B→A, B→C, A→C로 그 두 원반을 다시 그 위에 쌓습니다. 연습판이 있는 게임 방법.

배우기는 쉽고, 어려운 점은 딱 하나입니다. 원반을 하나 더할 때마다 두 배로 길어진다는 것이죠. 원반 3개는 일곱 번이고, 대부분의 사람은(여섯 살 무렵의 아이도) 첫 시도에 풉니다. 원반이 대여섯 개쯤 되면 이것저것 해 보는 방식이 통하지 않아 방법이 필요해지는데, 그 방법의 어려운 점은 뒤로 가는 것처럼 보이는 수를 믿는 것입니다. 목표가 오른쪽인데 더미 전체를 가운데 기둥에 쌓아 올리는 식이죠. 재귀라는 생각이 한번 잡히면 모든 크기가 같은 퍼즐이 됩니다. 재귀라는 생각이 퍼즐의 전부인 이유.

루빅스 큐브와 달리 하노이의 탑의 속도 기록을 공인하는 단체는 없어서, 주장되는 기록끼리 비교할 수 없고 대개는 유일하게 중요한 숫자인 원반 개수조차 밝히지 않습니다. 대신 계산해 봅시다. 원반 n개의 완벽한 게임은 2ⁿ − 1번이고, 익숙한 사람은 1초에 두 번쯤의 속도를 유지합니다. 그러면 원반 3개는 약 4초, 10개(1,023번)는 약 9분, 15개(32,767번)는 약 4시간 반이 걸립니다. 이 사이트의 판은 원반 개수마다 가장 적은 이동 횟수를 브라우저에 저장하고, 결과 화면에 걸린 시간을 보여 줍니다. 계산기에서 어떤 크기든 걸리는 시간을 알려 줍니다.

2ⁿ − 1번이며, 이는 알려진 최고 기록이 아니라 증명된 하한입니다. 원반 3개는 7번, 4개는 15번, 5개는 31번, 10개는 1,023번, 15개는 32,767번입니다. 증명은 두 부분입니다. 재귀적 방법이 그 횟수를 달성한다는 것, 그리고 어떤 풀이도 그보다 짧을 수 없다는 것입니다. 가장 큰 원반은 적어도 한 번 움직여야 하고, 그 위의 더 작은 원반은 모두 먼저 보조 기둥으로 치웠다가 나중에 다시 가져와야 하기 때문입니다. 증명의 두 부분 전체.

T(n) = 2·T(n − 1) + 1, 그리고 T(0) = 0입니다. 방법에서 그대로 읽힙니다. 원반 n개를 옮기려면 n − 1개를 치우고, 원반 하나를 건너보내고, 그 n − 1개를 다시 가져옵니다. 더 작은 풀이 두 개에 이동 한 번을 더한 것이죠. 이를 펼치면 T(n) = 2ⁿ − 1이 되고, 귀납법으로 확인할 수 있습니다. T(n − 1) = 2ⁿ⁻¹ − 1이면 T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1입니다. 점화식을 한 단계씩 풀기.

이동 횟수가 지수적으로 늘긴 하지만 계산 복잡도 면에서는 어려운 문제가 아닙니다. 알고리즘은 몇 줄이면 되고, 다음 수를 정하는 데는 상수 시간이 들며, 풀이가 지수적으로 긴 것은 답 자체가 길기 때문일 뿐입니다. 2ⁿ − 1개의 이동을 출력하는 일을 2ⁿ − 1단계보다 적게 할 수는 없으니까요. NP-난해가 아니고, 기둥 세 개에서 임의의 두 올바른 배치 사이의 최단 경로를 찾는 것도 효율적으로 풀립니다. 정말 어려운 것은 기둥 네 개짜리로, 그 최적 풀이는 1941년에 추측되었다가 2014년에야 티에리 부슈가 증명했습니다. 알고리즘과 그 비용.

프레임-스튜어트 방법을 씁니다. 기둥이 네 개면 n − 1개를 한 덩어리로 옮기지 않습니다. 나눌 지점 k를 골라, 위의 k개를 기둥 네 개를 모두 써서 보조 기둥으로 옮기고, 남은 n − k개를 기둥 세 개만 써서 목표로 옮긴 뒤(보조 기둥 하나가 차 있으니 이 부분은 원래 퍼즐입니다), k개를 그 위에 올립니다. 모든 k를 시험해 가장 좋은 것을 고르면 최적 횟수가 나오는데, 이 수가 극적으로 줄어듭니다. 원반 15개는 기둥 세 개에서 32,767번이던 것이 네 개에서는 129번이 됩니다. 기둥 네 개 퍼즐 하기.

재귀로 표현한 분할 정복입니다. 표준 풀이는 함수 하나로, n − 1개를 출발 기둥에서 보조 기둥으로, 원반 n을 출발에서 목표로, 그 n − 1개를 보조 기둥에서 목표로 옮기며, n이 0이 되면 기저 사례에서 아무것도 하지 않습니다. 재귀를 전혀 쓰지 않는 동등한 반복 알고리즘도 있습니다. 가장 작은 원반을 정해진 방향으로 한 기둥 옮기고, 이어서 유일한 다른 올바른 수를 두는 일을 되풀이하는 것이죠. 최적 풀이는 하나뿐이라 둘 다 정확히 같은 이동 순서를 만듭니다. 알고리즘을 한 줄씩.

재귀 함수 하나와 매개변수 세 개면 됩니다. void hanoi(int n, char from, char to, char via) — n이 0이면 return하고, 아니면 hanoi(n − 1, from, via, to)를 호출하고, from → to 이동을 출력한 뒤, hanoi(n − 1, via, to, from)을 호출합니다. 호출은 hanoi(3, 'A', 'C', 'B')로 합니다. 호출하는 쪽에서 이동이 필요하면 출력하는 대신 std::vector<std::pair<char, char>>에 모으고, n은 평범한 int로 두세요. 부호 없는 매개변수라면 실수로 넘긴 음수가 소리 없이 약 40억이 되어, 간단한 n &lt; 0 검사에서 멈추는 대신 스택이 넘칠 때까지 재귀가 계속됩니다. C++ 전체 프로그램을 한 줄씩 설명.

스택의 두 가지 쓰임이 있으니 구분해 두는 게 좋습니다. 첫째, 기둥 자체가 스택입니다. 각 기둥은 후입선출이고, 늘 맨 위 원반만 건드리며, 한 번의 이동은 한 기둥에서 pop하고 다른 기둥에 push하는 것입니다. 그래서 규칙 검사는 목적지의 맨 위와 한 번 비교하면 끝납니다. 둘째, 명시적 스택으로 재귀를 대신할 수 있습니다. 작업 전체 (n, from, to, via)를 push한 뒤 반복하며 작업을 pop하고, 원반이 남아 있으면 세 부분을 거꾸로 push합니다. 두 번째 옮기기, 원반 n의 한 번 이동, 첫 번째 옮기기 순서입니다. 스택은 마지막에 넣은 것을 먼저 돌려주므로 거꾸로 넣는 게 중요합니다. 재귀 버전에서는 언어의 런타임이 바로 이 일을 대신해 줍니다. 재귀를 전혀 쓰지 않는 풀이.

인공지능에서 이 퍼즐은 공식이 아니라 탐색 문제입니다. 각 상태는 원반마다 어느 기둥에 있는지를 정한 것이라 3ⁿ가지가 있고, 올바른 이동이 그 사이를 잇는 간선입니다. 너비 우선 탐색, A*, 또는 '아직 목표 기둥에 없는 원반 수' 같은 휴리스틱을 쓴 IDA* 같은 탐색이 시작 상태에서 목표까지의 최단 경로를 찾습니다. 뉴얼, 쇼, 사이먼의 General Problem Solver 이래 표준 시험 문제로 쓰였는데, 수단-목표 분석과 목표 분해를 깔끔하게 보여 주기 때문입니다. '가장 큰 원반 옮기기'라는 하위 목표는, 진행을 되돌리는 것처럼 보이는 다른 하위 목표를 먼저 이뤄야만 달성됩니다. 참고로 재귀 알고리즘은 탐색이 아닙니다. 이미 알려진 풀이이며, 쓰지 않을 상태를 살펴보는 일이 없습니다. 심리학 과제로서의 같은 퍼즐.