공략4분 읽기Tower Shift
하노이의 탑 해법: 완벽하게 푸는 간단한 규칙
미리 계획하지 않아도 Tower Shift를 최소 수로 푸는 두 박자 리듬.
왜 열다섯이 최소인가
가장 큰 원판을 옮기려면 먼저 그 위의 원판 세 개를 빈 기둥으로 치우고, 큰 원판을 옮긴 다음, 그 위에 세 개를 다시 쌓아야 합니다. 원판 세 개를 옮기는 데 일곱 수가 걸리니, 네 개는 일곱 더하기 하나 더하기 일곱, 열다섯 수입니다. 일반적으로 원판 n개의 탑에는 2의 n제곱 빼기 1 수가 필요합니다.
이렇게 두 배씩 늘어나는 것이 이 퍼즐에 얽힌 옛 전설의 요점입니다. 원판 예순네 개를 옮기는 승려들에게는 1,800경 번이 넘는 이동이 필요하다고 합니다.
두 박자 리듬
완벽하게 풀기 위해 재귀적으로 생각할 필요는 없습니다. 두 종류의 수를 번갈아 두세요. 홀수 번째에는 가장 작은 원판을 옆 기둥으로 하나 옮깁니다. 방향은 늘 같고, 끝에 닿으면 반대쪽 끝으로 돌아갑니다. 짝수 번째에는 가장 작은 원판을 건드리지 않는 유일한 합법적인 수를 둡니다.
원판이 네 개일 때 가장 작은 원판은 왼쪽에서 오른쪽으로 갑니다. 출발 기둥, 가운데, 오른쪽, 다시 출발 기둥. 원판 수가 홀수라면 반대 방향입니다.
실수가 생기는 방식
낭비되는 수는 거의 모두 가장 작은 원판이 반대 방향으로 간 경우입니다. 보통 오른쪽 기둥이 목표처럼 보여서 곧장 그리로 가고 싶어지기 때문입니다. 리듬을 믿으세요. 수가 열다섯을 넘으면 다시 시작하고, 처음 몇 수는 방향을 소리 내어 말해 보세요.