하노이의 탑 해답기

해답기의 원리

방법은 퍼즐 자체의 논리를 앞에서부터 실행하는 것입니다. 가장 큰 원반을 목표 기둥에 앉히려면 그보다 작은 원반이 모두 다른 곳에, 정확히는 남은 하나의 기둥에 쌓여 있어야 합니다. 그래서 해답기는 먼저 그 작은 더미를 그쪽으로 옮기라고 요청하고, 큰 원반을 건너보낸 다음, 작은 더미를 그 위로 다시 가져오라고 요청합니다. 이 요청들은 모두 원반이 하나 적은 같은 문제이고, 끝까지 내려가면 한 번에 움직이는 원반 하나가 됩니다.

이 해답기가 가득 쌓인 배치만 다루는 해답기들과 다른 점은 한 줄의 추론입니다. 가장 큰 원반이 이미 목표 기둥에 있다면 그 원반에는 할 일이 없고, 문제 전체가 그 위의 원반들로 줄어듭니다. 바로 이 한 가지 경우 덕분에, 처음부터 다시 하게 만드는 대신 절반쯤 진행된 판에서 풀 수 있습니다. 직접 만든 배치에서 나오는 이동 수가 2ⁿ − 1보다 적고, 이미 한참 진행한 판에서는 훨씬 적은 이유이기도 합니다.

1. 1위에 있는 n−1개의 원반을 보조 기둥으로 옮깁니다. 이 원반들이 비켜나기 전에는 아무것도 할 수 없습니다.

2. 2가장 큰 원반이 이제 자유롭고, 목표 기둥도 비어 있습니다. 한 번에 건너갑니다. 이 단계에 필요한 이동은 그것뿐입니다.

3. 3그 위에 n−1개의 원반을 다시 쌓습니다. 원반이 하나 적은 같은 문제이며, 끝까지 내려가면 한 번에 움직이는 원반 하나가 남습니다.

해답 읽는 법

각 행이 한 번의 이동을 가리킵니다. 어떤 원반이, 어느 기둥을 떠나, 어느 기둥에 놓이는지입니다. 원반 1이 가장 작습니다. 규칙에 맞는지 확인할 필요는 없습니다. 목록에 있는 모든 이동은 만들어질 때부터 이미 규칙에 맞습니다.

가득 쌓인 배치에서 시작하면 두 가지 규칙이 바로 눈에 들어옵니다.

• 가장 작은 원반은 한 번 걸러 한 번씩 움직입니다 — 1번, 3번, 5번 이동 — 그리고 세 기둥을 늘 같은 방향으로 돕니다.
• 그 사이의 이동은 가장 작은 원반을 건드리지 않는 유일한 합법적인 이동입니다.

이것이 반복문 해법의 전부이고, 가득 쌓인 배치에서 시작한 해답이라면 어디서든 그대로 읽어 낼 수 있습니다. 직접 만든 배치에서는 목록이 여전히 가장 짧지만, 더 작은 옮기기들을 이어 붙인 것이라서 가장 작은 원반이 중간에 방향을 바꾸기도 합니다. 반복문 해법은 이 방법이 통하는 이유를 보여 주고, 공략법은 그것을 실제로 둘 수 있는 수로 바꿔 줍니다. 재귀 자체를 여섯 가지 언어로 한 줄씩 따라가려면 하노이의 탑 알고리즘을 보세요.

자주 쓰이는 개수에는 저마다의 페이지도 있습니다. 모든 이동과 그 개수만의 특징이 실려 있습니다: 원반 3개부터 10개까지의 해답과 전설의 64개.

해답 가져가기

주소창은 언제나 화면의 판을 그대로 담고 있습니다. 전체 옮기기는 ?disks=5&from=A&to=C로 표시되고, 직접 만든 배치에는 pos=CBBAA 같은 부호가 붙습니다. 가장 작은 원반부터 한 개당 한 글자입니다. 그 링크를 복사하면 정확히 이 퍼즐이 다시 열립니다. 막힌 배치를 말로 설명하는 대신 그대로 보낼 수 있다는 뜻이기도 합니다.

이동 목록 자체는 클립보드로 복사되고, 실물 퍼즐 옆에 놓고 읽을 텍스트 파일이나 스프레드시트에서 열 CSV로 내려받을 수도 있습니다. 내려받기에는 표에 걸린 한도가 없습니다. 원반 15개라도 파일에는 32,767번의 이동이 모두 들어 있습니다.

목록이 12개에서 멈추는 이유

해답은 원반 하나마다 두 배가 됩니다. 12개는 4,095번으로, 길지만 쓸 수 있는 표입니다. 13개는 8,191번, 20개는 1,048,575번이고, 100만 행짜리 표를 사람이 쓸 수 있는 형태로 그려 내는 브라우저는 없습니다. 12개를 넘으면 이 페이지는 정확한 이동 수를 알려 주고 움직이는 판은 그대로 둡니다. 위의 내려받기에는 모든 이동이 들어 있으니 해답이 사라지는 것은 아니고, 표로 찍지 않을 뿐입니다. 숫자만 알고 싶다면 계산기가 원반 64개와 그 너머까지 답합니다.

자주 묻는 질문

하노이의 탑 해답기는 무엇을 하나요?

모든 원반을 한 기둥에 모으는 가장 짧은 이동 순서를 출력합니다. 원반 개수를 주면 고전적인 전체 옮기기를 풀고, 절반쯤 진행된 배치를 주면 거기서부터 풉니다. 뒤쪽은 대부분의 해답기가 하지 못하는 일입니다.

그 해답이 가장 짧은 해답인가요?

네. 이 해답기는 맞기만 한 것이 아니라 최적임이 증명됩니다. 가득 쌓인 시작 배치에서는 정확히 2ⁿ − 1번의 이동을 내놓고, 규칙에 맞는 다른 어떤 배치에서도 목표까지의 진짜 최단 경로를 내놓습니다. 이보다 적은 이동으로 된 순서는 없습니다.

이미 시작한 배치에서도 풀 수 있나요?

네, 직접 만든 시작 배치가 바로 그 용도입니다. 각 원반을 지금 놓여 있는 기둥에 두면, 해답기가 거기서부터 가능한 가장 적은 이동으로 마무리합니다. 대개 처음부터 다시 하는 것보다 훨씬 적습니다.

해답을 공유하거나 저장할 수 있나요?

네. 주소창에는 지금 보고 있는 판이 늘 담겨 있습니다. /ko/solver/?disks=5&from=A&to=C 는 원반 5개의 전체 옮기기이고, 직접 만든 배치에는 pos=CBBAA 같은 부호가 붙습니다. 가장 작은 원반부터 한 개당 한 글자입니다. 링크를 복사하면 정확히 그 퍼즐이 다시 열립니다.

이동 목록을 내려받을 수 있나요?

네. 복사 버튼 옆에서 일반 .txt 파일로도, 이동마다 한 행인 .csv로도 내려받을 수 있습니다. 페이지가 표로 찍지 않는 아주 긴 해답도 내려받을 수 있으니, 원반 15개의 답도 그대로 가져갈 수 있습니다.

이동 목록은 어떻게 읽나요?

각 행이 한 번의 이동을 가리킵니다. 원반 번호, 떠나는 기둥, 놓이는 기둥 순서입니다. 원반 1이 가장 작습니다. 순서대로 옮기면 퍼즐은 저절로 풀립니다. 어떤 원반이 규칙에 맞는지 고민할 필요가 없습니다. 목록에 있는 이동은 이미 모두 맞기 때문입니다.

왜 이동 목록이 12개에서 멈추나요?

원반 12개의 해답은 4,095번입니다. 20개라면 1,048,575행이 되는데, 이를 쓸모 있게 보여 주는 브라우저는 없습니다. 그래서 12개를 넘으면 페이지는 목록 대신 정확한 이동 수와 공식을 주고, 움직이는 판은 여전히 해답을 재생합니다.