ハノイの塔

プログラミング学習者が一度は挑戦するのが「ハノイの塔」の実装だ。

ハノイの塔とは、3本の杭と中央に穴の開いた大きさの異なるいくつかの円盤とで構成されるパズルで、左端に積み重ねられている円盤を、全て右端に移動させるというもの。円盤を移動する際には、(1) 小さい円盤の上には大きい円盤を置いてはいけない、(2) 移動できるのは1枚づつ、というルールを守らなければならない。(詳細はこちら)

多くのプログラミング学習書において、サブルーチンとかモジュールにおける「再起呼び出し」を説明する際に、このパズルがよく引き合いに出されている。

自分も先日から Ruby の勉強を始めてて、久しぶりにこのハノイの塔を実装してみようと思った次第。とりあえず自力で作ってみたものの、もっとスマートな解法があるんじゃないかと思って調べていたら、驚くべきページに出くわした。その名も Hanoimania! 。

このサイト、自らを「ハノイマニア」と呼ぶにふさわしい熱の入れようで、尊敬の念を越えてあきれかえってしまう。というのも、このサイトの Amit Singh 氏は、なんと108 もの手法を用いてハノイの塔を実装しているのだ。古いものでは BASIC や COBOL に始まり、有名どころの C や VB はもちろんのこと、比較的新しい Java や PHP まで、おおよそ想像しうる全てのプログラミング言語での解法が紹介されている。

そして中には「そんなんでハノイの塔が実装できるの？」っていうのもいくつかある。例えば Sendmail や PING などがそうだ。PING に関しては、実行結果が icpm_sec のカラムにアウトプットされるように Hack されてて、レスポンスが一行返ってくる度に解が提示されるようになっている。

しかしまぁ、一つの解を得るための手法がこれだけ集められてると、そのソースを見るだけでなかなか面白い。ある意味プログラミング言語の博物館みたいだ。個人的にはやっぱり Perl のソースが一番美しくてエレガントだと思う。ステップ数もたったの17だし、とってもスマートだ。

それにしても、お前はなぜそこまでしてハノイの塔を実装したいのかと問いたい。問い詰めたい。小1時間問い詰めたい。

# 余談
Emacs で M-x hanoi とすると、ハノイの塔の回答が見れます。引数を指定したい場合は、 C-u 5 M-x hanoi とかするとOK。

Hanoimania!
http://www.kernelthread.com/hanoi/