전설의 하노이 탑 문제는 기둥이 3개이다.

기둥이 3개인 경우 N개 원판의 최소 이동 횟수는 2^N - 1 인 것은 잘 알려진 사실이다.

기둥이 4개인 경우 원판의 최소 이동 횟수는 어떻게 될까?

기둥 번호는 차례로 A, B, C, D이고 N개의 원판을 A번 기둥에서 D번 기둥으로 옮겨야 한다.

규칙은 다음과 같이 기둥이 3개인 경우와 같다.

조건 1) 한 번에 하나의 원판만 옮길 수 있다.

조건 2) 반드시 큰 원판 위에 작은 원판이 있어야 한다.

조건 3) 각 탑의 맨 위에 있는 원판만 옮길 수 있다.

하노이2(4기둥-이동횟수만)(The Tower of Hanoi III) timer 1s memory 64MB

하노이2(4기둥-이동횟수만)(The Tower of Hanoi III) 1s 64MB