ストーリー
インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールの説明は省略）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。
概要
ハノイの塔とは3本の柱に通された円盤を用いるパズルである。基本的には最も左の柱に何枚かの円盤が通されており、その円盤を全て別の（同一の）柱に移し替えることを目標とする。
パズルとしてはシンプルなものであり、プログラミングの再帰呼び出しの例題としても有名である（実際、解法は機械的に求めることが可能）。
ルール
ハノイの塔には以下のルールがある
- 3本の柱と何枚かの円盤が用意される。円盤の大きさは全て異なっている。
- 円盤の上にはその円盤より小さな円盤しか置くことが出来ない
- 最初に左の柱に全ての円盤が通されている（2のルールから最上段が最も小さな円盤で、最下段が最も大きな円盤である）
- 円盤は1度に1枚を柱から外し、別の柱に通す。
- 最終的に左の柱以外のどちらかの柱に全ての円盤を通せばクリアである（右の柱とされる場合もあるが、右の柱に移し替えるのも真ん中の柱に移し替えるのも基本的には同解法である）
このパズルは円盤の枚数は何枚であろうと解く事が可能であり、円盤の枚数をn枚とした時、2のn乗-1回の手数で解けることが分かっている。
解き方
何枚であっても解き方は一緒である。
- 奇数手では最も小さい円盤を動かす 偶数手ではそれ以外の円盤を動かす
- 奇数手では「中央か右の柱」→「中央か右の柱」→「左の柱」→ループ で動かす
- 偶数手ではその時動かせる最も小さい円盤以外の円盤を動かせる場所へ動かす
尚、奇数手のループは最初に決めた順番を維持する必要がある。例えば1手目に右の柱と決めた場合はループ後も右の柱にしなければならない。
これを機械的に繰り返すだけで解ける。
再帰的解法
全て右の柱に移すと考える。
- n=1の時
円盤が1枚の時は円盤を右の柱に移せば完了である。
- n>2の時
n-1枚の円盤を真ん中の柱に移し、n番目の円盤を右の柱に移す。その後、n-1枚の円盤を右の柱に移せば完了である。
つまりn-1枚の円盤を真ん中の柱に移す方法を考えるとn-2枚の円盤を右の柱に移し、n-1番目の円盤を真ん中の柱に移し、n-2枚の円盤を真ん中の柱に移せば完了となる。
これを再帰的に行えば良い。
ちなみに……
冒頭のストーリーでは64枚の円盤を用いてハノイの塔を解くという話であったが、これを実際に行おうとすると2の64乗-1手かかることが分かる。これは1秒に1枚の円盤を動かすとしておよそ6000億年近い時間が掛かる。
64枚のハノイの塔を解いた時、世界が崩壊するというのはあながち間違いではないのかもしれない。
関連タグ
秋山仁…お気に入りらしく、著書等の度に出してくる。
