◼︎ 원반이 세 개일 때

원반이 세 개일 때부터는 조금 더 생각을 해야 합니다. 원반이 세 개인 문제를 풀기 전에 원반이 두 개인 문제를 이미 풀었다는 사실을 꼭 기억해야 합니다. 즉, 우리는 특정 기둥에 있는 원반 두 개를 우리가 원하는 기둥으로 옮기는 방법을 이미 알고 있다는 것입니다.

 

➊ 1번 기둥에 있는 원반 세 개 중에 위에 있는 원반 두 개를 비어 있는 2번 기둥(보조 기둥)으로 옮깁니다. 하노이의 탑 규칙에 따르면 한 번에 원반을 두 개씩 옮길 수 없다고 했지만, 우리는 이미 원반이 두 개일 때 하노이의 탑을 푸는 방법을 알고 있으니 그 방법을 그대로 적용하면 됩니다. 3번 기둥을 보조 기둥으로 사용하여 1번 기둥에 있는 원반 두 개를 2번 기둥으로 옮기는 문제이므로 1 → 3, 1 → 2, 3 → 2 순서로 옮기면 됩니다(실제로 원반은 세 번 이동합니다).

 

그림 6-9 원반 두 개를 1에서 2로 이동(1 → 3, 1 → 2, 3 → 2)

 

➋ 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮깁니다(1 → 3).

 

그림 6-10 남은 원반을 1에서 3으로 이동