본문 바로가기

퍼즐 종류

변형 하노이탑 퍼즐: 하노이탑 퍼즐 다시 생각해 보기

하노이탑 퍼즐 추가요~~

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

이름하여 하노이탑 (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. 하노이탑 퍼즐을 쉽게 푸는 해법




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