하노이탑 퍼즐 추가요~~

이번 포스트에서는 지난번에 포스팅한 내용과는 다르면서도 좀더 색다른 내용을 담아볼까 합니다.

이름하여 하노이탑 (Tower of Hanoi) 다시 생각해보기 입니다.

일반적인 하노이탑 퍼즐의 규칙을 그대로 적용하면서 새로운 조건이나 상황을 부여한 것이지요.
일반적인 하노이탑 퍼즐의 규칙은 다음과 같이 2가지입니다.

1. 원반은 한 번에 한 개씩만 옮겨야 한다.
2. 언떤 경우에도 작은 원반 위에 큰 원반을 올려놓을 수 없다.

그런데 이러한 규칙이 적용되는 일반적인 하노이탑 퍼즐의 기둥 갯수는 3개이며, 원반의 크기가 모두 다르며, 어느 기둥으로든지 옮기는 원반보다 작은 원반이 있으면 원반을 옮길 수 있습니다.

이런 특징을 지닌 기존의 하노이탑을 확장시켜본 것이 변형 하노이탑입니다.

변형 하노이탑에는 다양한 종류가 있더군요.

1. 동일한 크기의 원반이 여러 개인 경우
2. 인접통행(일방통행)만 가능한 경우 
3. 기둥의 수가 4개 이상인 경우

먼저 1번에 대한 설명입니다.

기본 하노이탑 퍼즐에는 모두 크기가 다른 원반이 있었습니다만, 이 경우는 크기가 같은 원반의 갯수를 2개, 3개, 4개인 경우로 늘려갈 경우의 최소 이동 횟수에 대한 일반해를 구하는 문제(퍼즐)입니다.

도대체 무슨 말인가 헷갈리지요?
당췌 감이 안오지요?
퍼즐러갱도 그랬답니다.
그래서 친절한 퍼즐러갱이 그림을 그려보았습니다.
아래의 그림을 보면 이해다 빨리 될 것입니다.

동일한 원반이 2개이면서 크기가 다른 원반이 1인 경우

 

동일한 원반이 2개이면서 크기가 다른 원반이 2개인 경우 

 

동일한 원반이 2개이면서 크기가 다른 원반이 3개인 경우

 

동일한 원반이 2개이면서 크기가 다른 원반이 4개인 경우

 

동일한 원반이 3개이면서 크기가 다른 원반이 1개인 경우

 

동일한 원반이 3개이면서 크기가 다른 원반이 2개인 경우

 

동일한 원반이 3개이면서 크기가 다른 원반이 3개인 경우

 

동일한 원반이 3개이면서 크기가 다른 원반이 4개인 경우

 

동일한 원반이 4개이면서 크기가 다른 원반이 1개인 경우

 

동일한 원반이 4개이면서 크기가 다른 원반이 2개인 경우

 

동일한 원반이 4개이면서 크기가 다른 원반이 3개인 경우

 

동일한 원반이 4개이면서 크기가 다른 원반이 4개인 경우

 

위 그림을 보면 동일한 크기의 원반이 m개이고 크기가 다른 원반이 n개인 경우 총 원반의 수는 m*n 개임을 알 수 있습니다.

물론 크기가 같은 원판 위에 동일한 크기의 원판을 올릴 수 있겠지요(언떤 경우에도 작은 원판 위에 큰 원판을 올려놓을 수 없다는 하노이탑의 기본 규칙인 2번 규칙을 어기는 경우에 해당하지 않는다는 말씀)

다음으로 2번에 대한 설명입니다.

기본 하노이탑 퍼즐에서는 어느 기둥으로든지 자유롭게 원반을 이동시킬 수 있었습니다만, 이 경우는 바로 인접한 기둥으로만 원반을 이동시키는 조건이 부여된 것입니다. 이렇게 하면서 목표 기둥까지 모든 원반을 옮기는 것에 대한 최소 이동 횟수를 구하는 문제(퍼즐)입니다.

즉 아래 그림에서 볼 수 있듯이 1번 기둥에 있는 원반은 1번 기둥과 인접해 있는 2번 기둥으로만 이동이 가능합니다.
2번 기둥에 있는 원반은 2번 기둥과 인접해 있는 1번과 3번 기둥으로 이동이 가능합니다.
3번 기둥에 있는 원반은 3번 기둥과 인접해 있는 2번 기둥으로만 이동이 가능합니다.

 

 

오리지날 하노이탑 퍼즐에 비해서 추가된 조건이 있기 때문에 좀더 어렵다고 할 수 있겠습니다.
그리고 결과적으로 목표 기둥으로의 최소 이동횟수도 자연스럽게 커지게 됩니다.

다음으로 3번에 대한 설명입니다.

기본 하노이탑 퍼즐에서는 기둥이 3개였지만, 이 경우는 기둥이 4개 이상입니다.

기둥이 4개이면서 원반의 수가 4개인 경우

 

기둥이 5개이면서 원반의 수가 4개인 경우

 

위에서는 원반의 갯수를 모두 4개로만 되어 있는 것을 보여드렸지만 원반의 수를 더 적게 할 수도 있고, 더 많게 할 수도 있습니다.

이 변형 하노이탑 퍼즐은 기둥이 3개일 때보다 원반을 옮길 곳이 많아서(자유도가 높아서) 상대적으로 쉬워 보입니다.
그리고 최소 이동 횟수도 기둥이 3개인 경우보다 실제로 적습니다.

그러나 재미난 것 중의 하나는 현재 3번 변형 하노이탑 퍼즐인 '기둥의 수가 4개 이상인 경우에 대한 일반해'는 아직까지 발견되지 않은 상태라고 합니다(Open Problem).
그 일반해를 컴퓨터를 이용해서 풀든, 똑똑한 머리로 풀어내든, 단순 반복작업을 통한 노가다로 풀어보든,
아무튼 풀어내기만 하면 아마 노벨상 감일 것 같습니다.^^

오늘은 그저 이런 종류의 변형 하노이탑이 있다는 것만 제시하고 나중에 시간나면 1번과 2번 변형 하노이탑 퍼즐에 대한 답을 정리해서 제시해 보도록 하겠습니다.

퍼즐러갱이 해답을 알려드리기 전에 지적 호기심이 충만한 분들은 스스로 한번 도전해 보시기 바랍니다.

3번의 변형 하노이탑 퍼즐에 대해서는 퍼즐러갱 나중에 은퇴하고 나서 시간나면 한번 도전해 볼 생각입니다.
그런데 퍼즐러갱이 풀어내기 전에 일반해를 다른 사람이 먼저 풀어내면 어떡하죠?

별 걱정을 다하고 사는 퍼즐러갱입니다요~~^^

오늘도 해피 퍼즐링~~

참고 포스트:
1. 하노이 탑 (Tower of Hanoi) 퍼즐에 얽힌 놀라운 이야기
2. 하노이탑 퍼즐을 쉽게 푸는 해법

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

댓글을 달아 주세요

  1. 이영재 2017.09.20 07:59 신고  댓글주소  수정/삭제  댓글쓰기

    하노이탑퍼즐 4개의 기둥에 대한 일반해를 제가 풀었다고 생각합니다. 이것이 정말 open problem이라고요?

    • 퍼즐러 갱 2017.09.21 12:18 신고  댓글주소  수정/삭제

      퍼즐러갱의 퍼즐박물관 블로그에 관심가져 주셔서 고맙습니다.
      말씀하신 4개의 기둥을 가진 하노이 탑(The Tower of Hanoi with 4 Legs) 문제의 일반해를 이영재님이 풀었다는 말씀이 무슨 말인지 잘 모르겠습니다.
      세계적으로 권위를 인정받고 있는 위키피디어에서도 현재 Frame–Stewart algorithm을 일반해로 추정하고 있다고 하고 있습니다. 2014년에 Bousch가 Frame–Stewart algorithm을 증명했다고는 하지만 널리 일반적으로 인정되고 있지는 않은 상태인 것으로 알고 있습니다 (여전히 '주장'하고 있다는 표현을 쓰고 있지요).
      이영재님께서 풀어냈다는 일반해를 국내 수학 전문가(예를 들면 대학교수)에게 먼저 보내보시면 어떨까요? 세계적으로 엄청 주목받게 될 것이라 확신합니다.

  2. 이영재 2017.09.21 21:11 신고  댓글주소  수정/삭제  댓글쓰기

    기둥이 4개이며 크기가 다른 원반의 수는 n개일 때에 대한 해법은 조금은 복잡하지만 명백히 풀 수는 있습니다. 저와 같이 평범한 사람에게도 그다지 어려운 문제는 아닌 것으로 보면 기둥4개의 문제는 open problem이 아닌듯 해서 글을 올린 것입니다.

    물론 기둥이 5개에 대해서는 아직 시도는 하지 못했습니다. 이 기둥 5개 문제가 open one일지도 모르겠네요.

  3. 이영재 2017.09.21 21:20 신고  댓글주소  수정/삭제  댓글쓰기

    소규모의 과학자들의 세미나 그룹에 그 1~2페이지 정도의 해법을 재미삼아 서면으로 발표했습니다. 모두들 꼼꼼이 검토했고 이의가 없었고 인정했습니다. 그런데 재미삼아 풀었던 그 해가 open problem의 해라면 발표하기가 좀 꺼려집니다. 그정도로 어려운 해법은 아닌데요. 반복법으로 하면 고등학교 수학보다는 좀 더 어렵고 학부정도 학생들도 이해할만 하던데요.

    • 퍼즐러 갱 2017.09.22 09:41 신고  댓글주소  수정/삭제

      저는 수학자가 아니어서 잘 모르겠습니다만 소규모의 과학자 그룹에서 이의가 없었다고 하면 상당히 의미있는 해법일 것 같습니다.
      혹시 그 내용을 저 퍼즐러갱(puzzlergang@gmail.com)에게 보내주실 수 있는지요?
      수학박사 또는 수학교수에게 자문을 구해보도록 할게요. 너무 부담 갖지 마시고요.^^

  4. 이영재 2017.09.22 22:41 신고  댓글주소  수정/삭제  댓글쓰기

    wikiepedia 사전에 들어가보니 다음과 같은 글이 있었습니다:

    The optimal solution for the tower of Hanoi problem with four peg has not been verified until 2014, in the case of more than four pegs the optimal solution is still an open problem, even if a proof that the Frame-Steward algorithm is optimal was proposed by Denontis in 2016.
    4 기둥의 하노이 타워문제에 대한 최적해는 2014년까지 입증되지 못했다. (2016년 Denontis라고 하는 사람이 Frame-steward 알고리듬이 최적이라고 증명을 제안하였지만) 4기둥보다 많을 경우 최적 해는 아직도 open problem이다.

    5기둥 이상에서 최적해라고 증명이 되었는데 open problem이라는 말은 이해하기는 쉽지 않네요!

    • 퍼즐러 갱 2017.09.25 09:06 신고  댓글주소  수정/삭제

      이영재님이 올린 영어원문을 제가 이미 해석해서 이영재님의 처음 댓글에 댓글로 달았습니다. 해법을 보내주시면 제가 수학 교수님께 의뢰해 보겠습니다~~

  5. 이영재 2017.09.30 09:05 신고  댓글주소  수정/삭제  댓글쓰기

    N개의 기둥이 있을 때 n개의 서로 다른 원반의 경우를 풀어볼 생각입니다.

    생각해보니 3개의 기둥의 문제는 0 차원 문제로 대학생을 정도면 풀수 있고, 4기둥의 문제(1차원
    문제) 는 대학원학생 수준에 해당되며 5기둥(2차원 공간문제) 이상 또는 N개 기둥 문제(N-3 차원공간문제)가 수학자들이 풀 수 있다고 보입니다.

    비수학자가 한번 도전해 봐야할 듯. 아는 수학자와 동업해야할지도 모르겠네요. 성공하면 알려드리겠습니다!