최근 수정 시각 : 2024-03-21 03:57:20

하노이의 탑

1. 개요

파일:external/437a6637b1f6834a74146f6e51b7360fa64116c23c3c0c7fd5462db9a8a73ab4.jpg

3개의 기둥에 적당한 개수의 원반을 쌓아 놓고 다른 쪽으로 옮기는 게임.

원반 개수가 늘어날수록 이동 횟수가 엄청나게 늘어나기 때문에 많아야 7, 8개 정도만 쓰며 소모 시간으로 승부를 짓는 것이 보통인데, 이 정도면 1초에 원반 하나를 옮긴다 가정할 때 2~4분 정도 걸린다.

1883년 프랑스의 수학자 에두아르드 뤼카(Lucas,E. : 1842~1891)가 처음으로 발표한 게임이다. 이후 여러 사람을 거치면서 상세 문단의 전설이 덧붙여졌다.

2. 상세

고대 인도 베나레스에 있는 한 사원의 이야기
여기에는 다이아몬드로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 64개의 크기가 각각 다른 황금 원반이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한 번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다.
이 규칙으로 64개의 원반을 처음 놓여 있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 세상의 종말이 온다고 한다.
이 가짜 전설 덕분에 인도에 있는 베나레스[1]가 베트남의 하노이와 같은 곳인 줄 아는 사람들이 꽤 많은 듯하다.

이 규칙들을 이용하여 64개의 원반을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가 [math( 2^n - 1 )]번이기 때문이다.

[math(n+1)]번째 원반을 목표로 하는 비어있는 한 기둥으로 옮기려면, 우선 그 위의 1번부터 [math(n)]번째까지의 원반을 목표로 하는 기둥 이외의 비어있는 기둥으로 옮겨야만 한다. 이 사실을 이용해서 다음과 같이 1번부터 [math(n+1)]번째까지의 원반을 목표로 하는 기둥으로 옮기는 데 요구되는 원반이동 횟수를 계산할 수 있다.

1부터 [math( n )]번째까지의 원반을 빈 한 기둥으로 옮기는 데 필요한 최소 횟수를 [math( a_n )]라고 하자. 1번부터 [math( (n+1) )]번째까지의 원반을 목표로 하는 빈 기둥으로 옮기려면 (즉 [math( a_{n+1} )]을 구하려면) [math( n )]번째까지의 원반을 목표로 하지 않는, 빈 다른 기둥으로 옮기고 (즉 [math( a_n )] 횟수만큼 옮기고) [math( (n+1) )]번째 원반을 목표로 하는 빈 기둥으로 옮긴 후 (즉 [math( 1 )]을 더한 후) [math( n )]번째까지의 원반을 목표 기둥에 꽂혀 있는 [math( (n+1) )]번째 원반 위로 옮기면 (즉 [math( a_n )]를 다시 더하면) 된다.

따라서 [math( a_1 = 1, a_{n+1}=2a_n+1 )]이고 이 점화식 (Recursive relation)에 의한 수열 [math( a_n )]의 일반항을 구해보면 [math( a_n=2^n - 1 )]가 나온다.[2]

따라서 64개의 원반을 완전히 옮기는 데 걸리는 횟수는 [math( 2^{64} - 1 )], 자그마치 1844경 6744조 737억 955만 1615회에 달한다. 판을 한 번 옮기는 데 1초가 걸린다 해도 약 5849억년이 걸리는데[3], 이는 우주의 나이인 130~135억년보다도 훨씬 길며 중소형 적색왜성의 예상 수명과 맞먹는 시간이다. 세계멸망이 오고도 남을 만큼 길다

하지만 만약 막대를 하나 더 추가해서 네 개로 만든다면 최소 18,433번만 옮기면 되는데, 1초에 판을 1개 옮긴다 할 때 5시간 7분 13초면 된다. 여전히 오래 걸린다.[4]

3. 프로그래밍




프로그래밍 공부를 하는 사람들의 초반의 벽이 이것의 알고리즘을 구현하는 것. 보통 재귀함수에 대해 공부할 때 예제로 쓰기 좋아 한번쯤은 보고 넘어가는 문제이다. 다음은 다양한 프로그래밍 언어로의 예제 구현이다.

n번째 링을 세번째 기둥으로 옮기기 위해선 1부터 n-1까지의 링을 모두 세번째 기둥이 아닌 다른 기둥으로 옮겨야 한다. 그렇다면 1부터 n-1까지의 링을 어떻게 두번째 기둥으로 옮길까? 당연히 1부터 n-2까지의 링을 모두 두번째 링이 아닌 다른 기둥으로 옮겨두는 것이다.

이처럼 큰 문제를 해결하기 위해 작은 문제를 계속 호출하는 것이 하노이의 탑 재귀 구현의 핵심이라고 보면 된다.

재귀를 사용하지 않는 경우의 알고리즘은 다음과 같다. 원반의 총 개수를 [math(n)]이라 할 때 원반의 이동 회수는 위에서 언급한 대로 [math(2^n-1)]번이 되며, 각 회차를 [math(x)]라 할 때(1부터 [math(2^n-1)]까지) [math(x)]를 2진수로 표현하여 1이 들어가는 최저 자리수에 해당하는 원반을 왼쪽 또는 오른쪽으로 움직이면 된다. 3회차때는 11이므로 맨위의 1번 원반이, 16회차때는 1000의 4번 원반이 이동한다.

예를 들어 원반이 3개라면 1, 2, 3, 4, 5, 6, 7회차에 1번, 2번, 1번, 3번, 1번, 2번, 1번 이동하면 완성된다. 이 때 위에서부터 홀수번째의 원반이 왼쪽으로 이동(시프트, 더이상 왼쪽에 막대가 없다면 맨 오른쪽으로 이동)하면 짝수번째는 오른쪽으로 이동(마찬가지로 오른쪽 끝에서 오른쪽으로 가야 할 경우 왼쪽 끝으로 이동)하면 실수 없이 최소한으로만 움직일 수 있다. 이때 맨 위의 원반이 왼쪽과 오른쪽 가운데 어느 쪽으로 시프트하느냐에 따라 탑이 어느 막대로 움직이는가가 달라진다. 맨 위의 그림처럼 왼쪽 막대의 4개의 원반에 첫 원반이 오른쪽으로 간다면 마지막엔 오른쪽 막대에 정렬되며, 첫 원반이 왼쪽으로 가면 중앙 막대에 정렬된다.

퍼즐을 풀 때, 원반의 개수가 짝수라면 첫째 원반을 이동시킬 막대와는 다른 막대로 이동시켜야 한다. 홀수는 반대.

3.1. OCaml

<syntaxhighlight lang="ocaml">
let rec move_tower n a b c = match n with
| 1 -> [(a,c)]
| _ -> (move_tower (n-1) a c b) @ (move_tower 1 a b c) @ (move_tower (n-1) b a c);;
</syntaxhighlight>

3.2. Lisp

<syntaxhighlight lang="lisp">
(defun hanoitowers (disc src aux dst)
(cond ((> disc 0)
(hanoitowers (- disc 1) src dst aux)
(princ (list "Move" disc "from" src "to" dst))
(hanoitowers (- disc 1) aux src dst))))
</syntaxhighlight>

3.3. Pascal


#!syntax Pascal
procedure Hanoi(n: integer; from, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', from, ' to ', dest)
    else begin
        Hanoi(n-1, from, by, dest);
        Hanoi(1, from, dest, by);
        Hanoi(n-1, by, dest, from);
    end;
End;

3.4. C


#!syntax c
#include <stdio.h>

void HanoiTower(int numOfDisks, char from, char by, char to) {
	if (numOfDisks == 1) {
		printf("원판 1을 %c 에서 %c 로 이동\n", from, to);
	}
	else {
		HanoiTower(numOfDisks - 1, from, to, by);
		printf("원판 %d을(를) %c 에서 %c로 이동", numOfDisks, from, to);
		HanoiTower(numOfDisks - 1, by, from, to);
	}
}

int main() {
	HanoiTower(3, 'A', 'B', 'C');
}

3.5. C++


#!syntax cpp
#include <iostream>
using namespace std;

void move(int from, int to)
{
    cout << from << " -> " << to << '\n';
}

void hanoi(int n, int from, int by, int to)
{
    if(n == 0) return;
    hanoi(n - 1, from, to, by);
    move(from, to);
    hanoi(n - 1, by, from, to);
}

3.6. 파이썬


#!syntax python
def hanoi(number_of_disks_to_move, from_, to_, via_):
    if number_of_disks_to_move == 1:
        print(from_, "->", to_)
    else:
        hanoi(number_of_disks_to_move-1, from_, via_, to_)
        print(from_, "->", to_)
        hanoi(number_of_disks_to_move-1, via_, to_, from_)

3.7. Visual Prolog

<syntaxhighlight lang="visualprolog">
class hanoi
predicates
hanoi : (unsigned N).
end class hanoi

implement hanoi
domains
pole = string.
clauses
hanoi(N) :- move(N, "left", "centre", "right").
class predicates
move : (unsigned N, pole A, pole B, pole C).
clauses
move(0, _, _, _) :- !.
move(N, A, B, C) :-
move(N-1, A, C, B),
stdio::writef("move a disc from % pole to the % pole\n", A, C),
move(N-1, B, A, C).
end implement hanoi

goal
console::init(),
hanoi::hanoi(4).
</syntaxhighlight>

3.8. Swift

<syntaxhighlight lang="swift">
import Foundation

func hanoi(_ n: Int, from a: Int, to b: Int, by c: Int) {
if n==1 {
print("Move 1 from \(a) to \(b)")
}
else {
hanoi(n-1, from: a, to: b, by: c)
print("Move \(n) from\(a) to\(b)")
hanoi(n-1, from: c, to: b, by: a)
}
}
</syntaxhighlight>

<br />

3.9. HTML & JavaScript

4. 기타

혹성탈출: 진화의 시작 초반부에서 주인공 시저의 어미 밝은 눈이 이걸 지능 테스트용으로 하는데, 무척 빨리 완성하는 모습을 볼 수 있다.

키란디아의 전설 2편 마지막에도 이 게임을 응용한 퍼즐이 등장한다.

김정훈이 출연한 일본 수학퀴즈 프로그램에서는 하노이의 탑을 변형한 문제를 냈는데, 왼쪽, 오른쪽에 있는 5개의 원반을 가운데로 모두 옮기는 데 최소 몇 번 움직여야 하느냐하는 문제. 답은 96번. 그 외에도 많은 변형이 고안되어 있다.

매스 이펙트에서도 퍼즐로 등장한다.

레이튼 시리즈에서는 단골로 나오는 문제 유형이다.

유희왕 VRAINS의 악역 조직 하노이의 기사는 여기에서 이름을 따왔는데, 3화의 수업장면에서 이 퍼즐을 설명하는 것으로 나왔다. 또한 29화에서 리볼버(유희왕)의 독백으로 다시 언급되며, 작중에서는 방대한 양의 데이터를 원반으로 흡수한 뒤 이를 단번에 출력해 네트워크 전체를 파괴하는 EMP 병기로 등장했다. 이후 2기에서는 무기 대신 스캔 프로그램을 설치하여 라이트닝의 은신처인 미러 링크 브레인즈 서버를 찾아낸다.

대항해시대 3에 나오는 미니게임 중 하나로 등장한다.

스텔라리스의 수호자들 중 수수께끼의 요새 이벤트를 시작할 시 볼 수 있는 퍼즐이다. "기둥 세 개가 있고 그 중 하나에는 고리 세 개가 크기 순서대로 쌓여있습니다." 정답은 "다른 기둥에 고리들을 재배열한다"로, 상술한 퍼즐의 규칙과 일치한다.

원신의 파루잔 캐릭터 초대 이벤트에서 등장. 아이들에게 장치학에 대해 조기 교육을 시킬 수 있는 목적의 장난감을 개발하는 합동 프로젝트에 참여했는데 고고학자이자 언어학자인 파루잔은 고대 유적에서 보았던 기믹을 재구현하기로 한다. 그 기믹 중 하나인 하노이의 탑을 종이를 잘라서 보여주었는데 아이들이 즐겁게 플레이하게 된다. 중간에 파루잔이 주인공에게 규칙을 찾았는지 물어보면서 7개의 원반을 옮기는 데 최소 몇 번 움직여야 하는지도 물어보는데 정답은 상세 문단에 나와 있듯이 [math( 2^7 - 1 = 127)]번. 이것과 관련하여 '장치학: 입문부터…?'라는 업적도 존재한다.

물론 실제 하노이에 위치한 타워와는 관련이 없다.
[1] 현재 이름은 바라나시. [2] 이 수열의 일반항을 구하는 방법은 다음과 같다.
관계식 [math( a_{n+1} = 2 a_n + 1)]을 [math( a_{n+1}+1 = 2(a_n+1) )]로 변형하고, [math( b_n=a_n+1 )]이라고 두면 [math( b_{n+1} = 2b_n )]이 되므로 [math( b_n )]는 첫째항이 [math( b_1 = a_1 + 1 = 2 (\because a_1=1))]이고 공비가 [math( 2 )]인 등비수열이 된다. 따라서 [math( b_n = a_n + 1 = 2^{n} )] 이므로 [math( \therefore a_n = 2^{n} - 1 )]이다. [3] 이 시간은 64비트 정수형으로 시간을 표기하는 시스템이 한계에 도달하는 데에 필요한 시간과도 같다. 자세한 내용은 2038년 문제 문서로. [4] 사실 기둥이 4개인 하노이 탑 관련 문제는 정말 골 때리는 문제인데, 최소이동경로를 확정할 수가 없기 때문이다. 이유는? 간단하다. 원반이 3개라고 가정하고 첫 번째 원반을 1기둥 -> 4기둥으로 옮긴다고 가정한다.(아무데나 상관이 없다) 그러면 2번째 기둥은? 2번 기둥이나 3번 기둥으로 옮길 수 있게 된다. 즉, 최소 횟수를 위한 이동경로가 한 개가 아니다. 그러면 내가 최소이동횟수를 구해도 "이게 정말 이렇게 옮겼을 때의 최소 이동횟수가 맞나?"라는 질문에 대답을 할 수가 없다.(심지어 이건 아직 증명되지도 않았다.) 원반이 3개면 그게 뭐가 어렵나고 할 수 있지만 우리가 원하는 것은 3개가 아닌 100개, 1000개, 나아가 n개의 원반에서 이동 횟수, 즉 일반항을 구하는 것이 궁극적 목표인데, 거의 논문 하나가 나올 정도로 어렵기에 그냥 논문을 참조하는 것을 추천한다.(논문에서조차 증명은 없다. 그냥 점화식을 구하고 점화식을 토대로 일반항만 구했지, 이게 정말 최소횟수인지 증명하는 내용은 없다.)

분류