하노이의 탑

비슷한 이름의 AON 하노이 랜드마크 타워에 관해서는 해당 문서를 참고하십시오.

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

하노이의 탑

게임의 목적은 다음 세 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

하노이의 탑의 원리(애니메이션)

하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2ⁿ -1번의 이동으로 원판을 모두 옮길 수 있다(2ⁿ − 1는 메르센 수라고 부른다).

한 번의 실수 없이 64개의 원판을 옮기는 데 2⁶⁴ - 1 = 18,446,744,073,709,551,615번(약 1.84 × 10¹⁹)을 움직여야 하고, 1초당 한 번 원판을 움직일 때 584,554,049,253년(1년 = 365.2425일)이 걸린다. 이는 우주의 나이인 138억 년의 42.4배이다.

유래

하노이의 탑은 프랑스의 수학자인 에두아르 뤼카(Édouard Lucas)가 클라우스 교수(professeur N. Claus)라는 필명으로 1883년에 발표하였다. 1년 후 드 파르빌(Henri de Parville)은 Claus가 Lucas의 애너그램임을 밝히면서 다음과 같은 이야기로 하노이의 탑을 소개하였다.

"인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다."

이후 라우즈 볼, 가드너 등이 하노이의 탑을 소개하면서 널리 알려졌다.

소스 코드

이것은 각각의 수를 구하는 컴퓨터 프로그램 등의 실행어에 대한 것이다.

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);;

Lisp

(defun hanoitowers (disc src aux dst)
  (cond ((> disc 0)
	 (hanoitowers (- disc 1) src dst aux)
	 (princ (list "Move" disc "from" src "to" dst))

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;

C++

#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);
}

파이썬

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_)

Visual Prolog

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).

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)
    }
}

같이 보기

• 재귀 (컴퓨터 과학)

외부 링크

• Weisstein, Eric Wolfgang. “Tower of Hanoi”. 《Wolfram MathWorld》 (영어). Wolfram Research.