하노이의 탑 알고리즘

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

무엇을 볼 것인가

• 역할이 돌아갑니다. 기둥 B는 첫 호출에게는 보조이고, 그 호출이 만드는 호출에게는 목표입니다. 재귀의 단계마다 세 기둥의 이름표가 바뀌며, 그 이름표 바꾸기가 요령의 전부입니다.
• 스택은 결코 깊어지지 않습니다. 원반 3개일 때 동시에 돌아가는 호출은 많아야 4개 — 3부터 0까지 개수마다 하나씩 — 인데, 프로그램 전체로는 15번을 호출합니다.
• 호출의 절반은 아무것도 하지 않습니다. 그 15번 중 8번은 원반 0개짜리 호출이라 곧바로 반환합니다. 가장 단순한 기저 사례를 고른 대가입니다.
• 옮기는 줄은 정확히 2ⁿ − 1번 실행됩니다. 원반 3개면 일곱 번, 실행 전체의 43단계에 걸쳐서.

첫 번째는 프로그램이 도는 동안 알아채기가 가장 어렵습니다. 그 일이 일어나도 판에서는 아무것도 움직이지 않고, 기둥 아래의 이름만 바뀌기 때문입니다. 여기서는 그것을 멈춰 두었습니다. 첫 호출, 1번째 이동으로 가는 길의 두 호출, 그리고 더미를 되가져오는 호출입니다.

1. hanoi(3, A, C, B)

   첫 호출: 원반 3개 전부를 A에서 C(으)로 옮깁니다. 그러면 B이(가) 보조가 됩니다. 출발 A, 목표 C, 보조 B.

2. hanoi(2, A, B, C)

   그 첫 호출. 원반 3은(는) 위에 원반 1과 2이(가) 있는 동안 움직일 수 없고, 그 둘은 원반 3이(가) 향하는 C(으)로 갈 수 없습니다. 그래서 조금 전까지 보조였던 B이(가) 목표가 되고, C이(가) 보조가 됩니다. 출발 A, 목표 B, 보조 C.

3. hanoi(1, A, C, B)

   한 단계 아래에서 같은 맞바꿈이 한 번 더. 원반 2의 위를 비우려고 원반 1이 C(으)로 가고, B이(가) 다시 보조가 됩니다. 출발 A, 목표 C, 보조 B.

4. hanoi(2, B, C, A)

   원반 3이(가) 건너갔습니다. 뿌리의 두 번째 호출이 원반 1과 2을(를) B에서 그 위로 되돌립니다. 그래서 이제 B이(가) 출발이고, 모든 원반이 처음 있던 A이(가) 보조입니다. 출발 B, 목표 C, 보조 A.

두 번째는 확인하기보다 의심하기가 더 쉽습니다. 그래서 실행 전체를, 각 단계에서 스택이 얼마나 높은지와 함께 보입니다.

• 이 실행은 43단계이고, 호출은 모두 15번입니다.
• 스택의 호출 수는 0과 4 사이를 오르내리며, 그 가운데 8단계에서 4에 이릅니다. 옮길 원반이 없는 호출이 시작해서 반환할 때마다입니다.
• 깊이 4은(는) n = 3일 때의 n + 1이고, 실행의 어느 단계도 그것을 넘지 않습니다.

재귀 트리

각 호출을, 그 호출을 만든 호출 아래의 상자로 그리면 프로그램은 트리가 됩니다. 그리고 각 상자를 그 호출이 하는 이동의 번호 위에 놓으면 또 하나가 드러납니다. 상자를 왼쪽에서 오른쪽으로 읽으면 이동이 순서대로 나온다는 것입니다. 원반 3개라면, 첫 호출 자신의 이동 — 가장 큰 원반 — 은 딱 가운데인 4번째이고, 그 양옆에 원반 2개짜리 세 수 해법이 통째로 놓입니다.

1. 1번째 수: n = 1인 호출(A에서 C(으)로)이 원반 1을(를) 옮깁니다.
2. 2번째 수: n = 2인 호출(A에서 B(으)로)이 n = 1인 두 호출 사이에서 원반 2을(를) 옮깁니다.
3. 3번째 수: n = 1인 호출(C에서 B(으)로)이 원반 1을(를) 옮깁니다.
4. 4번째 수: n = 3인 호출(A에서 C(으)로)이 n = 2인 두 호출 사이에서 원반 3을(를) 옮깁니다.
5. 5번째 수: n = 1인 호출(B에서 A(으)로)이 원반 1을(를) 옮깁니다.
6. 6번째 수: n = 2인 호출(B에서 C(으)로)이 n = 1인 두 호출 사이에서 원반 2을(를) 옮깁니다.
7. 7번째 수: n = 1인 호출(A에서 C(으)로)이 원반 1을(를) 옮깁니다.

이 대칭은 어떤 크기에서도 성립합니다. 2ⁿ⁻¹번째 수는 언제나 가장 큰 원반이 건너가는 수이고, 그 앞뒤는 (n − 1)개짜리 해법을 두 번 둔 것이며, 두 기둥의 역할만 맞바뀝니다. 아무리 긴 이동 목록도 한눈에 읽히는 이유이고, 원반 5개의 해법이 4개의 해법 · 한 수 · 다시 4개의 해법인 이유이기도 합니다.

왜 올바른가

이 알고리즘은 규칙을 어기는 법이 없고 반드시 끝납니다. 그 증명은 전부 적어도 될 만큼 짧습니다. 모든 n에 대한 주장은 이렇습니다.

출발 기둥의 위쪽 n개가 원반 1부터 n까지이고, 다른 곳에 있는 원반은 모두 n보다 크다면, hanoi(n, source, target, spare)는 그 n개를 규칙에 맞게 목표 기둥으로 옮기며, 그 밖의 어떤 것도 건드리지 않는다.

n = 0일 때는 옮길 것이 없고, 아무것도 건드리지 않습니다.

n − 1에 대해 주장이 성립한다고 합시다. 그러면 세 단계는 모두 규칙에 맞습니다.

1. 첫 호출이 원반 1부터 n − 1까지를 보조 기둥으로 옮깁니다. 그럴 자격이 있습니다. 원반 n을 포함해 다른 어떤 원반도 n − 1보다 크기 때문입니다.
2. 원반 n이 목표 기둥으로 갑니다. 이제 그 위에는 아무것도 없고, 목표 기둥에는 n보다 큰 원반만 있습니다.
3. 두 번째 호출이 원반 1부터 n − 1까지를 보조에서 목표로 옮깁니다. 이유는 같습니다. 이제 그 아래에 있는 원반 n이 더 크니까요.

n개 전부가 목표 기둥에 있고, 그 밖에는 아무것도 움직이지 않았습니다. 수학적 귀납법에 따라 주장은 모든 n에 대해 성립하고, 퍼즐 전체는 출발 기둥이 모든 원반을 가진 경우에 해당합니다.

1. 가정n − 1에 대한 주장

   가정은, n − 1개에 대한 호출이 시키는 곳으로 그것들을 규칙에 맞게 옮기고 그 밖의 어떤 것도 건드리지 않는다는 것입니다. 여기에 적용하면 원반 1부터 n − 1까지를 출발 기둥에서 보조 기둥으로 나릅니다. 그럴 자격이 있습니다. 그것들을 올려놓을 수 있는 어떤 원반도 — 원반 n을 포함해 — 나르고 있는 어떤 원반보다 크기 때문입니다.

2. 여기서 증명규칙에 맞는 한 번의 이동

   증명이 스스로 논증해야 하는 단계는 여기뿐이고, 그것은 한 번의 이동입니다. 원반 n의 위는 앞 단계가 비웠으니 비어 있습니다. 목표 기둥에는 n보다 큰 원반만 있습니다. 더 작은 것은 모두 보조 기둥에 있기 때문입니다. 그러므로 이 이동은 규칙에 맞습니다.

3. 가정n − 1에 대한 주장, 다시

   같은 가정을 두 번째로 써서, 원반 1부터 n − 1까지를 보조에서 목표로 가져옵니다. 앞과 같은 이유로 규칙에 맞습니다. 이제 그 아래에 있는 원반 n이 더 크니까요. n개 전부가 목표에 있고 그 밖에는 아무것도 움직이지 않았습니다. 그것이 n에 대한 주장입니다.

점화식, 제대로 푸는 법

T(n)을 원반 n개에 대해 이 알고리즘이 하는 이동의 수라고 합시다. 이 함수는 n − 1개에 대한 호출을 두 번 하고 자신의 이동을 한 번 하며, 원반이 없으면 한 번도 움직이지 않습니다.

풀려면 점화식을 자기 자신에 대입해 가며 규칙을 찾습니다. 이것을 펼치기, 또는 망원경식 소거라고 합니다.

규칙을 발견하는 것은 증명이 아니니, 귀납법으로 확인합니다. T(0) = 0 = 2⁰ − 1. 그리고 T(n − 1) = 2ⁿ⁻¹ − 1이면 T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1입니다. 닫힌 식은 모든 n에 대해 정확합니다.

세 번째 길도 있는데, 그것은 이미 본 그림입니다. 위의 재귀 트리는 완전 이진 트리입니다. 뿌리는 n개를 옮기고, 그 아래 두 호출은 각각 n − 1개, 그 아래 네 호출은 n − 2개를 옮기는 식입니다. 따라서 깊이 k에는 2ᵏ개의 호출이 있고, 마지막 층은 깊이 n − 1이며, 그 호출들은 저마다 정확히 한 번씩 옮깁니다. 층을 모두 더하면 개수가 등비급수로 나옵니다.

펼치기, 귀납법, 트리 — 세 가지 방법에 답은 하나입니다. 알아 둘 값어치가 있습니다. 끊임없이 권해지는 네 번째 방법이 있고, 그것이 틀렸기 때문입니다.

같은 계산으로 호출 수도 셉니다. n {">"} 0인 호출은 저마다 두 개를 더 만드니, C(n) = 2C(n − 1) + 1, C(0) = 1이 되고, 펼치면 2ⁿ⁺¹ − 1입니다. 원반을 옮기는 2ⁿ − 1번의 호출에, 곧바로 반환하는 2ⁿ번을 더한 값입니다.

시간과 공간 복잡도

각 호출은 두 번의 재귀 호출 말고는 상수만큼의 일만 하므로, 실행 시간은 호출 수에 비례합니다. 즉 Θ(2ⁿ)입니다. 아무리 영리한 알고리즘도 이를 이길 수 없습니다. 출력 자체가 2ⁿ − 1개의 이동이고, 2ⁿ − 1은 지금까지 찾은 최선이 아니라 증명된 최솟값이기 때문입니다. 더 짧은 해답이 없다는 증명은 별도의 페이지에 있습니다: 왜 최소가 2ⁿ − 1인가.

메모리는 이야기가 다릅니다. 호출이 한꺼번에 다 존재하지는 않습니다. 어떤 호출은 형제 호출이 시작하기 전에 끝나므로, 스택에는 단계마다 하나씩, n부터 0까지만 올라갑니다. 쓰는 공간은 Θ(n)입니다. 전설의 원반 64개라면 스택 프레임이 65개인데, 어떤 컴퓨터든 아무렇지 않게 감당합니다. 바닥나는 쪽은 시간입니다. 18,446,744,073,709,551,615번의 이동을 1초에 10억 번씩 해도 여전히 584년입니다.

그 수는 전설의 것이고, 그 전설은 들리는 것보다 젊습니다. 사제들이 64개의 황금 원반을 옮기고 마지막 원반을 놓는 순간 세상이 끝난다는 사원 이야기가 처음 인쇄된 것은 1884년, 그 전해에 파리에서 팔리기 시작한 퍼즐을 홍보하는 글에서였고, 존재하지도 않는 교수의 이름을 달고 있었습니다. 수도승들의 속도, 곧 1초에 한 번씩이라면 세상에는 아직 5,850억 년이 남아 있습니다. 지금 우주 나이의 약 마흔 배입니다. 퍼즐과 이야기를 모두 만든 수학자는 에두아르 뤼카로, 2¹²⁷ − 1이 소수임을 손으로 증명했고, 연회에서 종업원이 떨어뜨린 접시에 베인 상처가 감염되어 49세에 세상을 떠났습니다.

이 식에 숫자를 넣으면 두 종류의 비용이 갈라집니다. 원반이 하나 늘 때마다 이동과 호출은 두 배를 조금 넘게 늘고, 스택이 닿는 가장 깊은 곳은 한 칸만 깊어집니다.

최소 이동 수 계산기는 어떤 개수에 대해서도 이동 수와 시간을 계산하고, 마지막 줄 — 전설의 개수 — 에는 따로 마련된 페이지가 있습니다.

재귀 없이

같은 이동은 두 가지 규칙만 있는 단순한 반복문으로도 만들 수 있습니다.

• 홀수 번째 이동: 가장 작은 원반을 정해진 방향으로 한 기둥씩 옮깁니다. 원반 수가 홀수면 A → C → B, 짝수면 A → B → C입니다.
• 짝수 번째 이동: 가장 작은 원반을 건드리지 않는 유일한 합법적인 이동을 합니다. 그런 이동은 언제나 정확히 하나 있습니다.

이 두 규칙은 재귀 해법을 한 수도 빠짐없이 그대로 재현합니다. 반복문 해법 페이지가 그 이유를 보여 주고, 판 위에서 재생합니다.

기둥을 아예 저장하지 않는 더 기묘한 방식도 있습니다. m번째 이동의 원반, 출발, 도착을 모두 m의 이진수 자릿수에서 읽어 낼 수 있습니다. 그 연결과, 그 안에 숨은 그레이 코드는 하노이의 탑, 이진수, 그레이 코드에 있습니다.

처음이 아닌 배치에서 시작할 때

교과서의 함수는 모든 원반이 출발 기둥에 있다고 전제합니다. 절반쯤 진행된 퍼즐을 주면 할 말이 없습니다. 경우를 하나만 더하면 해결됩니다. 가장 큰 원반을 보세요.

• 이미 가야 할 기둥에 있나요? 그 원반에는 이동이 필요 없습니다. 더 작은 원반들을 같은 기둥으로 보내며 풀면 됩니다.
• 다른 곳에 있나요? 더 작은 원반들을 지금 있는 기둥도 갈 기둥도 아닌 기둥으로 치우고, 그 원반을 옮긴 뒤, 앞서와 똑같이 이어 갑니다.

이 방식은 규칙에 맞는 어떤 배치에서도 가장 짧은 해답을 찾아냅니다. 하노이의 탑 해답기가 돌리는 것이 바로 이것입니다.

스스로 확인하기

이 페이지가 이미 답한 세 가지 질문입니다. 열어 보기 전에 먼저 풀어 보세요. 잘 떠오르지 않는다면, 답과 함께 적힌 절이 다시 읽어 볼 곳입니다.

1. 원반 3개는 일곱 번입니다. 5개는 몇 번이고, 그중 원반 5 자신을 옮기는 것은 몇 번일까요?

   답 보기

   31번, 곧 2⁵ − 1입니다. 그리고 그중 가장 큰 원반을 옮기는 것은 정확히 한 번입니다. 가장 큰 원반을 뺀 나머지는 모두 한 번보다 많이 움직입니다. 해답의 두 절반이 저마다 그것들을 옮겨야 하기 때문입니다. 점화식, 제대로 푸는 법.

2. hanoi(3, A, C, B)는 첫 호출로 hanoi(2, A, B, C)를 만듭니다. 그 호출의 목표가 C가 아니라 B인 이유는 무엇일까요?

   답 보기

   원반 3이 C로 가야 하고, C가 비어 있어야만 거기 놓일 수 있기 때문입니다. 그래서 그 위의 두 원반은 다른 곳에 두어야 하는데, 그 다른 곳은 B뿐입니다. 어떤 호출이 겨냥하는 기둥은, 그 호출이 만드는 첫 호출이 비워 두어야 할 기둥이 됩니다. 세 인자 가운데 둘이 들어가면서 자리를 바꾸는 이유가 그것입니다. 무엇을 볼 것인가.

3. 원반 20개를 풀면 2,097,151번을 호출합니다. 그중 같은 순간에 스택에 있는 것은 많아야 몇 개일까요?

   답 보기

   21개입니다. 20부터 0까지 개수마다 하나씩. 어떤 호출은 형제 호출이 시작하기 전에 끝나므로, 호출이 한꺼번에 다 존재하는 일은 없습니다. 일은 지수적이지만 메모리는 선형입니다. 시간과 공간 복잡도.

여러분의 언어로 보는 알고리즘

같은 함수를 여섯 가지 언어로. 각각 실행할 수 있는 프로그램, 한 줄씩의 설명, 옆에서 도는 판, 그리고 그 언어만의 사정이 함께 있습니다. 원반 64개의 이동 수를 세려는 순간 그 사정이 바로 문제가 됩니다. 이 여섯 페이지는 영어입니다.

• Python로 구현한 하노이의 탑ENRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• JavaScript로 구현한 하노이의 탑ENWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Java로 구현한 하노이의 탑ENWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• C로 구현한 하노이의 탑ENUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• C++로 구현한 하노이의 탑ENCollecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• C#로 구현한 하노이의 탑ENTop-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

이 페이지의 낱말

기저 사례

재귀 함수가 자기 자신을 부르지 않고 곧바로 답하는 경우입니다. 재귀를 멈추는 것이 바로 이것입니다. 여기서는 n = 0입니다. 옮길 원반이 없으니 할 일도 없고, 호출은 반환합니다. 아무리 깊은 호출의 사슬도 끝은 여기입니다.

재귀 사례

기저 사례가 아닌 전부입니다. 같은 문제의 더 작은 판을 풀고 그 답으로 자신의 답을 짓는 부분이지요. 여기서는 n − 1개를 치우고, 원반 n을 옮기고, 그 n − 1개를 되돌리는 세 줄입니다.

호출 스택

시작했지만 아직 끝나지 않은 함수 호출의 목록이며, 가장 최근 것이 맨 뒤입니다. 호출은 시작할 때 쌓이고 반환할 때 빠지므로, 스택은 프로그램이 어디로 돌아갈지 기억하는 방법입니다. 위의 패널이 그리는 것이 이것이고, 실제 메모리이기도 합니다. 그래서 그 깊이가 알고리즘의 공간 비용이 됩니다.

스택 프레임

호출 스택의 한 칸입니다. 한 번의 호출에 속한 인자와 지역 변수를 말하지요. 패널에 있는 스택의 각 행이 한 프레임이며, 그 호출만의 n과, 어느 기둥이 출발·목표·보조인지에 대한 그 호출만의 생각을 담고 있습니다. 원반 64개에는 65개의 프레임이 필요한데, 그것은 아무것도 아닙니다. 문제는 이동 횟수입니다.

망원경식 소거

펼치기라고도 합니다. 점화식을 자기 자신에 규칙이 드러날 때까지 대입한 뒤, 대입 횟수를 정해 알려진 처음 값만 남기는 풀이법입니다. 가운데 항들이 망원경의 통처럼 겹쳐 접히기 때문에 붙은 이름입니다.

Θsaid “빅 세타”

위로도 아래로도 막는 증가율입니다. Θ(2ⁿ)은 비용이 2ⁿ보다 빠르지 않다는 뜻이 아니라, 2ⁿ처럼 자란다는 뜻입니다. O(2ⁿ)이라면 천장만 약속하는 셈이지요. 여기서 정직한 표기는 Θ입니다. 이 알고리즘은 실제로 2ⁿ − 1번을 옮기고, 운이 좋아 일찍 끝나는 법이 없기 때문입니다.

자주 묻는 질문

하노이의 탑 재귀 알고리즘은 어떻게 작동하나요?

원반 n개를 출발 기둥에서 목표 기둥으로 옮기려면, 먼저 위의 n − 1개를 보조 기둥으로 옮기고, 다음으로 가장 큰 원반을 목표로 옮기고, 마지막으로 그 n − 1개를 보조에서 목표로 옮깁니다. 이 두 번의 작은 옮기기는 원반이 하나 적은 같은 문제이므로 함수가 자기 자신을 부르고, 옮길 원반이 없는 호출은 그냥 반환합니다.

하노이의 탑은 분할 정복인가요, 동적 계획법인가요?

분할 정복입니다. 문제는 원반 n − 1개짜리 부분 문제 둘로 나뉘고, 각각이 재귀로 정복되며, 결합 단계는 가장 큰 원반의 한 번뿐인 이동입니다. 동적 계획법이 아니며, 메모이제이션도 도움이 되지 않습니다. 부분 문제가 실제로 되풀이되는데도 그렇습니다. 기둥이 셋이면 출발·목표·보조를 이름 붙이는 방법이 여섯 가지뿐이라, 원반 3개를 푸는 동안 hanoi(1, A, C, B)는 정말로 두 번 불립니다. 그것을 캐시해도 얻는 것이 없습니다. 부분 문제의 답은 2ᵏ − 1개의 이동 목록이고, 그 길이의 목록을 다시 내보내는 비용은 만들어 내는 비용과 같기 때문입니다. 여기서는 일 자체가 출력이고, 어떤 표를 만들어도 출력이 짧아지지는 않습니다.

하노이의 탑 점화식에 마스터 정리를 쓸 수 있나요?

없습니다. 마스터 정리는 T(n) = aT(n/b) + f(n) 꼴, 즉 부분 문제가 원래 문제의 몇 분의 일인 경우를 다룹니다. 하노이의 탑의 점화식은 T(n) = 2T(n − 1) + 1로, 부분 문제는 원반 하나만큼 작을 뿐 크기의 몇 분의 일이 아닙니다. 펼치면 T(n) = 2ⁿ − 1이 바로 나오고, 귀납법이 그것을 확인합니다.

재귀는 얼마나 깊어지나요?

기저 사례가 n = 0이면 동시에 스택에 있는 호출은 많아야 n + 1개입니다. n부터 0까지 개수마다 하나씩이지요. 기저 사례를 n = 1로 하면 n개입니다. 어느 쪽이든 깊이는 선형으로만 자라며, 그래서 재귀 해법은 지수적인 횟수를 옮기면서도 메모리는 O(n)만 씁니다.

재귀 해법은 함수를 몇 번 호출하나요?

기저 사례가 n = 0일 때 2ⁿ⁺¹ − 1번입니다. 원반을 옮기는 2ⁿ − 1번의 호출에, 옮길 것을 찾지 못하고 반환하는 2ⁿ번을 더한 값이지요. 원반 3개면 15번입니다. 기저 사례를 n = 1로 써서 만들면, 같은 프로그램이 정확히 2ⁿ − 1번, 이동마다 한 번씩 호출합니다.

반복 알고리즘이 재귀보다 빠른가요?

의미 있는 차이는 없습니다. 둘 다 2ⁿ − 1번의 이동을 만들어야 하므로 둘 다 2ⁿ에 비례하는 시간이 듭니다. 반복 방식은 함수 호출 비용을 피하고 스택을 다 쓸 일도 없지만, 여기서 재귀의 깊이는 n단계뿐입니다. 여러분이 기다릴 만한 어떤 개수에서도 스택이 바닥나는 일은 현실적인 위험이 아닙니다.

하노이의 탑 알고리즘을 순서도로 그리면 어떻게 되나요?

별것이 되지 않습니다. 그것이 정직한 답입니다. 순서도는 제어가 상자들을 한 번 지나가는 모습을 보여 주는데, 이 알고리즘의 두 번째 상자는 순서도 전체를 다시 그린 것입니다. 세 단계 아래에서, 기둥 둘이 맞바뀌고 원반이 하나 적은 채로요. 순서도에는 그것을 나타낼 표기법이 없습니다. 그래서 재귀 해법의 순서도는 틀렸거나, 아니면 「hanoi 호출」이라고 적힌 상자 두 개가 있는 한 번의 호출 그림일 뿐이고, 후자는 네 줄짜리 의사 코드가 알려 주는 것 이상을 알려 주지 않습니다. 그것을 나타내는 그림은 재귀 트리입니다. 각 호출이 그것을 만든 호출 아래에 그려지고, 각 상자가 자신이 하는 이동 위에 놓입니다. 그 그림이 이 페이지에 있고, 상자를 왼쪽에서 오른쪽으로 읽으면 이동이 순서대로 나옵니다.

이미 절반쯤 푼 퍼즐도 이 알고리즘으로 풀 수 있나요?

교과서 방식으로는 안 됩니다. 모든 원반이 한 기둥에서 시작한다고 전제하기 때문입니다. 경우를 하나 더하면 일반화됩니다 — 가장 큰 원반이 이미 목표 기둥에 있으면 건너뛰고 그 위의 원반들을 푼다 — 그리고 그 방식은 규칙에 맞는 어떤 배치에서도 가장 짧은 해답을 찾습니다. 이 사이트의 해답기가 돌리는 것이 바로 그것입니다. 해답기 열기 →