ハノイの塔

ハノイの塔の模型セット（ディスク8枚付き）

T (4, 3)のハノイの塔パズルのアニメーションによる解答

メキシコシティのユニヴェルサム博物館にあるハノイの塔のインタラクティブ展示

ハノイの塔（ベナレス神殿の問題 [ 1 ] 、ブラフマーの塔、ルーカスの塔 [ 2 ] とも呼ばれ、複数^形では タワー、または単に^{ピラミッドパズル[} 3 ] と呼ばれることもある）は、^3本の棒と、任意の棒にスライドできる様々な直径の円盤からなる数学ゲームまたはパズルである。パズルは、円盤を1本の棒の上にサイズの降順で積み重ね、一番小さい円盤を一番上にして円錐形に近づけることから始まる。パズルの目的は、以下のルールに従って、積み重ねた円盤全体を他の棒の1つに移動させることである。^{[ 4 ]}

1. 一度に移動できるディスクは 1 つだけです。
2. 各移動は、スタックの 1 つから上部のディスクを取り出し、それを別のスタックの上または空のロッドの上に置くことで構成されます。
3. 自分より小さいディスクの上にディスクを置くことはできません。

ディスクが3枚の場合、このパズルは7手で解けます。ハノイの塔パズルを解くのに必要な最小手数は2 ⁿ − 1です（nはディスクの枚数）。

起源

このパズルはフランスの数学者エドゥアール・リュカが考案し、1883年に「N. Claus (de Siam)」（「Lucas d'Amiens」のアナグラム）によって発見されたゲームとして初めて発表され、^{[ 5 ] [ 6 ] [ 7 ]}、後に1889年に小冊子として出版され、 ^{[ 8 ]}リュカの死後に出版されたRécréations mathématiques ^{[ 9 ]}にも収録された。ゲームには説明書が付属しており、ゲームの起源はトンキンにあると説明されており、伝説によればベナレスの寺院のバラモンが64枚の金の円盤からなる「ブラフマーの聖なる塔」をゲームと同じルールで動かしており、塔が完成すると世界の終わりが訪れるとされている。^{[ 10 ]}このパズルの古代の神秘的な性質に関して、この伝説には数多くのバリエーションが存在します。^{[ 5 ]}

1秒間に1回移動する速度で、64枚のディスクを完成させるのにかかる最小時間は2の64乗分の1秒、つまり5850億年となり^{、これは現在}の宇宙の 推定年齢の約42倍に相当します。^{[ 11 ]}

この伝説には様々なバリエーションがあります。例えば、いくつかの物語では、寺院は修道院であり、司祭は修道士です。寺院や修道院はハノイを含む様々な場所にあり、様々な宗教と関連付けられる可能性があります。また、いくつかのバージョンでは、塔が世界の始まりに作られたという事実や、司祭や修道士は1日に1回しか行動できないという事実など、他の要素が取り入れられています。

解決

このパズルはディスクの枚数に関係なく遊ぶことができますが、おもちゃのバージョンでは7枚から9枚程度のものが多くあります。n枚のディスクでハノイの塔パズルを解くのに必要な最小移動回数は2 ⁿ − 1です。^{[ 12 ]}

反復的な解決

6ディスク問題を解く反復アルゴリズムのアニメーション

おもちゃのパズルの簡単な解決法は、最小のピースと最小ではないピースを交互に動かすことです。最小のピースを動かすときは、常に同じ方向（開始時のピースの数が偶数の場合は右、開始時のピースの数が奇数の場合は左）の次の位置に移動します。選択した方向にタワーの位置がない場合は、ピースを反対側の端に移動しますが、その後は正しい方向に動き続けます。たとえば、開始時にピースが3つあった場合、最小のピースを反対側の端に移動し、その後は左方向に動き続けます。最小ではないピースを動かす番になったとき、有効な動きは1つだけです。これを行うと、最小限の動きでパズルを完成させることができます。^{[ 13 ]}

反復解のよりシンプルな記述

反復的な解決法は、目標が達成されるまで、次の一連の手順を繰り返し実行することと同じです。

• 1 枚のディスクをペグ A からペグ B へ、またはその逆に合法的に移動させます。
• 1 枚のディスクをペグ A からペグ C へ、またはその逆に合法的に移動させます。
• 1 枚のディスクをペグ B からペグ C へ、またはその逆に合法的に移動させます。

このアプローチに従うと、ディスクの数が奇数の場合はスタックはペグ B に配置され、偶数の場合はペグ C に配置されます。

再帰的な解決策

4枚のディスクを使ったハノイの塔パズルの再帰解法のイラスト。SVGファイル内の灰色のボタンをクリックすると、展開または折りたたむことができます。

問題を再帰的に解く鍵は、問題がより小さな部分問題の集合に分解できることを認識することです。それぞれの部分問題には、私たちが求めているのと同じ一般的な解法が適用されます。そして、それらの部分問題の解から、ある単純な方法で全体の解が求められます。このようにして生成された部分問題がそれぞれ「小さい」ということは、最終的に基本ケースに到達することを保証します。ハノイの塔の場合：

• ペグにA、B、Cのラベルを付けます。
• nをディスクの総数とし、
• ディスクに 1 (最小、最上部) からn (最大、最下部) までの番号を付けます。

n 個のディスクすべてがペグ間で有効な配置で分散されていると仮定します。ソースペグにm 個のトップ ディスクがあり、残りのディスクはすべてmより大きいため無視しても問題ないと仮定します。スペアペグを使用して、ルールに違反することなく、 m 個のディスクをソース ペグからターゲットペグに移動します。

1. 同じ一般的な解法を用いて、m − 1 個のディスクをソースペグからスペアペグへ移動します。仮定により、規則に違反しません。これにより、ディスクm がソースペグの一番上のディスクになります。
2. ディスクm をソースペグからターゲットペグに移動します。これは、仮定により有効な移動であることが保証されています (単純なステップ)。
3. スペアに置いたばかりのm − 1 個のディスクを、同じ一般的な解決手順でスペアからターゲットペグに移動し、ルールに違反することなくディスクmの上に配置します。
4. 基本ケースは、0 枚のディスクを移動すること (手順 1 と 3)、つまり何もしないことです。これはルールに違反しません。

完全なハノイの塔のソリューションでは、 B をスペア ペグとして使用して、 n 個のディスクをソース ペグ A からターゲット ペグ C に移動します。

このアプローチは数学的帰納法によって厳密な数学的証明を与えることができ、プログラミングを教える際に再帰の例としてよく使用されます。

再帰的解決の論理的分析

多くの数学パズルと同様に、もう少し一般的な問題を解くことで解を見つけるのが容易になります。つまり、 h (高さ) のディスクのタワーを開始のペグf = A (開始) から終了のペグt = C (終了) に移動する方法です。ここで、B は残りの 3 番目のペグであり、t ≠ fと仮定します。まず、ペグの名前の順列に対して問題が対称的であることに注目してください (対称群S ₃ )。ペグAからペグCに移動すると解がわかっている場合は、ペグの名前を変更することで、開始ペグと終了ペグの他のすべての選択に同じ解を使用できます。ディスクが 1 枚しかない場合 (またはディスクがまったくない場合)、問題は簡単です。h = 1 の場合は、ディスクをペグAからペグCに移動します。h > 1 の場合は、移動のシーケンスのどこかで、最大のディスクをペグAから別のペグ、できればペグCに移動する必要があります。この移動が可能なのは、h − 1 個の小さいディスクがすべてペグB上にある場合のみです。したがって、最初にh − 1 個の小さいディスクすべてをAからBに移動する必要があります。次に最大のディスクを移動し、最後にh − 1 個の小さいディスクをペグBからペグCに移動します。最大のディスクの存在は、h − 1 個の小さいディスクの移動を妨げることはなく、一時的に無視できます。これで、問題はh − 1 個のディスクを最初にAからBへ、次にBからCへ、あるペグから別のペグへ移動することに簡約されますが、ペグの名前を変更することで、どちらの場合も同じ方法を使用できます。同じ戦略を使用して、h − 1 の問題をh − 2、h − 3 といった具合に、ディスクが 1 つだけになるまで簡約できます。これは再帰と呼ばれます。このアルゴリズムは、次のように図式化できます。

0からhまでの自然数（ただしhは含まない）を用いて、ディスクの大きさが増加する順にディスクを識別します。したがって、ディスク0が最小のディスク、ディスクh −1が最大のディスクです。

以下は、 h 枚のディスクのタワーをペグAからペグCに移動する手順です。B は残りの 3 番目のペグです。

1. h > 1の場合は、まずこの手順を使用してh − 1個の小さいディスクをペグAからペグBに移動します。
2. これで、最大のディスク、つまりディスクhをペグAからペグCに移動できます。
3. h > 1の場合は、この手順を再度使用して、h − 1個の小さいディスクをペグBからペグCに移動します。

数学的帰納法によって、上記の手順は可能な限り最小の手数を必要とし、生成された解は、この最小の手数で解ける唯一の解であることが容易に証明されます。漸化式を用いると、この解に必要な正確な手数は次のように計算できます。この結果は、ステップ1と3で手数が 、ステップ2で1手数えられることに注目することで得られ、 となります。 ${\displaystyle 2^{h}-1}$ ${\displaystyle T_{h-1}}$ ${\displaystyle T_{h}=2T_{h-1}+1}$

非再帰的な解決策

再帰アルゴリズムによって生成される、あるペグから別のペグへタワーを運ぶための移動リストには、多くの規則性があります。 移動を 1 から数えると、移動m中に移動するディスクの順序数は、 m を2 で割ることができる回数です。したがって、奇数の移動には必ず最小のディスクが関係します。また、最小のディスクは、タワーの高さが奇数の場合はペグf、t、r、f、t、rなどを通過し、タワーの高さが偶数の場合はペグf、r、t、f、r、tなどを通過することもわかります。これにより、再帰アルゴリズムより簡単に、手動で実行できる次のアルゴリズムが得られます。

交互の動き：

• 最も小さいディスクを、最近取り出されていないペグに移動します。
• 別のディスクを合法的に移動します (可能性は 1 つだけです)。

最初の動きでは、最小のディスクは、hが奇数の場合はペグtに移動し、 hが偶数の場合はペグrに移動します。

また、次の点にも注意してください。

• 偶数パリティを持つ序数のディスクは、最小のディスクと同じ方向に移動します。
• 奇数パリティを持つディスクは逆方向に移動します。
• hが偶数の場合、連続移動中に残る 3 番目のペグはt、r、f、t、r、fなどになります。
• hが奇数の場合、連続移動中に残る 3 番目のペグはr、t、f、r、t、fなどになります。

この知識があれば、各ディスクの位置以外の状態情報なしで、最適解の中央にあるディスクのセットを復元できます。

• 上記で説明した動きをディスクの「自然な」動きと呼びます。
• ディスク 0 ではない最小の最上位ディスクを調べ、その唯一の (正当な) 移動が何であるかを書き留めます。そのようなディスクが存在しない場合は、最初の移動か最後の移動のいずれかになります。
• その移動がディスクの「自然な」移動である場合、ディスクは最後のディスク 0 の移動以降移動されていないため、その移動を行う必要があります。
• その移動がディスクの「自然な」移動ではない場合は、ディスク 0 を移動します。

バイナリソリューション

n 枚のディスクからなるパズルのディスクの位置は、移動回数mの2進数表現から直接決定できます。例えば、8枚のディスクからなるハノイの塔のm =216 の移動の詳細は、反復や再帰を必要とせず、また以前の移動やディスクの配置を参照することなく計算できます。逆に、適切なディスクの配置が与えられれば、その配置を達成するための移動回数を計算できます。

ディスクを、大きさが小さくなる順にn、n -1、…、 1 とラベル付けします。ペグA、B、Cをそれぞれ 0、 1、 2 とラベル付けします。0 は常に開始ペグ、2 は常に終了ペグです。さらに、ディスクを積み重ねるペグの台座を、ペグ 0、1、2 に対してそれぞれ n +1、n +2、n +3 とラベル付けします。

移動m後のディスクの位置は、mの2進表現から次の規則でマッピングできる。 ^{[ 14 ]}

• 各ディスクのmには 1 つの 2 進数 (ビット) があります。

• mのビット文字列は左から右に読み取られ、各ビットはディスクnからディスク 1 までの対応するディスクの位置をマップするために使用できます。
• 最上位（左端）ビットは、最大のディスク（ディスクn ）を表します。値が0の場合、最大のディスクは開始ペグ0（A ）にあることを示し、値が1の場合、最終ペグ2（ C ）にあることを示します。
• 移動後:

1. 各ディスクは、別のディスクまたは空のベースに、逆のパリティ順序で積み重ねられます。つまり、5>4>3（3÷4÷5）は有効ですが、5>4>2（2÷4）は無効です。
2. 上部のラベル (ディスク番号または空の基数) のうち 1 つだけが偶数です ( n が偶数の場合。それ以外の場合は 1 つだけが奇数です)。
3. 前の桁と同じ値のビットは、対応するディスクが前のディスクの上に積み重ねられていることを意味します。つまり、1または0の連続したシーケンスは、対応するディスクがすべて同じペグに積み重ねられていることを意味します。

• 前のビットと異なる値を持つビットは、対応するディスクが前のスタックではなく別のペグにあることを意味します。上記1) を考慮すると、残りの2つのペグのうち1つだけが有効な配置となります。最初のディスクセットの配置後、すべての「配置ラウンド」は、可能性のあるペグのうち1つが偶数パリティを持ち、もう1つが奇数パリティを持つ状態で開始および終了することに注意してください。

たとえば、8 枚のディスクからなるハノイの塔の場合:

• 0 = 00000000 に移動します。
  • ディスクの最大のビット (左端) は 0 なので、開始ペグ (0) にあります。
  • 他のディスクもすべて0なので、その上に積み重ねられます。したがって、パズルの初期配置では、すべてのディスクがスタートペグの上にあります。
• 255 ₁₀ (2 ⁸ − 1) = 11111111 を移動します。
  • 最大のディスク ビットは 1 なので、最後のペグ (2) にあります。
  • 他のディスクもすべて1なので、その上に重ねます。つまり、すべてのディスクが最後のペグに収まり、パズルは完成です。
• 216 ₁₀を移動= 11011000。
  • ディスクの最大ビットは1なので、ディスク8は最後のペグ（2）にあります。これは基数11（11>8）にあることに注意してください。
  • ディスク 7 も 1 なので、ディスク 8 の上に積み重ねられます (11>8>7)。
  • ディスク6は0なので、別のペグに置かれます。ペグ1は空ですが、その基数は10です。6のディスクは10の基数（どちらも偶数）には置けません。したがって、ディスク6はペグ0（9>6）に置かれます。
  • ディスク5は1なので、別のペグに置かれます。ペグ2の上に7が置かれているため、ディスク5はそこに置くことができません。したがって、ディスク5はペグ1に置かれます（10>5）。
  • ディスク 4 も 1 なので、ディスク 5 の上に積み重ねられます (10>5>4)。
  • ディスク3は0なので、別のペグに置かれます。ペグ2の上には7が置かれているため、そこに置くことはできません。ディスク3はペグ0に置かれます（9>6>3）。
  • ディスク 2 と 1 も 0 なので、ディスク 3 の上に積み重ねられます (9>3>2>1)。

m番目の移動（移動 0 を除く）の始点と終点のペグは、mのバイナリ表現からビット演算を用いて簡潔に求めることができます。Cプログラミング言語の構文を用いると、m番目の移動は次のようになります 。

ペグから(m & m - 1) % 3ペグへ((m | m - 1) + 1) % 3。

これを別の形で表現すると次のようになります。

ペグから(m - (m & -m)) % 3ペグへ(m + (m & -m)) % 3。

これらは奇数nのパズルに当てはまります。偶数nのパズルの場合は、ペグ1と2への出力参照を逆にする必要があります。

さらに、特定の移動で移動される単一のディスクは、移動カウント ( m ) を 2 (つまり、 mの右側の連続する 0 ビットの数) で割った回数に 1 を加算することで決まります。上記の移動 216 の例では、右側に 3 つの 0 があり、ディスク 4 (3 + 1) がペグ 2 からペグ 1 に移動されます。

グレイコードソリューション

グレイコードの二進法は、このパズルを解く別の方法を提供します。グレイコードでは、数値は0と1の二進法の組み合わせで表現されますが、標準的な位置表記法とは異なり、グレイコードは各値が前の値から1ビットだけ異なるという前提で動作します。

特定のハノイの塔のディスクの数に等しいビット サイズのグレイ コードでカウントする場合、ゼロから始まってカウントアップし、各移動で変更されるビットは移動するディスクに対応します。最下位ビットは最小のディスクであり、最上位ビットは最大のディスクです。

移動を 1 から数え、ディスクを 0 から始まる番号でサイズの大きい順に識別すると、移動m中に移動するディスクの順序は、m を2 で割ることができる回数になります。

この手法では、どのディスクを移動するかは特定しますが、どこに移動するかは特定しません。最小のディスクの場合、常に 2 つの可能性があります。他のディスクの場合、すべてのディスクが同じペグ上にある場合を除き、常に 1 つの可能性があります。ただし、その場合は、移動する必要があるのは最小のディスクであるか、目的がすでに達成されているかのどちらかです。幸いなことに、最小のディスクをどこに移動するかを指定するルールがあります。開始ペグをf 、目的のペグをt、残りの 3 番目のペグを r とします。ディスクの数が奇数の場合、最小のディスクはペグに沿ってf → t → r → f → t → rなどの順序で循環します。ディスクの数が偶数の場合は、これを逆にしてf → r → t → f → r → tなどとする必要があります。 ^{[ 15 ]}

グレイコード解におけるビット変化の位置は、各ステップで移動するディスクのサイズを示します。1、2、1、3、1、2、1、4、1、2、1、3、1、2、1、...（OEISのシーケンスA001511）^{[ 16 ]}は、ルーラ関数としても知られるシーケンス、または移動回数内の2の累乗より1大きい数です。Wolfram言語では、8枚のディスクパズルの移動回数を示します。 IntegerExponent[Range[2^8 - 1], 2] + 1

グラフィカルな表現

このゲームは無向グラフで表すことができ、ノードはディスクの配置、エッジは動きを表します。ディスクが1つの場合、グラフは三角形になります。

2 つのディスクのグラフは、3 つの三角形が接続されて、より大きな三角形の角を形成します。

2つ目の文字は、大きい方のディスクを表すために追加されています。明らかに、最初は動かすことはできません。

一番上の小さな三角形は、2 つのディスクによる 1 つの移動の可能性を表します。

最も外側の三角形の頂点にあるノードは、すべてのディスクが同じペグ上にある分布を表します。

h + 1 個のディスクの場合、h 個のディスクのグラフを取り、それぞれの小さな三角形を 2 個のディスクのグラフに置き換えます。

3 つのディスクの場合のグラフは次のようになります。

レベル 7 のゲーム グラフは、シェルピンスキーの三角形との関連性を示しています。

• ペグをa、b、cと呼ぶ
• ディスクの位置を左から右へサイズの大きい順にリストします

最も外側の三角形の辺は、タワーをあるペグから別のペグへ移動させる最短経路を表しています。最大の三角形の辺の中央にある辺は、最大のディスクの動きを表しています。次に小さい三角形の辺の中央にある辺は、次に小さいディスクの動きを表しています。最も小さい三角形の辺は、最も小さいディスクの動きを表しています。

一般に、 n 枚のディスクがあるパズルの場合、グラフには3 ^{n 個の}ノードがあります。3 つのコーナー ノードを除くすべてのノードには他のノードへのエッジが 3 つあります。コーナー ノードには 2 つのエッジがあります。最小のディスクを他の 2 つのペグのいずれかに移動することは常に可能であり、すべてのディスクが 1 つのペグに積み重ねられている場合を除き、1 つのディスクをそれらの 2 つのペグ間で移動することも可能です。コーナー ノードは、すべてのディスクが 1 つのペグに積み重ねられている 3 つのケースを表します。n + 1 個のディスクの図は、 nディスクの図 の 3 つのコピー(それぞれが新しい最大ディスクの特定の 1 つの位置に対する小さいディスクのすべての状態と動きを表します) を作成し、3 つの新しいエッジでコーナーで結合することで取得されます。これは、最大ディスクを移動できる 3 つの機会のみを表します。したがって、結果の図には 3 ^{n +1}個のノードがあり、2 つのエッジのみを持つ 3 つのコーナーがまだ残っています。

ディスクが追加されるにつれて、ゲームのグラフ表現はフラクタル図形、シェルピンスキーの三角形に似たものになります。最短解法では、パズルのほとんどの局面に到達できないことは明らかです。実際、伝説の司祭たちが最長解法（どの局面にも再訪せずに）を使用した場合、3の64^{乗−1手、つまり10の23}乗年 以上かかることになります。

未使用のエッジを消去することで、3 つのディスクの最長の非反復経路を視覚化できます。

ちなみに、この最長の非反復パスは、aからcへのすべての移動を禁止することによって取得できます。

3 つのディスクの ハミルトン サイクルは次のとおりです。

グラフは次のことを明確に示しています。

• ディスクの任意の分布から、すべてのディスクを 3 つのペグのいずれかに移動する最短の方法が 1 つだけ存在します。
• 任意のディスク分布の各ペア間には、1 つまたは 2 つの異なる最短経路が存在します。
• ディスクの任意の分布から、すべてのディスクを 3 つのペグのいずれかに移動するための、自己交差しない最長のパスが 1 つまたは 2 つあります。
• 任意のディスク分布の各ペア間には、1 つまたは 2 つの異なる最長の非自己交差パスが存在します。
• h枚の円盤からなる塔を1つのペグから別のペグへ 移動させる際に、自己交差しない経路の数をN _hとします。すると、次のようになります。
  • N ₁ = 2
  • N _{h +1} = ( N _h ) ² + ( N _h ) ³

これにより、N _{h は}2、12、1872、6563711232、... となります（OEISのシーケンスA125295）。

バリエーション

リニアハノイ

すべての移動が隣接するペグ間で行われなければならない場合（つまり、ペグA、B、Cが与えられている場合、ペグAとCの間を直接移動できない）、n枚のディスクの山をペグAからペグCに移動するには3 ⁿ − 1回の移動が必要です。この解法では、3 ^{n 個の}有効な位置すべてを使用し、常に前の移動を元に戻さない唯一の移動を行います。すべてのディスクがペグBにある位置は、中間、つまり(3 ⁿ − 1) / 2回の移動後に到達します。^{[ 17 ] [ 18 ]}

サイクリックハノイ

サイクリック・ハノイでは、3つのペグ（A、B、C）が与えられ、それらは円状に配置され、時計回りと反時計回りの方向はそれぞれA – B – C – A、A – C – B – Aと定義されます。円盤の移動方向は時計回りでなければなりません。^{[ 19 ]}移動させる円盤の順序を表せば十分です。解は、2つの相互再帰的な手順を用いて求められます。

n 個のディスクを反時計回りに隣接するターゲット ペグまで 移動するには:

1. n − 1 個のディスクを反時計回りに目標ペグまで移動する
2. ディスク#nを時計回りに1ステップ移動します
3. n − 1 個のディスクを時計回りにスタートペグまで移動します
4. ディスク#nを時計回りに1ステップ移動します
5. n − 1 個のディスクを反時計回りに目標ペグまで移動する

n 個のディスクを時計回りに隣接するターゲット ペグまで 移動するには:

1. n − 1 個のディスクを反時計回りに予備のペグまで移動する
2. ディスク#nを時計回りに1ステップ移動します
3. n − 1 個のディスクを反時計回りに目標ペグまで移動する

C(n)とA(n)がn個のディスクを時計回りと反時計回りに動かすことを表すとすると、両方の式は次のようになります。

	C(n) = A(n−1) n A(n−1)	そして	A(n) = A(n−1) n C(n−1) n A(n−1) です。
したがって	C(1) = 1	そして	A(1) = 1 1,
	C(2) = 1 1 2 1 1	そして	A(2) = 1 1 2 1 2 1 1.

循環ハノイの解には、いくつかの興味深い特性があります。

1. ディスクのタワーをペグから別のペグに移す移動パターンは、中心点に関して対称です。
2. 最も小さいディスクが、最初に移動するディスクと最後に移動するディスクになります。
3. 最小のディスクの移動のグループは、他のディスクの単一の移動と交互になります。
4. C(n)とA(n)で指定されるディスクの移動回数は最小です。

4本のペグ以上

3本のペグを使ったバージョンには単純な再帰的な解法があることは古くから知られていましたが、4本のペグを使ったハノイの塔問題（レーヴのパズルと呼ばれる）の最適解は2014年にBouschによって検証されるまで検証されていませんでした。^{[ 20 ]}

しかし、4つ以上のペグの場合、フレーム・スチュワートアルゴリズムは1941年以来最適性の証明なしに知られています。^{[ 21 ]}

フレーム・スチュワート法（および他の同等の方法）を適用して問題を解くために必要な最小移動数の正確な正式な導出については、次の論文を参照してください。^{[ 22 ]}

4本の釘によるハノイの塔問題のその他のバリエーションについては、ポール・ストックマイヤーの調査論文を参照してください。^{[ 23 ]}

いわゆるブカレストの塔とクラーゲンフルトの塔のゲーム構成は、3進法と5進法のグレイコードを生成します。^{[ 24 ]}

フレーム・スチュワートアルゴリズム

フレーム・スチュワートアルゴリズムについては以下に説明します。

• ディスクの数をとします。${\displaystyle n}$
• をペグの数とします。${\displaystyle r}$
• r 個のペグを使用して n 個のディスクを転送するために必要な最小移動回数として定義します。${\displaystyle T(n,r)}$

アルゴリズムは再帰的に記述できます。

1. いくつかの では、は、移動しながら、先頭のディスクをスタート ペグまたは宛先ペグ以外の 1 つのペグに転送します。${\displaystyle k}$ ${\displaystyle 1\leq k<n}$ ${\displaystyle k}$ ${\displaystyle T(k,r)}$
2. 一番上のディスクが入っているペグを動かさずに、残りのペグだけを使って、残りのディスクを目的のペグに移し、移動します。${\displaystyle k}$ ${\displaystyle nk}$ ${\displaystyle r-1}$ ${\displaystyle T(nk,r-1)}$
3. 最後に、一番上のディスクを移動先のペグに移し、移動します。${\displaystyle k}$ ${\displaystyle T(k,r)}$

全体のプロセスには手数がかかる。したがって、この量が最小となるカウント数を選ぶ必要がある。4ペグの場合、最適解はであり、は最も近い整数関数である。^{[ 25 ]}例えば、UPenn CIS 194 Haskellコースの最初の課題ページ^{[ 26 ]}には、 15枚のディスクと4ペグの場合の最適解が129ステップと記載されており、これは上記のkの値で得られる。 ${\displaystyle 2T(k,r)+T(nk,r-1)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1}$ ${\displaystyle \left\lfloor \cdot \right\rceil }$

このアルゴリズムは、任意の数のペグに対して最適であると推定されます。その移動回数は 2 ^{Θ ( n 1/( r −2) )です (} rは固定)。

一般的な最短経路と466/885という数字

このパズルの本来の目的を一般化すると、すべてのディスクが必ずしも同じペグに載っているとは限らない所定のディスク配置から出発し、最小限の移動回数で別の所定の配置に到達するという興味深い結果になる。一般的に、この問題を解くための最短の移動シーケンスを計算するのは非常に困難である。アンドレアス・ヒンツによって提案された解決策は、最短の移動シーケンスにおいて、移動させる必要のある最大のディスク（もちろん、初期配置と最終配置の両方で同じペグを占める最大のディスクはすべて無視できる）が正確に1回または正確に2回移動するという観察に基づいている。^{[ 27 ]}

この一般化された問題に関連する数学は、ランダムに選択された2つの初期および最終ディスク構成間の最短移動シーケンスにおける平均移動回数を考慮すると、さらに興味深いものになります。ヒンツとチャン・タット・フンは独立して^{[ 28 ] [ 29 ] （ [ 30 ]：第1章、14ページ} も参照 ）nディスクタワーの平均移動回数が以下の正確な式で与えられることを発見しました。

${\displaystyle {\frac {466}{885}}\cdot 2^{n}-{\frac {1}{3}}-{\frac {3}{5}}\cdot \left({\frac {1}{3}}\right)^{n}+\left({\frac {12}{59}}+{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5+{\sqrt {17}}}{18}}\right)^{n}+\left({\frac {12}{59}}-{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5-{\sqrt {17}}}{18}}\right)^{n}.}$

nが十分に大きい場合、第1項と第2項のみがゼロに収束しないため、漸近式 、としてが得られる。したがって、直感的に、 の割合は、ランダムに選択された構成から別のランダムに選択された構成に移行する際に実行する必要がある労力と、すべてのディスクを1つのペグから別のペグに移動させる「最も困難な」長さの経路を横断する難易度との比率を表すと解釈できる。定数466/885の出現に関する別の説明と、最短経路を計算するための新しくいくらか改良されたアルゴリズムは、ロミックによって与えられた。^{[ 31 ]}${\displaystyle 466/885\cdot 2^{n}-1/3+o(1)}$ ${\displaystyle n\to \infty }$ ${\displaystyle 466/885\approx 52.6\%}$ ${\displaystyle 2^{n}-1}$

マグネティック・ハノイ

ハノイの磁気タワーでは、各ディスクには南北の2つの異なる面（通常は「赤」と「青」）があります。ディスクを同じ極同士で置いてはいけません。各ディスクに内蔵された磁石が、この不正な動きを防いでいます。また、ディスクを動かす際は必ず裏返してください。

ハノイの二色の塔の初期構成（n=4）

ハノイの二色の塔

有名なハノイ塔パズルのこのバリエーションは、1988 年 7 月に開催された2ème Championnat de France des Jeux Mathématiques et Logiquesで 3 年生から 6 年生の生徒に提供されました^{。 [ 32 ]}

ハノイの二色の塔の最終構成（n=4）

パズルのルールは基本的に同じです。ディスクはペグ間で1枚ずつ移動します。大きなディスクを小さなディスクの上に置くことはできません。違いは、各サイズごとに2枚のディスク（黒と白）があることです。また、交互に色の異なるディスクの塔が2つあります。パズルの目的は、塔を単色（同じ色）にすることです。塔の底にある最大のディスクの位置が入れ替わると仮定します。

ハノイの塔

このパズルのバリエーションは、9枚のトランプを使ったソリティアゲームとして「ハノイの塔」という名前で採用されている。^{[ 33 ] [ 34 ]}元の名前の綴りが変更されたのは意図的なものか偶然のものかは不明である。^{[ 35 ]}

アプリケーション

ハノイの塔のような構造を持つシリコンウェハ上の多層パラジウムナノシートの3D AFMトポグラフィー画像^{[ 36 ]}

ハノイの塔は、問題解決能力に関する心理学的研究で頻繁に用いられています。また、この課題の派生課題であるロンドン塔は、実行機能障害の神経心理学的診断および治療に用いられています。^{[ 37 ]}

ZhangとNorman ^{[ 38 ]}は、ゲームの同型（等価）表現を複数用いて、タスク設計における表現効果の影響を研究した。彼らは、ゲームコンポーネントの物理的デザインにバリエーションを持たせることで、ゲームルールの表現方法を変えることで、ユーザーのパフォーマンスにどのような影響があるかを実証した。この知見は、人間とコンピュータのインタラクションを表現するためのTURFフレームワーク^{[ 39 ]}の開発に影響を与えた。

ハノイの塔は、複数のテープ/メディアが関係するコンピュータデータのバックアップを実行する際のバックアップローテーションスキームとしても使用されます。 ^{[ 40 ]}

ハノイの塔は、神経心理学者が前頭葉の障害を評価するためのテストとしても使用されています。^{[ 41 ]}

2010年に研究者らは、非線形力学とフェロモン信号を利用して、ハノイの塔問題の3ディスクバージョンを解くことができたという実験結果を発表しました。 ^{[ 42 ]}

2014年、科学者たちはハノイの塔のような構造を持つ多層パラジウムナノシートを合成した。 ^{[ 36 ]}

2025年、アップル社の研究者らはハノイの塔などのパズルを用いてLLM Generative AIプログラムの推論能力をテストした。研究者らは、 ChatGPT、Claude、Deepseekなどの主要なAIモデルが7リングレベルのハノイの塔を解くのに苦労し、精度が80%未満となり、8リングのハノイの塔を解くことは全くできないことを発見した。研究者らがAIモデルに解法アルゴリズムを与えた場合でも、モデルは失敗した。このパフォーマンスに基づき、研究者らは、複雑性が増すとAIシステムが崩壊し、トレーニングデータの分布を超えるタスクを処理できないことを示していると結論付けた。このことは、これらのモデルがAGIレベルに進化できるかどうかにも疑問を投げかけるものである。^{[ 43 ] [ 44 ]}

大衆文化において

エリック・フランク・ラッセルのSF小説『ナウ・インヘイル』では、ある惑星に囚われた人間が登場します。その惑星では、処刑前に勝敗が決まるまでゲームをさせるという慣習があります。主人公は救出船が到着するまで1年以上かかるかもしれないことを承知していたため、64枚のディスクを使った「ハノイの塔」で遊ぶことにしました。この物語は、仏教の僧侶たちが世界の終わりまでゲームを続けたという伝説に言及しています。^{[ 45 ] [ 46 ] [ 47 ]}

1966年のドクター・フーの物語『天空の玩具職人』では、悪役がドクターに10個のピース​​を使い1,023手で積み上げるピラミッド型のハノイの塔のゲーム「トリロジックゲーム」を強制的にプレイさせる。^{[ 46 ] [ 48 ]}

2007年、 『レイトン教授と悪魔の箱』のパズル6、83、84でハノイの塔問題のコンセプトが採用されましたが、ディスクはパンケーキに変更されていました。このパズルは、レストランのシェフが山盛りのパンケーキを片方の皿からもう片方の皿へと移さなければならないというジレンマを題材としており、元のパズルの基本原則（パンケーキを移動できる3枚の皿、大きいパンケーキを小さいパンケーキの上に乗せることができない、など）はそのままに、難問を解くというものでした。

2011年の映画『猿の惑星 創世記』では、このパズルは作中で「ルーカスタワー」と呼ばれ、類人猿の知能を研究するためのテストとして使用されています。^{[ 46 ]}

このパズルはアドベンチャーゲームやパズルゲームで頻繁に登場します。実装が簡単で認識しやすいため、大規模なグラフィックゲーム（例：スター・ウォーズ：旧共和国の騎士、マスエフェクト）のパズルとして用いるのに適しています。^{[ 49 ]}実装によってはディスクそのものを使用するものもありますが、他の形でパズルを隠しているものもあります。セガのアーケード版もあります。^{[ 50 ]}

ゲーム「Sunless Sea」では、このパズルの15枚組バージョンが墓の鍵として登場します。プレイヤーはパズルの各手をクリックして解くことができますが、ゲームでは完成までに32,767手かかると記載されています。特に熱心なプレイヤーがパズルの最後までクリックすると、パズルを完成させても扉が開かないことが明らかになります。

これは2002年のサバイバー・タイランドで初めてチャレンジとして使われましたが、指輪ではなく寺院を模したピースが使われていました。シーアンがパズルの解き方をよく知っていたにもかかわらず、スーク・ジャイはジェドを追い払うためにチャレンジを放棄しました。この問題は、2011年のアメリカ版サバイバーTVシリーズのエピソードで、報酬チャレンジの一部として取り上げられました。プレイヤーのオジー・ラストとベンジャミン・"コーチ"・ウェイドは二人ともパズルの解き方が分からず苦戦し、仲間の仲間に助けられました。

2025年には、このパズルは『ラブ アイランド ゲーム』シーズン 2 の最終回にあるメガ デュエルの冒頭にも登場します。

参照

• ABACABAパターン
• バックアップローテーションスキーム、TOHアプリケーション
• バゲノーディエ
• 再帰（コンピュータサイエンス）
• 「神の90億の名前」、1953年アーサー・C・クラークの短編小説。ゲームの枠組みと似た前提を持つ。

注記

1. "A000225 - OEIS" . oeis.org . 2021年9月3日閲覧。
2. ホフスタッター、ダグラス・R. (1985). 『メタマジカル・テーマ：心とパターンの本質を探る』 ニューヨーク：ベーシックブックス. ISBN 978-0-465-04540-2。
3. Cohn, Ernst M. (1963). 「整数の基本的性質を示すための装置」 . 『数学教師』 . 56 (2). 全米数学教師協会: 84. doi : 10.5951/MT.56.2.0084 . ISSN 0025-5769 . 2021年3月9日閲覧。 
4. Weisstein, Eric W. 「ハノイの塔」 . mathworld.wolfram.com . 2023年10月20日閲覧。
5. ヒンツ、アンドレアス M.;クラヴジャール、サンディ。ミルティノヴィッチ、ウロシュ。ペトル、シリル (2013-01-31)。ハノイの塔 – 神話と数学。スプリンガー。ISBN 978-3034802369。
6. Stockmeyer, Paul K. 「ハノイの塔：参考文献」（PDF） 。 2024年2月21日閲覧。
7. アンリ・ド・パルヴィル (1883-12-27)。「科学レビュー」。議論のジャーナル。2024 年 2 月 21 日に取得。
8. ルーカス、エドゥアール(1889)。Jeux scientifiques pour servir à l'histoire, à l’enseignement et à la pratique du calcul et du dessin (フランス語)。パリ：シャンボン・エ・バイ。2024-01-27に取得。
9. ルーカス、エドゥアール(1892)。Récréations mathématiques (フランス語)。 Vol. 3. アルバート・ブランチャード図書館、1979 年。 58.
10. Stockmeyer, Paul K. 「ハノイの塔の英語による説明、1ページ目」 。 2024年2月21日閲覧。
11. モスコヴィッチ、イヴァン（2001年）『1000のプレイシンク：パズル、パラドックス、イリュージョン＆ゲーム』ワークマン、ISBN 978-0-7611-1826-8。
12. ペトコヴィッチ、ミオドラグ (2009).偉大な数学者たちの有名なパズル. AMS書店. p. 197. ISBN 978-0-8218-4814-2。
13. Troshkin, M. 「終末の日が来る：再帰的ハノイの塔問題の非再帰的分析」Focus（ロシア語）95 (2): 10–14。
14. TR Walsh,ハノイの塔再考：移動回数を数えてリングを動かす, Information Processing Letters, 1982, Vol.15, 64-67. オランダ.
15. ミラー、チャールズ・D. (2000). 「第4章 2進数と標準グレイコード」.数学的アイデア集(第9版). アディソン・ウェスリー・ロングマン. ISBN 978-0-321-07607-62004年8月21日時点のオリジナルよりアーカイブ。
16. グロス、L. (1872)。テオリ・デュ・バゲノディエ。リヨン：エメ・ヴァントリニエ。
17. 「質問コーナー ― ハノイの塔問題の一般化」 math.toronto.edu . 2023年7月28日閲覧。
18. Hinz, Andreas M.; Klavzar, Sandi; Milutinovic, Uros; Petr, Ciril; Stewart, Ian (2013). 『ハノイの塔 ― 神話と数学』（第1版）. バーゼル: Springer Science+Business Media . pp.  241– 259. ISBN 9783034802369。
19. Gedeon, TD (1996). 「ハノイの循環タワー：変換によって生み出される反復的なソリューション」.コンピュータジャーナル. 39 (4): 353– 356. doi : 10.1093/comjnl/39.4.353 .
20. ブッシュ、T. (2014)。「ラ・カトリエム・ツアー・ド・ハノイ」（PDF）。ブル。ベルク。数学。社会サイモン・ステビン21 (5): 895–912。土井: 10.36045/bbms/1420071861。S2CID 14243013。 2017 年 9 月 21 日のオリジナル(PDF)からアーカイブされました。 
21. Stewart, BM; Frame, JS (1941年3月). 「上級問題3819の解答」. American Mathematical Monthly . 48 (3): 216–9 . doi : 10.2307/2304268 . JSTOR 2304268 . 
22. Klavzar, Sandi; Milutinovi, Uro; Petrb, Ciril (2002). 「ハノイの4柱タワーパズルのバリエーション」（追記） . Congressus Numerantium . 102 .
23. ストックマイヤー、ポール (1994). 「ハノイの4柱タワーパズルのバリエーション」（追記） . Congressus Numerantium . 102 : 3–12 .
24. Herter, Felix; Rote, Günter (2018-11-14) [2018-08-09, 2017-12, 2017-08-09, 2016-04-22]. 「ループレス・グレイコード列挙とブカレストの塔」(PDF) .理論計算機科学. 748 . ベルリン、ドイツ: 40– 54. arXiv : 1604.06707 . doi : 10.1016/j.tcs.2017.11.017 . ISSN 0304-3975 . S2CID 4014870 . 2020年12月16日時点のオリジナルよりアーカイブ(PDF) . 2020年12月16日閲覧。  [1]（15/18/19/24ページ）
25. 「トロント大学 CSC148 Slog」 2014年4月5日. 2015年7月22日閲覧。
26. 「UPenn CIS 194 Haskell入門 課題1」（PDF） . 2016年1月31日閲覧。
27. ヒンツ、A. (1989)。 「ハノイの塔」。L'Enseignement Mathématique。35 : 300–303 .土井: 10.5169/seals-57378。
28. Hinz 1989、307ページ。
29. Chan, T. (1988). 「ハノイの塔問題の統計的分析」. Internat. J. Comput. Math . 28 ( 1–4 ): 57–65 . doi : 10.1080/00207168908803728 .
30. スチュワート、イアン (2004). 『Another Fine Math You've Got Me Into..』 クーリエ・ドーバー. ISBN 978-0-7167-2342-4。
31. Romik, D. (2006). 「ハノイの塔グラフと有限オートマトンにおける最短経路」. SIAM Journal on Discrete Mathematics . 20 (3): 610– 622. arXiv : math/0310109 . doi : 10.1137/050628660 . S2CID 8342396 . 
32. Prasad Vithal Chaugule (2015). 「ハノイの二色塔問題の再帰的解法」(PDF) .レクリエーション数学マガジン(4): 37– 48. ISSN 2182-1976 . 
33. アーノルド、ピーター (2003年5月28日). 『Card Games for One』 . スターリング出版社. ISBN 978-0-600-60727-4。
34. ヘッジス、シド・G. (2018年3月6日).みんなの趣味の本. Read Books Ltd. ISBN 978-1-5287-8344-6。
35. 「ハノイの塔 ペイシェンス（別名：ハノイの塔 ペイシェンス）」bbcmicro.co.uk . 2020年10月17日閲覧。
36. Yin, Xi; Liu, Xinhong; Pan, Yung-Tin; Walsh, Kathleen A.; Yang, Hong (2014年11月4日). 「ハノイタワーのような多層超薄パラジウムナノシート」. Nano Letters . 14 (12): 7188–94 . Bibcode : 2014NanoL..14.7188Y . doi : 10.1021/nl503879a . PMID 25369350 . 
37. Shallice, T. (1982-06-25). 「計画機能の特異的障害」 . Philosophical Transactions of the Royal Society of London. B, Biological Sciences . 298 (1089): 199– 209. Bibcode : 1982RSPTB.298..199S . doi : 10.1098/rstb.1982.0082 . ISSN 0080-4622 . PMID 6125971 .  
38. Zhang, J (1994). 「分散認知タスクにおける表現」(PDF) .認知科学. 18 : 87–122 . doi : 10.1016/0364-0213(94)90021-3 .
39. Zhang, Jiajie; Walji, Muhammad F. (2011). 「TURF：EHRユーザビリティの統一フレームワークに向けて」 . Journal of Biomedical Informatics . 44 (6): 1056– 67. doi : 10.1016/j.jbi.2011.08.005 . PMID 21867774 . 
40. Ruiz, Dirk; Newell, Allen (1989-06-01). 「ハノイの塔におけるタワーへの気づきが戦略変更を誘発する：ソアモデル（報告書）」バージニア州フォートベルボア：国防技術情報センター. doi : 10.21236/ada218927 .
41. Beers, SR; Rosenberg, DR; Dick, EL; Williams, T.; O'Hearn, KM; Birmaher, B.; Ryan, CM (1999). 「強迫性障害を有する向精神薬未服用小児の前頭葉機能に関する神経心理学的研究」 .アメリカ精神医学誌. 156 (5): 777–9 . doi : 10.1176/ajp.156.5.777 . PMID 10327915. S2CID 21359382 .  
42. Reid, CR; Sumpter, DJ; Beekman, M. (2011年1月). 「自然システムにおける最適化：アルゼンチンアリがハノイの塔を解く」. J. Exp. Biol . 214 (Pt 1): 50–8 . Bibcode : 2011JExpB.214...50R . CiteSeerX 10.1.1.231.9201 . doi : 10.1242 / jeb.048173 . PMID 21147968. S2CID 18819977 .   
43. ゲイリー・マーカス (2025年6月10日). 「数十億ドル規模のAIが子供でも解けるパズルを解けなくなる時、その誇大宣伝を再考すべき時だ」 .ガーディアン. 2025年11月9日閲覧。
44. Parshin Shojaee、Iman Mirzadeh、Keivan Alizadeh、Maxwell Horton、Samy Bengio、Mehrdad Farajtabar (2025年6月10日). 「思考の錯覚：問題の複雑性というレンズを通して推論モデルの強みと限界を理解する」(PDF) .機械学習研究. 2025年11月9日閲覧。
45. ラッセル、エリック・フランク（1959年4月）「Now Inhale」。中編小説。アスタウンディング・サイエンス・フィクション第63巻第2号。31  ～ 77ページ。
    • 再版：ラッセル、エリック・フランク（2000年）「今、息を吸う」。リック・カッツェ編『メジャー・イングリディエンツ：エリック・フランク・ラッセル選集』、マサチューセッツ州フレーミングハム：NESFAプレス、  399～ 417頁。ISBN 978-1-886778-10-8。
46. ボナノメ, マリアンナ C.; ディーン, マーガレット H.; ディーン, ジュディス・パトナム (2018). 「自己相似群」.注目すべき群のサンプル：トンプソン群、自己相似群、ランプライター群、バウムスラッグ・ソリター群. Compact Textbooks in Mathematics. シャム、スイス：シュプリンガー. p. 96. doi : 10.1007/978-3-030-01978-5_3 . ISBN 978-3-030-01976-1。
47. Birtwistle, Graham (1985年1月). 「Hanoiのコルーチン」. ACM SIGPLAN Notices . 20 (1): 9– 10. doi : 10.1145/988284.988286 . S2CID 7310661 . 
48. 「第4次元：天上の玩具職人」ドクター・フーBBC One 2021年4月2日閲覧。
49. 「ハノイの塔（ビデオゲームのコンセプト）」 Giantbomb.com . 2010年12月5日閲覧。
50. 「ハノイの塔 / アンダミロ」セガ・アミューズメンツ。2012年3月1日時点のオリジナルよりアーカイブ。2012年2月26日閲覧。

外部リンク

• ワイスタイン、エリック W. 「ハノイの塔」。MathWorld 。