ハノイの塔

ハノイの塔についてはググって頂くとして。
ハノイの塔　wikipedia

棒１に刺さっている円盤の一番上のものを、棒２へと移動するとき

(1.2)

のように表現する

たとえば、棒 1に刺さっている３枚の円盤を、棒2へと移動することを考えたとき

その手順は以下のようになる

[ (1.2) (1.3) (2.3) (1.2) (3.1) (3.2) (1.2) ]

これを解く関数をPrologっぽい擬似言語で。帰納的に書いてみると、

一枚だけのときはそのまま素直に

ハノイの塔(１,開始位置,移動先,その他の棒,手順) :-

  [(開始位置 . 移動先) ].

開始位置に円盤がＮ枚有る場合は、

• Ｎ−１枚を開始位置でも移動先でもない「その他の棒」へと移動
• Ｎ枚目＝一番大きな円盤を　開始位置から移動先へ移動
• Ｎ−１枚の山をその上に移動

ハノイの塔(円盤の枚数,開始位置,移動先,その他の棒,手順) :-

  ハノイの塔(円盤の枚数-1,開始位置,その他の棒,移動先,手順1),

  ハノイの塔(円盤の枚数-1,その他の棒,移動先,開始位置,手順2),

　リストを連結([手順1,[ (開始位置 .  移動先) ],手順2], 手順).

 

とりあえず擬似言語でしか書いてないので、ちゃんと動くかどうかチェックしてないですけれども。