ハノイの塔（ハノイのとう、Tower of Hanoi）はパズルの一種。 バラモンの塔または ルーカスタワー とも呼ばれる。以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。"n"枚の円盤すべてを移動させるには最低 2 - 1 回の手数がかかる。解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。3本の棒にA,B,Cの名前を付ける。最初Aに "n" 個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。"n" = 1のときは自明であるから、"n" > 2の場合、ここで、1は最初Aに "n" - 1 個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける。再帰的でない解き方として、以下のような手順がある。人間が解く場合にも利用可能である。このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2 - 1 手かかる。棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。初期状態から "n" 回動かした状態は、"n" の2進数表記から、一意的に求めることができる。すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下の様に求められる。ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。2進数の演算を利用すると、"n" 番目の移動を簡単に表記することができる。C言語の表記を用いると "n" 番目の移動は、「"(n&(n-1))%3"番目の棒にある円盤を"((n|(n-1))+1)%3"番目の棒に移動する」となる。ハノイの塔の解答とグレイ・コードによる数字の表記は近い位置にある。グレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。この方法では動かす円盤がわかるだけでどの棒に動かすべきかは求められないが、円盤同士のパリティを考えることにより移動先も定まる。（偶数番目同士、奇数番目同士の円盤は重ならない。）ハノイの塔は、フランスの数学者エドゥアール・リュカが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枚の円盤を移動させるには、最低でも（2-1）回 = 18,446,744,073,709,551,615（1844京6744兆737億955万1615）回かかり、1枚移動させるのに1秒かかったとすると、最低でも約5,845億年かかる（なお、ビッグバンは今から約137億年前に発生したとされている）。日本では1907年（明治40年）に書かれた書物世界遊戯法大全で紹介されている。その中では何回移動させればいいかなど数学的考察もしっかり書かれている。

出典:wikipedia