ハノイの塔

ハノイの塔（ハノイのとう、Tower of Hanoi）は、パズルの一種。 バラモンの塔または ルーカスタワー"(Lucas' Tower)"とも呼ばれる。
ルール.
以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
"n"枚の円盤すべてを移動させるには最低 2"n" − 1 回の手数がかかる。
解は、次のように再帰的に考えることができる。塔を「一番下にある円盤」と「残りの円盤群」というように分けてみる。そして、まず「残りの円盤群」を移動させ、次に「一番下にある円盤」を移動し、その上にまた「残りの円盤群」を動かせばよい。
解が再帰的な構造をしているということから、この解の手順を表示させるという問題は、再帰的なコンピュータ・プログラムの単純な例題として多用されている。ただし支配数がメルセンヌ数なので、同じく再帰の例題として多用されるフィボナッチ数のように、"n"が大きくなると結果も膨大となる。
解き方.
3本の棒にA,B,Cの名前を付ける。最初Aに "n" 個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。"n" = 1のときは自明であるから、"n" > 1の場合、
ここで、1は最初Aに "n" − 1 個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。
3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける。
実用的な解法.
再帰的でない解き方として、以下のような手順がある。人間が解く場合にも利用可能である。
このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2"n" − 1 手かかる。
棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。
2進数による解析.
初期状態から "n" 回動かした状態は、"n" の2進数表記から、一意的に求めることができる。
すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下のように求められる。
ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。
2進数の演算を利用すると、"n" 番目の移動を簡単に表記することができる。C言語の表記を用いると "n" 番目の移動は、「(n&(n-1))%3 番目の棒にある円盤を ((n|(n-1))+1)%3 番目の棒に移動する」となる。
なお、メルセンヌ数は二進数では全ての桁の位を占める数が1になるから、前述の二進数演算による解析は、全ての棒に与えられた枚数n分の二進メルセンヌ数桁との因果関係を明らかにしている。これは次項のパリティとグレイ・コード解法にも大きく関与しているといえる。
グレイコードによる解法.
ハノイの塔の解答とグレイ・コードによる数字の表記は近い位置にある。
グレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。
この方法では動かす円盤がわかるだけでどの棒に動かすべきかは求められないが、円盤同士のパリティを考えることにより移動先も定まる（偶数番目同士、奇数番目同士の円盤は重ならない）。
前述の通り、全ての桁と円盤を対応付ける事は、その桁に対応したメルセンヌ数に支配される事と等しい。
由来.
ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。パッケージには「Li-sou-stian大学勤務のシャム出身のN. Claus教授によりトンキンからもたらされたゲーム」と書かれているが、Li-Sou-Stian大学はリュカが働いていたリセ・サン＝ルイ (Saint-Louis) 校のアナグラム、シャム出身のN. Claus (N. Claus de Siam) はアミアン出身のリュカ (Lucas d'Amiens) のアナグラムであるため、すべてはリュカの創作だと思われている。
同梱のリーフレットには、次のような伝説があると書かれていた。
インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールの説明は省略）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。
パッケージではハノイの塔となっていたが、リーフレットではブラフマーの塔となっていた。ハノイはトンキンの中心都市、ブラフマーはヒンドゥー教や仏教における創造神である。
この話には多くのヴァリエーションが生まれた。たとえば、ダイヤモンドの針のかわりに大理石の柱が立っているなどである。
64枚の円盤を移動させるには、最低でも
かかり、1枚移動させるのに1秒かかったとすると、最低でも約5845億年かかる（なお、ビッグバンは今から約137億年前に発生したとされている）。
日本におけるハノイの塔.
日本では1907年（明治40年）に書かれた書物『世界遊戯法大全』で紹介されている。その中では何回移動させればいいかなど数学的考察もしっかり書かれている。
脚注.
注釈
出典