アラカン"BOKU"のITな日常

あれこれ興味をもって考えたことを書いてます

今更ですが、ハノイの塔をやってみました。

ハノイの塔というパズルがあります。

 

なんか誰でも知ってるレベルの有名なパズルみたいです。が・・・、恥ずかしながら知りませんでした。

 

下の図のように、3本の柱があって、一番左端(A)に何枚か(例では3枚)の円盤がささっているところからスタートします。

f:id:arakan_no_boku:20170303232100j:plain

 

そこから、円盤を1枚ずつ動かして、真ん中の柱(B)に移すパズルです。上記の3枚のパターンなら、こうなればOKです。

f:id:arakan_no_boku:20170304131001j:plain

 見てのとおり、円盤は図のように全部大きさが違い、下の段ほど大きい円盤になってます。そして、動かす途中であっても、小さい円盤の上に、大きい円盤をのせてはいけないという縛りがあります。

 

これがルールです。円盤の数が3枚なら「3ハノイ」、4枚なら「4ハノイ」のように、円盤の数+ハノイで呼ぶのが一般的みたいです。

 

このサイトによると、「2のN乗 -1(Nは円盤の数)」回で解けるのが最短手順とのことです。

mathtrain.jp

 

 つまり、円盤3枚なら手順は7回(2の3乗-1)で解けるということなのでやってみます。

A→B
A→C
B→C
A→B
C→A
C→B
A→B

 確かに7回ですね。

 

でも、5枚だと、31手順とかが必要になるので、手作業で考えながらやるのは、なかなか大変です。

 

と思ってたら、上記のサイトの記事に、こんな記述がありました。

f:id:arakan_no_boku:20170304002645j:plain

 

おー。再帰的なアルゴリズムがあるということは、プログラムで解けるということですね。

 

早速、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のケースもこれでいけるので書いてないだけです。

 

とりあえず、3ハノイから5ハノイまではプログラムの出力を見ながら、実際にやってみましたが、OKでした。

 

ただ、6ハノイ以上は試してません。すいません。たぶん、大丈夫と思うのですが、もし、バグとかあったら、ごめんなさい。