ハノイの塔

概要
ゲームの解析
プログラミング的な話
文化的な話
参考

概要

3本の杭とそれに刺さる円盤を動かすことで、円盤のタワーを左から右に移動するパズルゲームです。ルールとして動かした円盤は必ず杭（peg）に刺します。また、小さな円盤の上に大きな円盤を動かしてはいけません。ゲーム木を作れる一人パズルゲームで、再帰的なコンピュータアルゴリズムの解説でよく扱います。バラモンの塔やルーカスタワーとも呼ばれます。次のリンクで遊べます（円盤は4枚）。AUTOを押すと初めから自動で、最短の方法でパズルを攻略します。

hanoi

ゲームの解析

このゲームは再帰的な解法によって簡単に攻略ができるほか、より単純なアルゴリズムであっても解くことができることで知られます。

一般にゲームの攻略は、その目標の状態にするための副目標の状態を作ることで解決します。具体的には、左のタワーを右に移動するために一番目に大きい円盤をまず右に移動する必要があり、そのために一番目に大きい円盤以外の円盤を真ん中に積む必要があります。しかし、そのためには二番目に大きな円盤を真ん中に移動する必要があり、そのために一番と二番目に大きい円盤以外の円盤を右に積む必要があります。しかし、その、、、と一番目に小さい円盤まで再帰的に分解して副目標を設定することです。

つまりこのゲームでは攻略において、以下を再帰的に繰り返すことで成立し、どうにかしての部分は分解的に求まります。

移動したい円盤より上の円盤群を移動したい杭でない杭にどうにかして移動
移動したい円盤を移動したい杭に移動
１で移動した円盤群を２で移動した円盤の上にどうにかして移動

円盤の枚数をｎとすると、最善で2^ｎ-1回の移動でゲームを終了できます。また総局面数は3^ｎで、ハノイグラフと呼ばれる無向グラフによってすべての状態をあらわすことが可能です。

プログラミング的な話

いくつかある解法のなかの一つとして再帰的なアルゴルズムによって簡単にプログラムすることができます。

//関数moveは配列solutionに選択と移動先の杭の数字（０・１・２）＝（左・真ん中・右）を格納する
//円盤が3枚の時このようにして使うー＞move(3,0,1,2,solution[])
void move(int discsNum,int org,int tmp,int dst,int[] solution){
    if(discsNum==1){//移動する必要のある円盤が1枚の時
      solution.push(org);//選択される円盤のある杭の数字を格納
      solution.push(dst);//選択した円盤の移動先の杭の数字を格納
      return;
    }else{
      //１．移動したい円盤より上の円盤群を移動したい杭でない杭に移動（org->tmp）
      move(discsNum-1,org,dst,tmp,solution);
      //２．移動したい円盤を移動したい杭に移動（org->dst）
      move(1,org,tmp,dst,solution);
      //３．１で移動した円盤群を２で移動した円盤の上に移動（tmp->dst）
      move(discsNum-1,tmp,org,dst,solution);
    }
  }