공 옮기기(하노이의 탑)란?
1883년 프랑스 수학자 에두아르 뤼카가 만든 고전 퍼즐입니다. 규칙은 단 두 가지예요.
- 공은 한 번에 하나씩만 옮길 수 있습니다
- 큰 공을 작은 공 위에 놓을 수 없습니다
단순한 규칙인데도 몇 수 앞을 내다보지 않으면 금방 막힙니다. 그래서 신경심리학에서 계획력(planning)과 실행기능을 평가하는 도구로 오랫동안 사용돼 왔습니다. 비슷한 원리의 '런던탑 과제(Tower of London)'는 임상 현장에서도 쓰입니다.
최소 이동 횟수는 정해져 있습니다
공이 n개일 때 최소 이동 횟수는 2ⁿ − 1번입니다.
- 공 3개 → 7번
- 공 4개 → 15번
- 공 5개 → 31번
화면 상단에 최소 값이 항상 표시되니, 자신의 이동 횟수와 비교해 보세요.
점수 계산
- 총 5라운드 (공 3개 → 3개 → 4개 → 4개 → 5개)
- 라운드 점수 = 100 × (최소 이동 ÷ 내 이동), 최저 30점 보장
- 즉 최소 이동으로 풀면 100점, 두 배 걸리면 50점입니다
- 만점은 500점
공략 — 재귀적으로 생각하기
이 퍼즐에는 아름다운 해법 패턴이 있습니다.
"n개를 옮기려면, 위의 n−1개를 보조 기둥으로 옮기고 → 가장 큰 것을 목표로 옮기고 → 다시 n−1개를 그 위로 옮긴다"
- 가장 큰 공을 언제 옮길지부터 생각하세요. 그 위의 공들이 전부 비켜야 합니다.
- 실전 요령: 가장 작은 공은 항상 같은 방향으로 순환시키세요. (공이 홀수 개면 목표 기둥 방향, 짝수 개면 반대 방향) 그리고 작은 공을 옮긴 다음에는 작은 공이 관여하지 않는 유일한 이동을 하면 됩니다. 이 두 가지를 번갈아 하면 자동으로 최소 이동이 나옵니다.
- 막혔다면 대개 큰 공을 너무 일찍 옮긴 경우입니다.
내 점수는 어느 정도일까?
- 200점 이하 — 시행착오로 푸는 단계
- 250~350점 — 평균 범위. 패턴이 보이기 시작합니다
- 360~450점 — 상위권. 대부분 최소 이동에 근접합니다
- 500점 — 만점. 전 라운드를 최소 이동으로 해결했습니다
자주 묻는 질문
Q. 잘못 옮겼는데 되돌릴 수 있나요?
A. 되돌리기는 없지만 다시 옮기면 됩니다. 다만 이동 횟수가 늘어 점수가 깎여요.
Q. 공을 어떻게 옮기나요?
A. 옮길 공이 있는 기둥을 탭해서 선택하고, 목표 기둥을 탭하면 이동합니다.
같은 기둥을 다시 누르면 선택이 취소돼요.
Q. 5개는 31번이나 걸리는데 정상인가요?
A. 네, 그게 이론적 최소입니다. 31번에 풀었다면 완벽한 거예요.