이 문제는 잘 알려진 하노이 탑 문제의 변형이다.

하노이 탑 문제는 다음과 같다. 세 개의 막대기, 즉 막대기-1, 막대기-2, 막대기-3 이 있고, 막대기1 에 크기가 다른

n개의 디스크가 내림차순으로 쌓여 있다. 즉, 가장 작은 디스크가 가장 위에, 가장 큰 디스크가 가장 아래에 놓여 있다. 문제의 목표는 막대기-1 에 쌓여 있는 모든 디스크를 막대기-3 으로 옮기는 것이다. 단, 옮기는 과정에서, 한 번에 하나의 디스크만 옮길 수 있으며, 어떤 경우에도 큰 디스크가 작은 디스크 위에 놓여서는 안 된다.

원래의 하노이 탑 문제가 아래와 같이 변형된다.

1. 동일한 크기의 디스크가 허용된다. 따라서 디스크를 이동하는 과정에서 어떤 디스크는 크기가 동일하거나 또는 더 큰 디스크 위에 놓을 수 있다.
2. 각 디스크는 빨간색(R), 녹색(G) 또는 파란색(B)의 세 가지 색상 중 하나로 칠해져 있다. 하지만, 동일한 크기의 디스크는 동일한 색상을 가진다.
3. 동일한 크기의 디스크가 둘 이상일 경우, 디스크를 옮긴 후 이들 간의 상대적 순서가 유지될 수도 있고, 반대로 될 수 있는데, 이를 디스크 색이 결정한다. 즉, 디스크 색이 빨간색이면 모든 디스크를 최종적으로 이동한 후 동일한 크기의 디스크의 상대적인 순서가 반대로 되어야 한다. 디스크의 색이 파란색이면 모든 디스크의 이동이 완료된 후의 상대적인 순서가 처음의 순서와 동일해야 한다. 그리고 색이 녹색이면 이동 후의 상대적인 순서가 중요하지 않다. 다만, 디스크를 이동시키는 중간 과정에서는 상대적인 순서에 대한 조건을 만족할 필요는 없다.
4. 디스크 이동의 총 횟수를 최소화해야 한다.

그림 C.1 은 디스크를 모두 옮긴 후, 크기가 같은 디스크의 색상에 따른 상대적 순서의 조건을 만족시키는 예를 보여준다.

그림 C.1

#9649 upload 2 done - how_to_reg -

Colorful Tower of Hanoi timer 1s memory 128MB

#9649

Colorful Tower of Hanoi 1s 128MB