キーワード辞典
ハノイの塔

登録日 05/05/05   更新日 05/05/05



再帰プログラムを説明する時に8クイーンと並んで必ずと言って良いほど例に出されるゲーム。 1883年にフランスのサン・ルイ校(Saint-Louis)の数学教授リュカ(Edouard Lucas)が、 友人であるリー・スー・スチャン(Li-sou-stian)大学の中国公務員 N・クロー・ド・シャム教授(N.Claus)から聞いた話を基にして考案したことになっていますが、 実は、この友人の大学名と名前はリュカ自身のアナグラムで、 全てリュカの創作であり、 この友人は真実性を高めるための架空の人物らしいです(伝聞)。 何故にハノイ? というのは、 同じ1883年にフランスはベトナムを保護国としているなどの世界事情によるのではないか、 と思われています。
伝説のストーリーは、以下の通り。

インドのガンジス河畔にベナレスという町がある。 ここには大きな寺院があって、世界の中心を示すドームがあり、 ドームの真下には1枚の青銅の板がある。 その板の高さ1cubit(約50cm)で、 ミツバチの胴体ほどの太さのダイヤモンドの針が3本立ててあり、 そのうちの1本には64枚の純金の全て大きさの違う円盤が上から小さい順に積み重ねられている。 世界の始まりの時、 バラモンの神は寺院の僧侶達を集めて円盤を積み重ねた黄金の塔を指し、 「これはバラモンの塔である。 汝ら、今よりこの3本の針を使い、64枚の純金を他の針に移せ。 1度に1枚ずつであることは当然だが、 小さな円盤の上に大きな円盤を積み重ねる様な事は決して有ってはならない。 この仕事は、バラモンの掟に従って日夜休みなく実行せよ。 64枚の円盤を1本の針から他の針に完全に移し終わった時がこの世の終わりである。 その時には、塔も寺院もお前たちも一切のものが塵と化し、 恐ろしい雷鳴とともに世界が消滅するであろう」 と告げたという。


このゲームのアルゴリズムの基本形は、 3本の棒があり、そのうちの1本に重なっている小大の2枚の円盤を、 全て別の棒へ同じ重なり方で移動させる動きです。 ここでは、左の棒から中央の棒へ移動させます。 次の様に3回で完了します。

(基本形)
小                  小
大   → 大 小 →  大小 →  大
+++   +++   +++   +++
      1回目   2回目   3回目

大中小の3枚の円盤で考える時、仮に小と中が接着剤でくっついているとすると、 基本形と同じ2枚の移動と同じ考え方が出来るので、

(第1図)
小                  小
中       小     小    中
大   → 大 中 →  大中 →  大
+++   +++   +++   +++
      1回目   2回目   3回目

となるのですが、第1図の1回目と3回目の移動は、 実際は小と中の2枚の円盤の移動ですから、 実は1回ではなく、それぞれに基本形の3回が必要となり、 全体の回数は、第2図の様に、基本形+1回+基本形=3回+1回+3回で7回になります。

(第2図)
小                            小
中   中         小   小      中   中
大   大小  大小中 大 中  大中 小大中 小大   大
+++ +++ +++ +++ +++ +++ +++ +++
    ← 第1図の1回目 →     ← 第1図の3回目 →

円盤が4枚の時も同様に、第2図の小をさらに2枚に分けると、 第2図でいう小が移動した時に実際には基本形の3回の移動が起きますから、 全体の回数は、((3回+1回+3回)+1回+(3回+1回+3回))=7回+1回+7回=15回になります。

こうしてみると、複数枚数のハノイの塔の円盤を別の棒に同じ形で移動させる時の回数は、 実は、1枚少ない時の移動回数の2倍に一番大きい円盤を動かす1回を加えたものであることが 見えてきます。 例えば、円盤が5枚ならば、15回+1回+15回=31回です。

これを数学的に書くと、
n枚の円盤を別の棒に同じ形で移動させる時の回数をaとすると、

nが1の時は当然1回で終わりなので、a=1

nが2以上の正の整数の時は、

  1. まず、上からn-1枚の円盤を全て別の棒に移す。 → an-1
  2. 一番大きい円盤をもう一つの棒に移す。 → 1回
  3. 上からn-1枚の円盤を全て一番大きい円盤の有る棒に移す。 → an-1
よって、a=2an-1+1

と、なります。

この様に、aを求めるためにan-1 を求めなければならない場合は、 1つの関数から同じ関数を呼び出す再帰プログラムを使うと便利です。
例えば、円盤が5枚の場合の移動回数をシミュレーションするプログラムの流れは、 上記の条件から、

  1. 円盤が5枚の時の回数=円盤が4枚の時の回数×2+1=?
    それなら、
  2. 円盤が4枚の時の回数=円盤が3枚の時の回数×2+1=?
    それなら、
  3. 円盤が3枚の時の回数=円盤が2枚の時の回数×2+1=?
    それなら、
  4. 円盤が2枚の時の回数=円盤が1枚の時の回数×2+1=?
    それなら、
  5. 円盤が1枚の時の回数=a=1なので、1回
    よって、
  6. 円盤が2枚の時の回数=円盤が1枚の時の回数×2+1=1×2+1=3回
    よって、
  7. 円盤が3枚の時の回数=円盤が2枚の時の回数×2+1=3×2+1=7回
    よって、
  8. 円盤が4枚の時の回数=円盤が3枚の時の回数×2+1=7×2+1=15回
    よって、
  9. 円盤が5枚の時の回数=円盤が4枚の時の回数×2+1=15×2+1=31回
となります。




板の動きをJavaとC言語のプログラムでシミュレーションすると、こんな感じになります。
最も小さい板から順に1、2、3、と番号を付けます。


Javaの例。
プログラムの引数で板の枚数を指定しています。
※プログラムをダブルクリックすると、コピー出来ます。


public class Hanoi{

  static int cnt=0;

  public static void hanoi(int n, char a, char b, char c) {
    if(n>0){
      hanoi(n-1, a, c, b);
      System.out.printf("%2d: %d番目に小さい板を %c から %c に¥n", ++cnt, n, a, b); 
      hanoi(n-1, c, b, a);
    }
  }

  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    System.out.printf("%d枚の板を左の柱にセット¥n",n);
    hanoi(n, '左', '中', '右');
    System.out.println("完了!");
  }

}


このプログラムを板4枚で実行すると、左の様に計15回目で終了しますが、
表示される手順のちょうど真ん中(8回目)で一番大きい板4が動いており、
その上半分と下半分では同じ動きをしており、
それぞれの丁度真ん中(4回目と12回目)で二番目に大きい板3が動いており、
さらに、...という過程が、確認出来ると思います。





C言語の例。
※プログラムをダブルクリックすると、コピー出来ます。
#include <stdio.h>

void hanoi(int n, char a, char b, char c){
  if(n>0){
    hanoi(n-1, a, c, b);
    printf("%d番目に小さい板を %c から %c に¥n", n, a, b);
    hanoi(n-1, c, b, a);
  }
}

void main(void){
  int n;
  prinftf("円板の枚数 ? ");
  scanf("%d",&n);
  printf("%d枚の板を左の柱にセット¥n",n);
  hanoi(n, '左', '中', '右');
}



かなり昔ですが、全商のプログラム競技大会の全国大会で (再帰の出来ない)COBOL言語でハノイの塔が出題された時は、 確かに、再帰を使わなくても可能なのですが、 そんなの有りか~、と思いました...




n枚(nは1以上の整数)の円盤の時のハノイの塔の解a=は、 2-1で求められることが判っています。
ちなみに、n=64の場合の解は、
64ー1=18,446,744,073,709,551,615
となり、円盤1枚を1秒で移動させるとしても、およそ5845億年かかることになります。 当分は世界は大丈夫の様です。

(’05/05/05 記す)


[ 赤い玉の画像 ] 「キーワード辞典」の目次へ

[ 黒板消しとチョーク受けの画像 ]