会社でアルゴリズムの話題でハノイの塔のアルゴリズム考える話を聞いて、ちょっと前にやったのでQiitaの記事にしてみようかなと
ハノイの塔とは
wiki
https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94
ピラミッド状に重なってるものを、小さいものの上に大きいものは乗せてはいけないってルールで最初の一から別の位置へ、三つの位置を移動させながら移し替えるパズルです。
以下では言葉を統一するために移動させるものを円盤、円盤を置ける場所を杭とします
円盤の数によらず三つの杭で移し替えることは可能なのか
数学的帰納法的な論理展開で証明できます。
(1) 円盤が一枚の時
自明
(2) 円盤が1..n-1枚の時、移し替えることが可能だと仮定(n>=2)
円盤がn枚の時
n枚目以外のn-1枚の円盤は別の杭に移動させることは仮定より可能
n-1枚を別の杭に移動させたのちに、n枚目の円盤を残る空いている杭に移し替え、再度n枚目の円盤の上にn-1枚の円盤を移し替えればn枚の円盤を三つの杭でうつしかえることができる。
以上より三つで移し替えることができる。
アルゴリズムを考えてみた
アルゴリズムを考える際に、上記の円盤の塊を別の杭に移し替えるイメージがあって何となく再帰関数を用いてうまいことやれそうだなって思って考えてました。
ただ、n枚の円盤の塊を動かす関数をうまく定義できずにうまくいかずに悩むこと半日。1枚目の円盤の上には何も置けないのでそいつの動きに注目してみようと思い、円盤3枚とか4枚とかで動きを確認したところ何やら規則的な動きをしてるような感じがあり、他の円盤に対しても確認してみたところ、他も同様の規則性が！！
このあたりの規則性に関しては実際にお手を動かして確認された方が感動するかと思います。
で、私がそこから導いたアルゴリズムは以下のような感じです。
円盤を塊で見るのではなく、円盤一つ一つを規則的にうごかす形式です。
書き方悪いので補足します。
routってあるのは何枚の円盤を動かすかって話です。
input:n-1ってあるのは、この関数をinput:n-1で実行させろってことです。
で、これをpythonで記述したのが以下のコードになります
import sys
pos = [0]*int(sys.argv[1])
pole = [list(range(1,int(sys.argv[1])+1)),[],[]]
print(pole)
def move(n,m):
if n!=1 : move(n-1,m)
next = (pos[n-1]+2)%3 if (m-n)%2==0 else (pos[n-1]+1)%3
pole[next].insert(0,pole[pos[n-1]].pop(0))
pos[n-1]=next
print(pole)
if n!=1 : move(n-1,m)
move(int(sys.argv[1]),int(sys.argv[1]))
できる限り短く書いてやろうと頑張りましたが、自分にはこれが限界でした...
そもそも円盤の位置を保持する配列が必要なのかどうか、個人的には疑問だったのですが、その配列なしでうまくやる方法を思いつかなかったので...そのあたりまだまだ改良できそうです。
まとめ
Pythonの勉強がてらハノイの塔のアルゴリズムに挑戦しましたが、Pythonの勉強よりも頭の体操になった感じでした。