ハノイの塔とは
たぶん、誰でも知ってるレベルの有名なパズルです。
下の図のように、3本の柱があって、一番左端（A)に何枚か（例では3枚）の円盤がささっているところからスタートします。
そこから、円盤を1枚ずつ動かして、真ん中の柱（B）に移すパズルです。上記の3枚のパターンなら、こうなればOKです。
見てのとおり、円盤は図のように全部大きさが違い、下の段ほど大きい円盤になってます。そして、動かす途中であっても、小さい円盤の上に、大きい円盤をのせてはいけないという縛りがあります。
これがルールです。
円盤の数が３枚なら「３ハノイ」、４枚なら「４ハノイ」のように、円盤の数＋ハノイで呼ぶのが一般的みたいです。
最短手順の計算式
このサイトによると、「２のN乗 －１（Nは円盤の数）」回で解けるのが最短手順とのことです。
つまり、円盤３枚なら手順は７回（２の3乗－1）で解けるということなのでやってみます。
A→B
A→C
B→C
A→B
C→A
C→B
A→B
確かに7回ですね。
でも、5枚だと、31手順とかが必要になるので、手作業で考えながらやるのは、なかなか大変です。
ハノイの塔を解くアルゴリズム
上記のサイトの記事に、こんな記述がありました。
おー。
再帰的なアルゴリズムがあるということは、プログラムで解けるということですね。
pythonのソースコード
早速、pythonでやってみました。
def hanoi_imp(n,a,b,c):
nop = 0;
if n <= 0:
nop = 0
else:
hanoi_imp(n - 1,a,c,b)
print ( a + u"→" + b)
hanoi_imp(n - 1,c,b,a)
def hanoi(n,a,b,c):
hanoi_imp(n,a,b,c)
引数のnに円盤の枚数をわたし、a,b,c には、表示用にA,B,Cの文字を渡します。
再帰呼び出しをするところで、引数で渡されてa,b,cの位置を入れ替えないといけない所が、ちょっと工夫が必要でしたが、ほぼ、まんまです。
n=1のところは横着してはしょってる様に見えますが、実行してみたらn=1のケースもこれでいけるので書いてないだけです。
とりあえず、３ハノイから5ハノイまではプログラムの出力を見ながら、実際にやってみましたが、OKでした。
ただ、6ハノイ以上は試してません。すいません。たぶん、大丈夫と思うのですが、もし、バグとかあったら、ごめんなさい。
ではでは。