하노이탑 퍼즐 추가요~~

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

이름하여 하노이탑 (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 차원공간문제)가 수학자들이 풀 수 있다고 보입니다.

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

  6. 이영재 2017.11.06 21:52 신고  댓글주소  수정/삭제  댓글쓰기

    나는 임의의 기둥 문제의 하노이탑 퍼즐, open problem을 풀었다고 생각합니다. 몇개월 후에 논문으로 발표할 생각입니다. 사실은 이 여러기둥 문제를 컴퓨터로는 어떤 한계까지(기둥10개 원반 50개)는 알고리듬을 써서 알아낼 수는 있다고 합니다. 그러나 나는 공식하나로 몇번에 한 기둥에서 목표기둥으로 탑을 이루는 원반들을 옮길 수 있는지 최소의 수를 알 수 있습니다.

    100년 이상이 된 이문제를 내가 유도해서 답을 낸 것입니다. 2개월전 지난 9월달에 이 퍼즐을 접하고 재미로 4개의 기둥을 풀어 봤지만 이것이 open problem인지 몰랐는데 여기 들어와서 알았습니다. 그래서 wikipedia에서 정확하게 알게 되었습니다. 감사합니다. 이미 알려진 테이터와 맞추어보니 잘 맞았습니다. 지금은 내가 유도하여 만든 공식을 증명하고 있습니다. 내가 유도해서 알아냈으니 유도과정은 길이 거의 보입니다. 그러나 잘 검토하겠습니다. 아무도 나를 믿어주는 사람은 없지만 증명이 끝나면 몇달안에 발표하겠습니다. 참을성 있게 말하지 않으려고 해도 이렇게 말하고 있군요.

    머지 않아 여기 주인장에게도 내 식을 보여줄 때가 있을 것입니다. 아직 보여주지 못하는 것을 미안하게 생각합니다. 관심을 갖어주어서 고맙고 유익한 정보가 저를 자극해 주어서 고맙습니다. 나는 물리학 전공자입니다.

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

      혹시 발표 과정에 어려움이 있으면 저에게 전달해 주셔도 됩니다.
      국내의 저명한 수학박사 또는 수학과 교수님께 자문을 구할 수 있습니다.
      건승을 기원합니다~~

  7. 이영재 2017.11.06 22:05 신고  댓글주소  수정/삭제  댓글쓰기

    나는 예전부터 퍼즐을 좋아했습니다. 12개의 공 중에서 무게가 다른 공 1개를 찾기위해 천칭을 3회 이용하는 퍼즐도, 풀었고, n개의 공중 다른 무게의 공 1개를 찾아내는지 몇회 천칭을 이용해야하는 문제를 만들어 풀었고, 시중에 해법이 나오기 전에 돌릴 수 있는 정육면체 퍼즐의 6면을 모두 맞추어 주위 사람들을 놀라게 했으며, 최근에는 4개의 기둥일 경우 하노이탑을 옮기는 움직임 수를 풀었는데

    임의의 N개의 기둥일 때는 정말 힘들었습니다. 주위에서 모두 부정적인 신호만 주었는데 여기 들어와 보니 주인장만은 용기를 돋구어주었네요. 그런데 일단 풀고 보니 믿거나 말거나 알리고 싶은 마음이 드는 것이 심리인가봅니다. 나는 확신을 갖는데 해답인 공식을 증명을 해야하는 일이 남아 있어서 발표할 때가 아니라고 생각합니다.

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

      긍정적으로 말씀해 주시니 고마울 따름입니다.
      이영재님 말씀 덕분에 저도 학창 시절에 천칭을 이용한 문제를 열심히 풀어보았던 기억이 새록새록 나는군요.^^

  8. 이영재 2017.11.06 22:13 신고  댓글주소  수정/삭제  댓글쓰기

    나는 하나의 식을 해답으로 얻었지만 wikipedia의 설명으로는 1941년에 두 미국인이 독립적으로 얻어낸 동일한 algorithm으로 관행적으로 계산을 했다는 것입니다. 그것을 통해 컴퓨터로 계산한다는 의미입니다. 그러나 2010년 이후에야 그 알고리듬이 맞다고 증명이 되었던 것입니다. 그러나 그 알고리듬은 해답이 아니라 푸는 방식(해법)일 뿐입니다. 그래서 하노이 다중탑문제는 open problem인 것입니다. 운이 좋게 나는 모퉁이를 돌아서 적절한 유도를 통해 하나의 식을 얻었고 그 답으로 여러가지 기존 계산결과를 맞추어 보니 비켜나간 수치가 없었습니다.

    나의 식으로는 시간이 많이 걸려 답을 얻을 수 있는 컴퓨터에 비하여 손으로도 계산 가능하고 숫자가 너무 많다면 calculator를 쓰면 더 빠르겠지요.

  9. 이영재 2017.11.18 13:47 신고  댓글주소  수정/삭제  댓글쓰기

    증명이 끝나서 논문으로 발표할 생각입니다. 지금은 초안을 작성중입니다. 수식이 많고 여기에 발표하기가 길어서 초록(abstract)만 옮겨 놓습니다.

    title: The solution to the p-post Tower of Hanoi puzzle
    Auther: Youngjae Lee
    Date: Nov. 18, 2017

    <Abstract>
    The Tower of Hanoi puzzle with three posts and it's simple solution have long been well-known since Lucas invented it in 1883. The problem is to find the least number of moves needed to transfer a Tower of Hanoi of n disks under certain rules, from an initial post to a destination post. This problem was extended to the puzzle with more than three posts in 1939 and an algorithm for the puzzle were proposed without proof by Frame and Stewart in 1941. The algorithm for p-post puzzle had been regarded as empirically optimal until it was proved in 2016, while the optimal solution to four-post puzzle has not been verified until 2014. But until now the general solution to the puzzle with more than four posts has been unknown for many decades and remains open.

    In this paper I propose a compact function of any number of posts and disks, and prove that it is the general solution to the extended Tower of Hanoi problem for finding the least number of moves of disks.

    1. Introduction
    <omitted>