ハノイの塔の攻略法

キューブ王 海永

ハノイの塔は以下のようなパズル。

 棒Aの位置に重ねてあった複数の円盤を、棒Cの位置に移動する。

円盤は1枚づつ移動する。必ず、棒A,B,Cの位置に重ねる。小さい円盤の上に大きい円盤を載せてはならない。

 

[攻略法]

Aの位置に5枚重ねてあったとする。これを総て棒Cの位置に移動するのが問題。この問題の解法をH(5,A,C)と呼ぼう。

この問題は、かなり難しい。

しかし、4枚の問題の解法を我々は知っていると仮定する。そこで4枚をAからBに移動する。これはH(4,A,B)と呼べる。

H(4,A,B)後の状態を眺めれば、棒Aに残っていた円盤5をCに移動できることが分かる。実際に移動。これをm(A,C)と呼ぼう。

m(A,C)後の状態を眺めれば、後はB位置の4枚の円盤をC位置に移動すればいいと分かる。すなわちH(4,B,C)で終わり。

    5枚の解法   H(5,A,C)=H(4,A,B)*m(A,C)*H(4,B,C)

“=”は、勿論「は」と読む。”*”は「それから」と読む。全体は以下のように読む。 「H(5,A,C)は、H(4,A,B)、それからm(A,C)、それからH(4,B,C)」。

 さて我々は、4枚の問題の解法を本当に知っていたのかと自問する。実は知っていると仮定しただけで知らなかった。しかし「5枚の解法」と同様なことが4枚の解法に適用できる。

    4枚の解法   H(4,A,B)=H(3,A,C)*m(A,B)*H(3,C,B)

H(4,B,C)=H(3,B,A)*m(B,C)*H(3,A,C)

次に3枚の問題の解法を知っているかと、自問することになるかもしれない。しかし3枚の解法なら、間違えることなくその場で旨くやれそうで問題あるまい。

 

 ハノイの塔は、素数判定で有名なリュカの発明だそうである。「リュカ ハノイ」でgoogleサーチすれば夥しい数の記事がサーチできると思う。昔、何故「ハノイの塔」という名前なのが不思議だったのだが、ベトナムがフランスの植民地だったという程度の話かららしくてウンザリしてしまった。

 

[Cコード]

 以上が、解法。こういう解法、馬鹿だが言われた通りに実行するのが得意なコンピュータにやらせるのが相応しい。以下のCコードはその例。

 

#include <stdio.h>

void move(int n,int from,int to)

{             printf("move %d from %c to %c\n",n,from,to); }

void hanoi(int n,int from,int to)

{             int third='A'+'B'+'C'-from-to;

              if(n==0)    return;

              hanoi(n-1,from,third);

              move(n,from,to);

              hanoi(n-1,third,to);

}

main()

{             int n=4;

              printf("++++ hanoi %d ++++\n",n);

              hanoi(n,'A','C'); printf("\n");

}

 

しかし、表示が貧弱か。以下のコードなら、移動をそれなりに図示してくれることになる。

 

#include <stdio.h>

int pole[3][10];

int ix0,ix1,ix2;

 

char*str[10]={

"         |         ", "        [1]        ", "       [2|2]       ",

"      [33|33]      ", "     [444|444]     ", "    [5555|5555]    ",

"   [66666|66666]   ", "  [777777|777777]  ", " [8888888|8888888] ",

"[99999999|99999999]"

};

void showState()

{             int n0,n1,n2,i;

              for(i=9; i>=0; i--){

                            n0=pole[0][i]; n1=pole[1][i]; n2=pole[2][i];

                            if(n0 || n1 || n2)

                              printf("%s  %s  %s\n",str[n0],str[n1],str[n2]);

              }

              printf("---------A--------------------B--------------------C-------\n");

}

void initState(int n)

{             int i;

              for(i=0;i<n;i++){

                            pole[0][i]=n-i; pole[1][i]=0; pole[2][i]=0;

              }

              ix0=n; ix1=0; ix2=0;

              showState();

}

void newState(int n,int from,int to)

{             switch(from){

              case 'A': pole[0][--ix0]=0; break;

              case 'B': pole[1][--ix1]=0; break;

              case 'C': pole[2][--ix2]=0; break;

              }

              switch(to){

              case 'A': pole[0][ix0++]=n; break;

              case 'B': pole[1][ix1++]=n; break;

              case 'C': pole[2][ix2++]=n; break;

              }

              showState();

}

 

void MOVE(int n,int from,int to)

{             printf("move %d from %c to %c\n",n,from,to);

              newState(n,from,to);

}

void HANOI(int n,int from,int to)

{             int third='A'+'B'+'C'-from-to;

              if(n==0)    return;

              HANOI(n-1,from,third);

              MOVE(n,from,to);

              HANOI(n-1,third,to);

}

main()

{             int n=3;

              printf("++++ hanoi %d ++++\n",n);

              initState(n);

              HANOI(n,'A','C'); printf("\n");

}

 

 

トップページへ

 

Ads by TOK2