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

ルール

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

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

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

解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。ただし支配数がメルセンヌ数^[4]なので、同じく再帰の例題として多用されるフィボナッチ数^[5]同様、再帰をストレートに実装するととんでもない事態を生む例でもある。

解き方

3本の棒にA,B,Cの名前を付ける。最初Aに n 個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。n = 1のときは自明であるから、n > 2の場合、

1. 上から n − 1 個目までの円盤を何らかの方法でAからBに移動する。
2. 残った1枚をAからCに移動する。
3. Bにある円盤を何らかの方法でBからCに移動する。

ここで、1は最初Aに n − 1 個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。

1. 上から n − 2 個目までの円盤を何らかの方法でAからCに移動する。
2. 残った1枚をAからBに移動する。
3. Cにある円盤を何らかの方法でCからBに移動する。

3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける^[3]。

実用的な解法

再帰的でない解き方として、以下のような手順がある^[3]。人間が解く場合にも利用可能である。

• いちばん小さい円盤とそれ以外の円盤を交互に動かす。
• いちばん小さい円盤は常にB→C→A→B(円盤の数が偶数の場合)またはC→B→A→C(円盤の数が奇数の場合)の順に動かす。
• いちばん小さな円盤以外の円盤を動かす場面では、動かせる方法は1通りしかない。

このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2ⁿ − 1 ^[2]手かかる。

棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。

2進数による解析

初期状態から n 回動かした状態は、n の2進数表記から、一意的に求めることができる。

すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下のように求められる。

• n を2進数で書き表す。
• 最上位が一番大きい円盤、以下順に対応し1の位が一番小さい円盤に対応する。
• 最上位が0のとき、一番大きい円盤がまだ動いておらず、1の時には移動済みである。
• 各桁の数字を一つ上の位と比べる。
  1. 同じ値の場合
     • その円盤は一回り大きい円盤の上に乗っている（同じ棒上にある）。
  2. 異なっている場合
     • その数字が0の場合
       • 下から奇数番目の場合、一回り大きい物の右隣にある。
       • 下から偶数番目の場合、一回り大きい物の左隣にある。
     • その数字が1の場合
       • 下から奇数番目の場合、一回り大きい物の左隣にある。
       • 下から偶数番目の場合、一回り大きい物の右隣にある。

ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。

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枚の円盤を移動させるには、最低でも

（2⁶⁴ − 1）回 = 18,446,744,073,709,551,615 回 = 1844京6744兆737億955万1615回

かかり、1枚移動させるのに1秒かかったとすると、最低でも約5,845億年かかる（なお、ビッグバンは今から約137億年前に発生したとされている）。

日本におけるハノイの塔

日本では1907年（明治40年）に書かれた書物世界遊戯法大全で紹介されている。その中では何回移動させればいいかなど数学的考察もしっかり書かれている。

脚注