무료 하노이의 탑 | 기둥 세 개 퍼즐

작동 원리

이 페이지를 여세요. 시작 기둥에 원판 네 개가 쌓여 있습니다. 최소 15번이면 됩니다.
맨 위 원판을 다른 기둥으로 끌거나, 기둥을 클릭한 다음 원하는 기둥을 클릭하세요. 큰 원판을 작은 원판 위에 놓으면 거부됩니다.
‘풀기’를 누르면 가장 짧은 풀이를 볼 수 있고, ‘단계’로 하나씩 볼 수도 있습니다. 그런 다음 PNG로 저장하세요.

원판은 하나씩, 큰 원판은 작은 원판 위에 놓지 않기

한 번의 이동은 한 기둥의 맨 위 원판을 집어 다른 기둥이나 빈 기둥에 놓는 것입니다. 이동은 이것 한 가지뿐입니다. 놓는 원판은 그 아래 원판보다 작아야 합니다. 이 규칙 덕분에 모든 기둥의 원판은 가장 큰 것이 맨 아래인 순서를 유지합니다.

2ⁿ − 1번, 그보다 적을 수 없다

원판 n개를 옮기려면 먼저 가장 큰 원판 위의 n − 1개를 비켜 놓고, 가장 큰 원판을 한 번 옮긴 다음, n − 1개를 그 위로 옮깁니다. n − 1개에 T번이 걸리면 n개에는 2T + 1번이 걸립니다. 그래서 2ⁿ − 1이 됩니다. 1, 3, 7, 15, 31. 여기서 가장 높은 탑인 원판 8개는 255번이 걸립니다.

같은 퍼즐, 원판 하나 적게

위쪽 n − 1개 원판을 보조 기둥으로 옮깁니다. 가장 큰 원판을 목표 기둥으로 옮깁니다. n − 1개 원판을 보조 기둥에서 목표 기둥으로 옮깁니다. 이 작은 작업 하나하나가 다시 같은 퍼즐입니다. ‘단계’와 ‘풀기’는 가장 짧은 경로를 재생합니다. 완전한 탑에서 시작하면 바로 이 재귀입니다. 뒤섞인 판에서 시작해도 허용된 배치를 탐색해 찾은 가장 짧은 경로입니다.