하노이탑 퍼즐을 쉽게 푸는 해법

예전에 퍼즐 종류 코너에 포스팅한 '하노이 탑 (Tower of Hanoi) 퍼즐에 얽힌 놀라운 이야기' 포스트 이후로 하노이탑을 검색 키워드로 하는 유입 건수가 의외로 많더군요.
퍼즐러 갱 생각에는 아마도 학생들이 숙제를 하기 위해서 참고하는 것이 아닐까 합니다.

그래서 이번 포스트에서는 하노이탑을 쉽게 푸는 방법 즉 해법 규칙을 공유하려고 합니다.

하노이탑은 원반 개수가 올라갈 수록 미션을 달성하기 위한 움직임 수가 기하급수적으로 늘어납니다.

그래도 어렵지는 않습니다. 일정한 흐름이 있기 때문입니다. 퍼즐러갱이 파악한 결과 하노이탑 퍼즐을 풀기 위한 원칙은 크게 7가지 뿐입니다. 이 7가지 원칙을 유지하면 아무리 많은 원반 수라 할 지라도 쉽게 하노이탑을 풀 수 있습니다.

그 일곱 가지 원칙이란 다음과 같습니다.
(설명의 편의상 원반이 3개인 경우와 4개인 경우를 좌우 그림으로 나누어 보여드리겠습니다.)

1. 기둥을 왼쪽부터 1, 2, 3 이라고 했을 때, 1번 기둥에 현재 탑이 쌓여 있고 목표는 3번 기둥으로 옮기는 것이라고 가정할 경우, 1번 기둥에 쌓여 있는 원반 수가 홀수일 경우에는 맨 위의 원반을 3번으로 옮기고, 1번 기둥에 쌓여 있는 원반 수가 짝수일 경우에는 맨 위의 원반을 2번으로 옮깁니다. 아래 그림의 1회 부분을 설명한 것입니다.

첫 스타트가 중요합니다. 1번 원칙이 유지되어야만 목표로 하는 기둥에 모든 원반을 제대로 옮길 수 있습니다. 이 원칙이 유지되지 않으면 원하지 않는 기둥에 모든 원반이 옮겨지게 됩니다.

 

(1회)

 

2. 1번 기둥에 남아있는 맨 위의 원반(원래에는 위에서 두번째 층) 조각을 비어있는 기둥으로 옮깁니다. 이건 그리 어렵지 않죠?

 

(2회)

 

3. 이미 한번 옮겼던 가장 작은 원반 조각을 원래 있던 1번 기둥이 아닌 새로운 기둥, 즉 위에서 두번째 층 조각이 현재 놓여 있는 기둥으로 옮깁니다. (이때 1번 기둥에 있는 원반은 2번이나 3번으로 옮길 수가 없는 조건이 형성되어 있습니다. 1번 기둥에 남아있는 맨 위의 원반은 2번 또는 3번에 놓여있는 원반보다 크기 때문입니다. 따라서 3번 원칙은 어찌 보면 원칙이라기 보다는 어쩔 수 없이 해야 하는 단계 또는 원칙이라고 볼 수도 있습니다.)

그리고 2개의 원반으로 구성된 하노이탑을 완성한다고 생각하면 쉽습니다.

원반수가 아무리 많든 2개 원반으로 구성된 하노이탑을 먼저 쌓고, 이후에 3개 원반으로 구성된 하노이탑을 쌓고, 그 이후에 4개 원반으로 구성된 하노이탑을 쌓고, 또 그 이후에 5개 원반으로 구성된 하노이탑을 쌓는 과정을 거치게 됩니다.

 

(3회) --> 2개 완성

 

4. 1번 기둥의 맨 위에 있는 원반(원래는 위에서 세번째 층 조각)을 비어있는 기둥에 옮깁니다. (이 원칙도 어찌 보면 어쩔 수 없이 행해야 하는 자연스러운 결과라고 할 수 있습니다.)

(4회)

 

5.  이제 이번 단계가 매우 중요합니다. 1번 기둥에 있던 최초 조각 수가 3개였다면 1번 기둥에는 원반이 없을 것입니다. 4개 이상이었다면 지금까지 옮긴 원반보다 큰 원반이 있을 것입니다. 3개였다면 옮길 원반이 없는 것이며, 4개이상이면 1번 기둥에 있는 원반을 2, 3번으로 옮길 수는 없습니다. 왜냐하면 2, 3번에 이미 자신보다 작은 원반이 놓여 있기 때문이죠.

따라서 가장 작은 원반을 옮겨야만 하는데 가장 작은 원반이 갈 수 있는 곳은 두군데입니다. 
이때 가장 작은 원반이 놓여 있는 기둥(두개의 원반이 놓여 있는 기둥)을 최초의 원칙인 1번 원칙을 적용하면 됩니다. 즉 짝수개가 놓여 있으면 목표하는 기둥이 아닌 기둥으로, 홀수개가 놓여 있으면 목표하는(최종적으로 쌓고자 하는) 기둥으로 옮기면 되는 것입니다.

여기서 목표로 하는 기둥이라 함은 현재 2개이므로 3개의 원반을 쌓을 곳을 의미합니다. 최초에 원반의 개수가 3개인 하노이탑(왼쪽 그림)의 경우는 3개의 원반을 쌓을 곳은 3번 기둥이었죠. 최초에 원반의 개수가 4개인 하노이탑(오른쪽 그림)의 경우는 3개의 원반을 쌓을 곳은 2번 기둥입니다. 먼저 2번 기둥에 3개를 쌓고 나중에 최종 목표인 3번 기둥에 4개의 원반을 쌓아서 미션을 완성하는 것입니다.

원반의 개수가 증가하더라도 이 원칙은 그대로 유지됩니다. 즉 만일 최초의 원반수가 5개였고 목표 기둥이 3이라면 4개를 먼저 2번 기둥에 쌓고, 3개를 3번 기둥에 쌓고, 2개를 2번 기둥에 쌓는 것입니다.

여기서는 가장 작은 원반이 놓여 있는 기둥에 원반이 총 2개 있으므로 짝수, 짝수이므로 목표로 하는 기둥이 아닌 다른 기둥으로 옮기면 됩니다. 결국 1번 기둥으로 옮겨야 하는 것이지요.

(5회)

 

6. 가장 작은 원반을 1번 기둥으로 옮기고 나면 다음에 움직여야 하는 원반은 자연스럽게 하나밖에 없습니다. 즉 최초에 위에서 두번째 원반(여기서는 초록색 원반)입니다. 그리고 이 초록색 원반이 갈 곳도 딱 한군데밖에 없습니다. 가장 작은 원반 위로는 가지 못하므로 최초에 위에서 세번째 원반(빨간색 원반) 위로 옮기는 경우만 가능해집니다.

 (6회)

 

7. 이제 3개의 원반을 가지런히 쌓을 수 있는 기회가 생겼습니다. 바로 아래 그림처럼 말이죠. 이렇게 하면 3개의 원반을 다 옮길 수 있습니다.

(여기에서도 사실은 1번 원칙이 적용되는 것입니다. 1번 기둥에 있는 원반의 개수가 왼쪽은 하나, 즉 홀수입니다. 따라서 목표로 하는 기둥인 3번 기둥으로 옮기면 됩니다. 1번 기둥에 있는 원반의 개수가 오른쪽은 둘, 즉 짝수입니다. 따라서 목표로 하는 기둥이 아닌 2번 기둥으로 옮기면 됩니다. 최초의 원반 총 개수가 3개인 경우는 3번 기둥, 최초의 원반 개수가 4개인 경우는 2번 기둥으로 옮기면 되는 것입니다.

여기서 문제 하나 내 볼까요?

그렇다면 최초의 원반 총 개수가 5개인 경우에는 파란색 원반을 몇번 기둥으로 옮겨야 할까요?
여기서는 그림으로 제시되고 있지 않지만 유추 해석해보면 바로 알 수 있을 것입니다.)

(7회) --> 3개 완성

 

자 이제 최초의 원반이 총 4개인 경우는 여전히 가장 큰 아래층 원반이 1번 기둥에 남아있습니다.
여기서도 1번 원칙을 적용하면 됩니다. 원반이 1개이므로 홀수, 따라서 목표 기둥으로 옮기면 됩니다. 즉, 3번 기둥이죠.(그런데 이것은 원칙이라고 거창하게 말할 필요도 없습니다. 가장 큰 원반이 갈 수 있는 기둥은 비어있는 곳밖에 없기 때문이죠.)

(8회)

 

자 이제 2번 기둥에 남아있는 3개의 하노이 탑을 목표기둥(3번 기둥)으로 옮기는 작업을 하면 됩니다. 3번 기둥에 있는 가장 큰 원반은 그 어디로도 옮길 필요가 없습니다. 가장 크기 때문에 옮길 수도 없구요. 가장 크기 때문이죠. 따라서 3번 기둥에 있는 가장 큰 원반은 지금부터 무시하면 됩니다.

제1번 원칙을 적용하여 3개의 원반으로 구성된 하노이탑을 푼다고 가정하면 3개로서 홀수이므로 목표 기둥에 가장 작은 파란색 원반을 옮겨야 합니다.

(9회)

 

이하부터는 앞에서 이미 설명한 3개의 원반으로 구성된 하노이탑을 푸는 과정과 동일합니다. 차이점이 있다면 최초의 원반이 1번에 있던 것이 2번으로 옮겨진 것뿐입니다. 아래 그림은 (2회)와 동일합니다.

(10회)

 

아래 그림은 (3회)와 동일합니다.

(11회)

 

아래 그림은 (4회)와 동일합니다.

(12회)

 

아래 그림은 (5회)와 동일합니다.

(13회)

 

아래 그림은 (6회)와 동일합니다.

(14회)

 

아래 그림은 (7회)와 동일합니다.

(15회)

 

이상과 같은 원칙 또는 규칙은 원반의 수가 아무리 증가해도 그대로 적용됩니다. 일종의 반복 작업이 이루어지는 것이죠.

나름 자세히 설명한다고 했는데 쉽게 설명이 되었는지 모르겠네요.

이상 하노이탑 퍼즐을 쉽게 푸는 정답은 마무리하고 추가 정보를 드릴게요.

아래 블로그에서는 하노이 탑 퍼즐을 직접 플레이해볼 수 있는 플래시 게임을 제공하고 있습니다. 
시간 나시면 한번 체험해 보시기 바랍니다.

하노이탑 퍼즐 체험하기 플래시 게임 --> http://flashgamerz.tistory.com/504

원반수가 작은 것부터 차근차근 풀어가다 보면 퍼즐러갱이 말한 일정한 규칙이 느껴질 것입니다.
그러다가 시간이 지나면 이제는 속도를 단축하는 목표를 세우는 것도 재미있을 것 같습니다.

(* 퍼즐러갱 위 그림들 그리느라고 눈알 빠지는 줄 알았습니다. 박수좀 쳐주세요~~^^)

 

오늘도 해피 퍼즐링~~

관련 포스트: 하노이 탑 (Tower of Hanoi) 퍼즐에 얽힌 놀라운 이야기

 

*아래 화면은 퍼즐러갱이 개설한 유튜브 '퍼즐러갱TV'의 초기화면입니다. 아래 그림을 클릭/터치하여 퍼즐러갱TV를 감상해 보시지요(구독과 좋아요는 저에게 큰 힘을 줍니다)!!