ハノイの塔アルゴリズム (Tower of Hanoi Algorithm for VB)

ハノイの塔は、インドの神話では「ブラフマーの塔」と呼ばれ天地創造のとき神が６４枚の金の円盤を重ね、移し替えが終わったときに世界が終焉するといわれたことに由来します（ブラフマー神は創造の神、ヴィシュヌ神は維持の神、シヴァ神は破壊の神）。ルールは下の円盤が常に上に重なる円盤よりも大きな円盤になるようにします。６４枚の円盤を移し変えるには最小で2⁶⁴-1回(18,446,744,073,709,551,615回)の移動が必要です。

今回の記事では、その移し変えのアルゴリズムを紹介します。下の画像は３枚のディスクを左のロッドから右のロッドに移し替えた場合のイメージです。

Algorithm of "Tower of Hanoi" which is written by VB as shown below, click "Continue Reading". The images below is how to move the three disks from a left rod to a right rod.

1

2

3

4

5

6

7

8

ハノイの塔のアルゴリズムのソースコードを２つ紹介します。アルゴリズム自体は同じものです。２番目のソースコードは３本あるロッドの目的地のロッドと間にあるロッドの受け渡しを交互に選択されるように(6 - Start - Dest)と書いてあります。省略された分、コードが簡略化されてます。 最小の移動回数は2^N-1 (Nはディスクの数）になります。10枚のディスクのケースでは、2¹⁰-1=1023回の移動が必要です。20枚の場合はもう３桁増えます。64枚のディスクの場合は2^N-1回の移動になります。64枚の場合、プログラムが実行されたら冗談抜きで少なくとも数千年の時間を要することになると思います。VBAで実行してもQueueのスタック領域の制限があるのでエラーになると思います。Java や C などでこのアルゴリズムを実行する際は枚数設定で注意が必要です。

3枚のディスクを移動する場合は以下のようになります。2³-1=7回の移動回数です。１番目のロッドが初期設定の場所で、そこから目的地の３番目のロッドに移動します。(プロシージャを実行するとイミディエイトウィンドウにに表示されます。)

Move Disk(No.1) from 1 to 3　<--ディスク1を1から3に移動
Move Disk(No.2) from 1 to 2
Move Disk(No.1) from 3 to 2
Move Disk(No.3) from 1 to 3
Move Disk(No.1) from 2 to 1
Move Disk(No.2) from 2 to 3
Move Disk(No.1) from 1 to 3

4枚のディスクを移動する場合は以下のようになります。2⁴-1=15回の移動回数です。

Move Disk[No.1] from 1 to 2
Move Disk[No.2] from 1 to 3
Move Disk[No.1] from 2 to 3
Move Disk[No.3] from 1 to 2
Move Disk[No.1] from 3 to 1
Move Disk[No.2] from 3 to 2
Move Disk[No.1] from 1 to 2
Move Disk[No.4] from 1 to 3
Move Disk[No.1] from 2 to 3
Move Disk[No.2] from 2 to 1
Move Disk[No.1] from 3 to 1
Move Disk[No.3] from 2 to 3
Move Disk[No.1] from 1 to 2
Move Disk[No.2] from 1 to 3
Move Disk[No.1] from 2 to 3