하노이 탑 (Tower of Hanoi) 퍼즐은 아래와 같이 생겼습니다.
아주 심플한 퍼즐입니다.

위 사진에서 알 수 있듯이 일정한 판 위에 3개의 막대가 고정되어 있습니다. 지름이 약간씩 다른 원반이 여러개 있고 그 중심에 구멍이 뚫려 있어 작은 지름의 원반이 위에 오도록 하여 맨 왼쪽의 막대에 원반들이 꽂혀 있습니다.
이 퍼즐의 미션은 모든 원반을 다른 막대로 옮기는 것입니다.
여러 사람이 할 경우에는 최소의 이동 횟수를 기록한 사람이 이기는 것이겠죠.
단 규칙이 있습니다.

① 1회에 한 개의 원반밖에 이동할 수 없다.
② 이동은 막대에서 막대로 이루어진다.
③ 작은 원반 위에 큰 원반을 올려놓을 수 없다.

그런데 이 퍼즐에는 다음과 같은 전설이 있다고 합니다.
옛날옛적 인도 카시 비슈와나스 (Kashi Vihswanath)에 있는 브라만교 대사원에 하노이 탑이 있었습니다.
이 하노이 탑은 세 개의 다이아몬드 기둥이 있는데,
신(Brahma) 이 이 세상을 창조할 때 64개의 순금 원판을 이 기둥 중 하나에 쌓아 놓았다고 합니다.
이 원판들은 크기가 큰 것이 아래에 놓이고 작은 것이 위에 놓이도록 차례로 쌓여 있는데
신은 브라만 승려들에게 두가지 원칙을 제시하며 승려들에게 원판을 옮기라고 합니다.
첫째, 원판은 한번에 한개씩만 옮겨야 한다.
둘째, 작은 원판 위에 큰 원판을 올려놓을 수 없다.
이렇게 해서 64개의 원판이 모두 다른 기둥으로 옮겨졌을 때, 이 세상의 종말이 오게 된다고 했다고 합니다.
전설속의 승려는 지금 이순간에도 원판을 룰에 의해 하나씩 하나씩 옮기고 있는 중이구요.

이 전설에 의하면 지구의 종말은 언제쯤 가능할까요?
왠지 모르게 가까운 시일 내에 원판을 다 옮겨서 세상이 멸망할 것 같은 불길한 느낌이 엄습합니다.

그러나 이 전설이 설사 맞다 할 지라도 걱정 붙들어 매도 됩니다.
왜냐하면 64개의 원판을 다른 다이아몬드 기둥으로 옮기기 위해서는 엄청난 세월이 소요되기 때문입니다.

이게 무슨 말인지에 대해서 좀더 자세히 살펴보겠습니다.

이 하노이의 탑 퍼즐의 해법 관련해서는 이미 수학적으로 증명이 되어 있습니다.
예전에 'http://puzzlemuseum.tistory.com/206' 코너에서 간단히 언급했던 누진 이진법 원리입니다.
쉽게 말해서 거듭제곱의 위력입니다. 

 원반 수

 최소 이동 횟수

최소 이동 횟수 산식 

 1

 1

21−1

 2

 3

22−1

 3

 7

23−1

 4

 15

24−1

 5

 31

25−1

 6

 63

26−1

 7

 127

27−1

 8

 255

28−1

 ...

 ...

2원반수−1

위 표의 맨 아래 행에 표시했지만 하노이 탑 퍼즐의 최소 이동 횟수는 (2원반수−1) 입니다. 
굳이 이 산식이 아니더라도 원반의 수가 하나씩 늘어남에 따라 거의 두배씩 최소이동횟수가 증가함을 알 수 있습니다. 즉, 원반 수가 증가함에 따라 최소 이동 횟수는 기하급수적으로 급격히 증가한다는 것입니다.

만일 원반의 수가 64개라고 하면 최소 이동 횟수는 264−1 회이며,
1회의 이동에 1초가 걸린다고 가정하면 최소 이동 횟수는 264−1 초로서,
이것을 아라비아 숫자로 표현해 보면 18,446,744,073,709,551,615 초에 해당하며,
이를 연으로 환산하면 5,850억년에 해당하는 수치입니다.
이 수치는 현재 과학적으로 추정하고 있는 태양의 잔여 수명보다도 더 긴 기간이라고 합니다.
실제로 원반을 다 옮기는 때가 오면 이미 이 세상은 종말이 온 것이겠죠.

결과적으로 위의 인도 전설에 나오는 세상의 종말 이야기에 대해서 전혀 걱정할 필요가 없습니다.

이와 유사한 이야기가 하나 더 있습니다.
옛날 인도에 어떤 왕이 있었는데 전쟁을 너무 좋아해서 백성들이 항상 불안에 떨고 있었습니다.
이런 현상을 본 세타라는 승려가 전쟁과 비슷한 규칙을 지닌 체스 게임을 만들어 냈습니다.
서양식 장기인 체스는 가로와 세로 각각 8칸씩 총 64칸으로 이루어진 정사각형의 판 위에 여러 종류의 말을 놓고, 일정한 규칙에 따라 말을 움직이는 게임입니다.
얼마나 많은 말을 보유하고 있는가도 중요하지만,
정작 승패를 판가름하는 것은 어떻게 전략을 짜느냐 하는 것이죠.
다행히 왕은 체스 게임에 흥미를 느껴 전쟁이 아니라 체스로 관심을 돌리게 되었습니다.
왕은 체스 게임을 소개해 준 세타에게 고마움을 표시하기 위해 무엇이든 원하는 것을 말해보라고 합니다.
그러자 세타는 체스판의 첫 칸에 밀 한 알, 둘째 칸에 밀 두 알, 셋째 칸에 밀 네 알과 같이 두배씩 밀알을 늘려 채워달라고 요구합니다.
왕은 세타가 참으로 소박한 승려라고 생각했습니다.
그....러....나,
실제로 체스판을 세타가 말한 방식대로 채우기 위해서 필요한 밀알은 의외로 엄청난 양이었습니다.
즉, 1 + 2 + 4 + 8 + 16 + 32 + ...... + 262 + 263 개,
위의 숫자를 모두 더하면 결국 264−1 개의 밀알이 됩니다.
왕은 결국 이 숫자의 밀알을 줄 수가 없게 된 것입니다.
왕의 섣부른 오판, 그리고 세타 승려의 현명함이 돋보이는 대목입니다.

또 이와 유사한 원리로서 신문지 종이를 몇회 접어야 달까지 갈 수 있을까 하는 문제가 있습니다.
즉, 신문지 종이를 반으로 접고, 반으로 접은 것을 다시 다시 반으로 접고 해서 이런 과정을 계속 반복했을 때 과연 몇회만에 지구에서 달까지 도착할 수 있는지의 문제입니다.
상당히 큰 횟수를 생각했겠지만 실상은 42번만 접으면 지구에서 달 표면까지 도착하고도 남아서 56,805km를 더 간답니다.
그리고 43번 접으면 달 표면까지 갔다 다시 지구로 돌아오고도 (왕복하고도) 113,609km가 남게 됩니다.
(여기서의 가정은 신문 종이의 두께가 0.1mm 이고, 달까지의 거리는 383,000km라는 것입니다.) 

이러한 현상이 발생하는 것 모두 누적 이진법 즉 거듭제곱의 힘입니다.
기하급수적으로 늘어나는 숫자는 그 횟수가 커질 수록 엄청난 위력을 발휘하는 것이죠.
0.1mm * 242 = 439,805km
0.1mm * 243 = 879,609km

그리고 하노이 탑 (Tower of Hanoi) 퍼즐은 브라마의 탑 (Tower of Brahma) 또는 루카스 타워 (Lucas' Tower) 또는 파나마 콘 퍼즐 또는 파나마 디스크 퍼즐 (Panama Cone or Disc Puzzle) 이라고도 불린답니다.
브라마 탑이라고 불리는 이유는 힌두교 최고의 신인 브라마가 이 퍼즐을 만들었다고 해서 주어진 이름이구요.
루카스 타워라고 불리는 이유는 프랑스 수학자인 Edouard Lucas 의 책에 의해 1883년에 서양에서 처음으로 대중에 알려졌기 때문입니다. 위에서 언급한 인도의 전설 속의 세상의 종말 관련한 이야기는 루카스가 한 말입니다. 이 전설을 루카스가 지어낸 것인지, 아니면 실제로 전설이 있고 그 전설에 영향을 받아서 이야기한 것인지는 현재 불분명합니다. 
파나마 콘 퍼즐 또는 파나마 디스크 퍼즐이라고 불리는 이유는 예전에 이 이름으로 아래와 같은 퍼즐이 판매되었기 때문입니다. 

 

그런데 이 하노이 탑 퍼즐을 즐기려면 반드시 퍼즐을 구입해야만 하는 것일까요?
아닙니다.
요즘 인터넷의 발달로 인해 인터넷 상에서 하노이 탑 퍼즐을 가상 체험해 볼 수 있는 프로그램이 많이 있답니다.
http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm 사이트를 방문해 보시면 하노이 탑 퍼즐을 체험할 수 있는 프로그램을 제공하고 있습니다.
원반을 드래그 앤 드랍하면서 손쉽게 즐길 수 있습니다.
관심 있으신 분들은 한번 방문해 보시지요.

마지막으로 하노이 탑 퍼즐에 대한 각종 이미지를 보여드리겠습니다. 나름 재미있는 구석이 있더군요.

위 퍼즐은 하노이 탑 퍼즐을 나무 상자 안에 정리할 수 있도록 고안된 퍼즐입니다.
퍼즐러 갱이 가지고 있는 것도 이와 유사한 것입니다.

위 퍼즐은 일반적 하노이 탑 퍼즐과는 달리 가운데 있는 나무 기둥을 뱀 모양으로 만들었다는 것이 특징이군요.
그리고 가장 넓은 원반 끝부분을 뱀의 꼬리처럼 처리함으로써 결국,
뱀이 또아리를 틀고 있는 모습으로 만들었다는 것이 참 기발한 아이디어입니다.

 

위 퍼즐은 직사각형의 바닥 대신에 삼각형 모양의 바닥을 가지고 있는 하노이 탑 퍼즐입니다. 가운데의 것은 나름 부드러운 곡선미를 자랑하는군요.

 

위 사진은 하노이 탑이라는 퍼즐 이름에 걸맞게 단순한 원반 대신 탑 형식을 취한 것입니다.
상당히 멋드러진 하노이 탑 퍼즐인 것 같습니다.
진짜 탑 모양을 하고 있는 위의 퍼즐을 꼭 손에 쥐고 싶은 생각이 굴뚝 같습니다.

마지막으로 하노이 탑 퍼즐은 기계적 퍼즐 분류에 의하면 순차이동 퍼즐 (Sequential Movement Puzzle) 에 해당합니다~~

오늘도 해피 퍼즐링~~

- 참고 사이트:
http://cmath_club.blog.me/30138769398
- 관련 포스트:
http://puzzlemuseum.tistory.com/206
http://puzzlemuseum.tistory.com/141
http://puzzlemuseum.tistory.com/180

 

 

저작자 표시 비영리 변경 금지
신고
Posted by 퍼즐러 갱

댓글을 달아 주세요

  1. Puzzler PAM 2012.11.05 19:01 신고  댓글주소  수정/삭제  댓글쓰기

    하노이의 탑... 솔직히 맨 첨에 무시했었습니다.
    옮기는 방법 무쟈게 간단해요. 맨 위, 가장 작은것을 옮기는 것으로 부터 시작됩니다. 이 때, 홀수개면 옮긴 위치에, 짝수개면 옮긴 위치와 원래 위치가 아닌 세번째 위치에 전체가 옮겨지게 됩니다.
    세 개의 막대를 1,2,3이라 하고 맨 위의 것이 1에서 2로 옮겨졌다고 한다면 홀수번째에 1에서 2로, 2에서 3으로, 3에서 1로...를 반복하면 됩니다.
    짝수번째에서는 가장 작은 원반이 있지 않은 두 개의 막대 a,b 중에서 하나의 막대에서 하나로 옮기면 됩니다.
    (움직일 수 있는 것은 하나밖에 없습니다.)
    그렇게 움직이면... 1,2,3순서를 시계순이라 하고, 1,3,2 순서를 반시계라 하면
    맨 위는 시계로 움직이면, 그 아래는 반시계, 그 아래는 시계, 그 아래는 반시계...로 움직임을 알 수 있습니다.
    또한, 1,3,5,7...등 홀수에는 맨 위의 것, 2,6,10...에는 두번째 것이 움직입니다.
    n번째는 n을 이진수로 나눴을 때 가장 오른쪽에 있는 1(옆으로 k-1개의 0이 있다.)이 있으면, k번째 원반을 움직이는 것입니다.

    • 퍼즐러 갱 2012.11.06 08:56 신고  댓글주소  수정/삭제

      사실 원리만 이해하면 무쟈게 단순하긴 하지요.^^

    • Puzzler PAM 2012.11.06 19:14 신고  댓글주소  수정/삭제

      그러나... (시간상 지금 올리게 되네요;;)
      앞부분에 '맨 처음'에 무시했다고 했었죠. 그러나... 실질적으로 무시할 만 한 건 안되더라구요. 확장하면...무시무시해집니다.
      막대기 수 3개->4개...
      1,2,3 막대가 일열로 늘어서서 1에서 3으로 혹은 3에서 1로 바로 못가고 2를 거쳐갈 때 옮기는 횟수...
      1,2번 막대에 홀수번째 큰 원반과 짝수번째 큰 원반이 각각 있을 때 3번 막대에 그것을 모두 정렬하는데 걸리는 횟수 등...
      세번째는 아직도 정확한 해법을 모릅니다.;;
      무시할게 못되요... 이것보다 훨씬 복잡해지던데;;

    • 퍼즐러 갱 2012.11.06 20:02 신고  댓글주소  수정/삭제

      와우!!!!
      엄청난 내공이 팍팍!!

  2. 지치뽕 2012.11.06 09:20 신고  댓글주소  수정/삭제  댓글쓰기

    이거 우리집에도 있는데 원반 수는 4개나 5개 정도가 적당하더군요.
    3개는 약간 쉽고,
    6개는 너무 오래 걸리고 어렵고,
    4개 5개가 가지고 놀기에는 딱이더군요.

    아 그리고 원반수에 따라 해법 수가 일정한 원리가 적용된다는 것을 여기서 처음 알게 되어 기쁩니다.

  3. 송승현 2012.12.19 20:17 신고  댓글주소  수정/삭제  댓글쓰기

    좀 퍼갈께요^^

  4. 백윤하 2015.04.21 18:52 신고  댓글주소  수정/삭제  댓글쓰기

    사진만 퍼갈게요