サンプルコード：ハノイの塔

再帰（ recursion ）を使うと解法のロジックをわかりやすく表現できる問題のひとつに「ハノイの塔」というものがあります。

ハノイの塔（ハノイのとう、Tower of Hanoi）はパズルの一種。 バラモンの塔または ルーカスタワー(Lucas' Tower)とも呼ばれる。

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n枚の円盤すべてを移動させるには最低 2n − 1 [2]回の手数がかかる。

解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。

ハノイの塔 - Wikipedia

画像、テキストともに出典はいずれも Wikipedia です。

私事ですが、最近ホワイトボードプログラミングの本を読んでおりその中にハノイの塔が出てきたので、今回は個人的なエクササイズも兼ねてハノイの塔のプログラムを Python で書いておきたいと思います。

ここに載せるには少し長くなったので Gist に貼り付けました。



このプログラムを実行すると次のような内容が出力されます。「 move ... 」から始まる行はディスクの移動を表します。 s d e は各塔を表します。蛇足かもしれませんが、 s は source 、 d は destination 、 e は extra の略です。

started.
s: 3 2 1 
d: 
e: 
move disk-1 from s to d (1).
s: 3 2 
d: 1 
e: 
move disk-2 from s to e (2).
s: 3 
d: 1 
e: 2 
move disk-1 from d to e (3).
s: 3 
d: 
e: 2 1 
move disk-3 from s to d (4).
s: 
d: 3 
e: 2 1 
move disk-1 from e to s (5).
s: 1 
d: 3 
e: 2 
move disk-2 from e to d (6).
s: 1 
d: 3 2 
e: 
move disk-1 from s to d (7).
s: 
d: 3 2 1 
e: 
finished.

解法のコアとなる部分は TowerOfHanoi クラスの move_disk() メソッドのみです。その他の部分は、途中経過や移動の回数を表示するための周辺的コードです。

ハノイの塔の解法がなぜ move_disk() のような再帰を含むメソッド（関数）で書けるのかについてここでの説明は割愛します。興味のある方は Wikipedia の「解き方」の節をご覧になってみてください。

私事ですが、ふだんはウェブ開発をやっていて、このような難しいアルゴリズム問題を考えたりするようなことはあまりないので、書いていてとても新鮮な気持ちになりました。おもしろいです。


参考

ハノイの塔 - Wikipedia