하노이탑
기둥을 눌러 맨 위 원판을 집고, 다른 기둥을 눌러 내려놓습니다. 작은 원판 위에 큰 원판은 못 얹습니다. 원판을 모두 오른쪽 기둥으로 옮기면 끝나고, 화면에 최소 횟수가 함께 서 있어 몇 번을 더 썼는지 바로 보입니다.
기둥을 눌러 맨 위 원판을 집고, 다른 기둥을 눌러 내려놓습니다. 작은 원판 위에 큰 원판은 못 얹습니다. 자판의 1·2·3 으로도 됩니다.
규칙에 맞게 놓인 수만 셉니다
원판 수를 고르면 최소 횟수가 함께 섭니다. 3개 7번, 5개 31번, 8개 255번입니다. 큰 원판을 작은 원판 위에 놓으려 하면 아무 일도 일어나지 않고 횟수도 오르지 않습니다. 집은 기둥을 다시 누르면 내려놓기가 취소되고, 이것도 세지 않습니다. 되돌리기는 없습니다 — 잘못 놓은 수도 한 번, 되돌리는 것도 한 번이라 실수 하나가 두 번입니다.
가장 작은 원판이 갈 곳은 정해져 있습니다
최소 횟수로 가는 길은 하나뿐이고 외울 것은 두 줄입니다. 홀수 번째 수마다 가장 작은 원판을 옮기되 늘 같은 방향으로 돕니다 — 원판이 홀수 개면 왼쪽→오른쪽→가운데→왼쪽, 짝수 개면 왼쪽→가운데→오른쪽→왼쪽 순입니다. 짝수 번째 수에서는 가장 작은 원판을 건드리지 않는 수가 꼭 하나뿐이라 고를 것이 없습니다. 자동으로 풀기는 이 차례를 0.32초에 한 수씩 놓습니다.
기록은 원판 수마다 따로 남습니다
다 옮기면 그 원판 수의 기록과 견줘 더 적을 때만 갈아 둡니다. 기록은 이 브라우저에만 남고 서버로 보내지 않습니다. 자동으로 풀기로 끝낸 판은 기록에 남기지 않습니다 — 원판은 실제로 움직이지만, 기록은 손으로 옮긴 판만 셉니다.
자주 묻는 질문
Q최소 몇 번이면 되나요?
원판이 n개면 2ⁿ − 1 번입니다. 3개면 7번, 4개면 15번, 5개면 31번, 10개면 1,023번입니다. n개를 옮기려면 위의 n−1개를 비켜 두고, 가장 큰 것을 옮기고, 다시 그 위에 얹어야 하므로 f(n) = 2·f(n−1) + 1 이 되기 때문입니다.
Q그게 정말 최소인가요? 더 좋은 방법이 있을 수도 있잖아요.
없습니다. 외운 식을 그냥 믿지 않고 원판 9개까지 있을 수 있는 자리를 전부 훑어 확인했습니다. 원판 n개의 자리는 3ⁿ 가지인데, 처음 자리에서 한 수씩 퍼뜨려 보니 3ⁿ 가지에 모두 닿았고 끝 자리까지의 거리가 2ⁿ − 1 과 하나도 어긋나지 않았습니다.
Q「자동으로 풀기」는 어떻게 두나요?
최소 횟수로 가는 차례를 그대로 놓습니다. 1개부터 14개까지 그 차례를 한 수씩 실제로 놓아 보며 규칙에 어긋나는 수가 없고 반드시 다 옮겨지는지 확인했습니다(14개는 16,383번입니다).
Q원판이 왜 8개까지만 있나요?
8개면 최소 255번입니다. 그 위로는 한 판이 손으로 할 것이 못 됩니다 — 10개면 1,023번, 20개면 백만 번이 넘습니다. 전설처럼 이야기되는 64개는 2⁶⁴ − 1, 약 1,844경 번입니다.
Q원판을 아무 기둥으로나 옮겨도 되나요?
됩니다. 세 기둥 어디로든 옮길 수 있고, 가운데 기둥은 잠시 비켜 두는 자리로 쓰입니다. 최소 횟수로 가려면 그 비켜 두기를 몇 번 하느냐가 전부입니다.
Q가운데 기둥으로 다 옮기면 안 되나요?
끝으로 치지 않습니다. 오른쪽 기둥에 다 쌓여야 끝난 것으로 봅니다. 가운데에 쌓아도 횟수는 세지만, 거기서 오른쪽으로 다시 옮기려면 최소 횟수만큼이 또 듭니다.
Q최소보다 많이 썼는데 어디서 틀렸는지 알 수 있나요?
화면은 알려 주지 않습니다. 대신 가장 작은 원판의 방향만 보면 됩니다. 도는 방향을 한 번이라도 거꾸로 가면 그 자리에서 두 수가 낭비됩니다. 최소보다 2·4·6번 많다면 거의 그 경우입니다.