ハノイの塔とはどんなパズルか

ハノイの塔というパズルは、細長い台に3本の支柱が立っていて、それに中心に穴の開いたドーナッツ状の円盤が重ねられて刺さっている。円盤は上に行くほど小さくなるので、全体としてピラミッド型をしている。

円盤は最初全てが左端の支柱に刺さっているが、それを右端の支柱に移すのがパズルの目的だ。ただし、円盤は一度に一枚しか移動できない。また、小さい円盤の上にそれより大きな円盤を重ねることはできない。このパズルを解くプログラムを作ってみようという訳だ。

まず3本の支柱をアルファベットの A B C で識別することにする。円盤は最初全て A の支柱に重ねられていて、それを、C の支柱に移動することになる。ここで、Aの円盤全てがCの円盤全てに移されるときの最終段階の様子を考えてみる。仮に円盤の個数が n 個であったとする。また、円盤には上から順番に 1..n の番号が割り振られているとする。

すると、一番大きな n の円盤をAからCへ移すためには、n-1個の円盤が B の支柱に重ねられている必要がある。なんらかの方法でその操作を終えたのち、AからCへ n の円盤を移すことができる。そのうえで、また、何らかの方法で B に重ねてある n-1 個の円盤を、Cに刺さっている n の円盤の上に重ねてやれば移動は完了する。

そこで、n 個の円盤を何らかの方法で移動させることを、hanoi n from work to という関数で表すことにする。hanoi が関数名、 n が円盤の数、from は移動前に円盤が重ねられていた支柱の名前、work は作業用に利用された支柱の名前、to は最終的に n 個の円盤が移動した支柱の名前だ。

そうすると、n 個の円盤全部を支柱 A から支柱 C へ移動させる方法は、hanoi n 'A' 'B' 'C' で表せる。n-1 個の円盤を支柱 A から支柱 B まで移動させる方法は、hanoi (n-1) 'A' 'C' 'B' だ。また、n-1 個の円盤を支柱 B から支柱 C まで移動させる方法は hanoi (n-1) 'B' 'A' 'C' だ。さらに、支柱Aから支柱Bへn番の円盤を移動することを、(n, 'A', 'B') の三つ組で表すことにする。

ハノイの塔プログラム

これらの抽象的な考察をもとに作ったのが次のプログラムだ。hanoi がどういう関数なのかという内部構造には一切触れず上の考察をそのままプログラムにしている。

Prelude> :{
Prelude| hanoi 0 _ _ _ = []
Prelude| hanoi n from work to =
Prelude|   hanoi (n-1) from to work ++
Prelude|   [(n, from, to)] ++
Prelude|   hanoi (n-1) work from to
Prelude| :}

一行目の定義は hanoi 関数の終了条件で、これがないとスタックがオーバーフローするまでプログラムが止まらない。この意味は、円盤の数が０の時はなにもしないという意味だ。

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

Prelude> hanoi 2 'A' 'B' 'C'
[(1,'A','B'),(2,'A','C'),(1,'B','C')]
Prelude> hanoi 3 'A' 'B' 'C'
[(1,'A','C'),(2,'A','B'),(1,'C','B'),(3,'A','C'),(1,'B','A'),(2,'B','C'),
(1,'A','C')]

ちゃんとパズルの回答が出力されているのに不思議な気がする。繰り返しのある構造のデータについて、ある一点でのデータ構造を記述することで全体の動きをプログラムできる再帰的定義の威力を感じさせる例だ。

Haskell を使うとだんだん馬鹿になるそうだ。スタックやキューやデータ構造などを考えなくても、アルゴリズムをPerl で文字列を扱うときのように記述できてしまう。Haskell は一種のアルゴリズム記述言語だ。Haskell のプログラム例の解読の難しさは、言語操作の難しさではなく、アルゴリズムそのものの難しさなのだろう。