人気ブログランキング | 話題のタグを見る

ハノイの塔

ハノイの塔のパズルは、土台に横一列に3本の柱が並んで立っており、その柱には中心に穴の空いた円盤がさしてある。円盤は最初は左端の柱に大きい方から下から順番に棒に通して重ねてある。

パズルの目的はこの円盤を右端の柱に全て移してしまうことだ。柱の数は3本あるのでそのうちの1本は作業用として使うことができる。ただし、円盤は1回に1枚しか動かせない。また、小さい円盤の上に大きい円盤を重ねることはできない。このパズルはしかし、コンピュータのプログラムで解法を見つけることができる。

お手本のプログラムを写経して動くのを確認して見たことはあるのだが、そのアルゴリズムがもう一つよくわからなかったので Haskell で実験することにした。プログラムは何回も手直しが必要だと思われたので、ファイルに作成した。ファイル名は hanoi.hs にした。

先ず3本の棒の場所を表すデータ型 Place を作った。

module Hanoi where

data Place = A | B | C deriving Show

次に、円盤が1枚だけのパズルの解答を考えてみた。hanoi 関数は円盤の枚数と、円盤の置かれている場所 from とそれを移動する先の to と円盤を一時置いておくための場所の work を引数として、移動を表すペア、たとえば A -> C なら (A,C) のリストを戻り値とした。

円盤の移動の一番単純な形は、円盤が1枚だけのときだ。このときは、円盤は from から to へ移動させることができる。つまり、次のようになる。

hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)]
hanoi 1 from to work = [(from, to)]

実行例は次のようになる。

*Hanoi> hanoi 1 A C B
[(A,C)]

これは A の場所から C の場所へ円盤を移したことを示している。作業用の B の場所には何も置かれていないので使われていない。

次に円盤が2枚の場合を考えてみた。2枚めの円盤を A から C に移し、B に置いてあった1枚目の円盤を B から C に移す。この動作を hanoi 2 from to work を利用して定義すると、1枚目の板は work 領域に置いてあるはずだから、hanoi 1 work to from になるはずだ。

hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)]
hanoi 1 from to work = [(from, to)]
hanoi 2 from to work = [(from, to)] ++ hanoi 1 work to from

実行例は次のようになるがなにかおかしい。

*Hanoi> hanoi 2 A C B
[(A,C),(B,C)]

リストの最初の (A,C) は2枚めの板を A -> C に移動させることを示しており、(B -> C) は1枚目の板を B -> C に移動させることを意味しているが、1枚目の板は最初は A にあったはずなのにいきなり B のところにあることになっている。これは実際のパズルとは違う。

しばらく考えてもわからなかったのでカンニングしたら謎が解けた。上のプログラムでは、最初に1枚目の板を B へ移す動作が記述されていなかったのだ。そこで、それを加えてみた。

hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)]
hanoi 1 from to work = [(from, to)]
hanoi 2 from to work = hanoi 1 from work to ++ [(from,to)] ++ hanoi 1 work to from

実行例は次のようになった。

*Hanoi> hanoi 2 A C B
[(A,B),(A,C),(B,C)]

この結果なら、1枚目の板を A -> B に移し、2枚めを A -> C へ、最後に1枚めを B -> C へ移すので実際のパズルとも合致している。

そこで板が3枚の場合も考えてみた。3枚の板を移動するときに2枚の板を移動させるプログラムを活用することにする。

hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)]
hanoi 1 from to work = [(from, to)]
hanoi 2 from to work = hanoi 1 from work to ++ [(from, to)] ++ hanoi 1 work to from
hanoi 3 from to work = hanoi 2 from work to ++ [(from, to)] ++ hanoi 2 work to from

結果は次の様になった。

*Hanoi> hanoi 3 A C B
[(A,C),(A,B),(C,B),(A,C),(B,A),(B,C),(A,C)]

hanoi 2 と hanoi 3 は同じ形をしているので、このようなものは再帰的定義の recursive case として定義することができる。

hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)]
hanoi 1 from to work = [(from, to)]
hanoi 2 from to work = hanoi 1 from work to ++ [(from, to)] ++ hanoi 1 work to from
hanoi 3 from to work = hanoi 2 from work to ++ [(from, to)] ++ hanoi 2 work to from
hanoi n from to work = hanoi (n-1) from work to ++ [(from,to)] ++ hanoi (n-1) work to from

実行例は次の様になる。

*Hanoi> hanoi 4 A C B
[(A,B),(A,C),(B,C),(A,B),(C,A),(C,B),(A,B),(A,C),(B,C),(B,A),(C,A),(B,C),(A,B),(A,C),(B,C)]

これは1枚めをBに置き、2枚めをCに置き、Bの1枚めをCの2枚めの上に起き、空いたBのスベースに3枚めを置き、... と読めるから実際のパズルの動きをイメージでシミュレーションしてみると正しい答えのようだ。

hanoi n from to work 関数は hanoi 2 from to work と hanoi 3 from to work を含むのでプログラムを次のように整理した。

module Hanoi where

data Place = A | B | C deriving Show

hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)]
hanoi 1 from to work = [(from, to)]
hanoi n from to work = hanoi (n-1) from work to ++ [(from,to)] ++ hanoi (n-1) work to from

最終的に出来上がったプログラムをみたら、なんのことはない、quick ソートと同じ両側への再帰だった。n枚の板を動かすには先ず (n-1) 枚の板を work へ移動させ、次にn枚目の板を from から to へ移動させる。最後に (n-1) 枚の板を work から to へ移動させるという手順そのままのプログラムだ。

再帰的プログラムをいきなり作るのはハードルが高いが、Haskell ではパターンプログラミングができるので、実際の単純な例のプログラムを最初に作ってみて、最後に統一的な再帰的定義として完成させるというような芸当ができる。パターンプログラミングの威力を感じる例だ。

by tnomura9 | 2019-06-25 07:49 | Haskell | Comments(0)
<< 魔法陣 Text.Prinf, Dat... >>