ハノイの塔

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

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

ディスクが 3 枚ある場合、パズルは 7 回の移動で解くことができます。ハノイの塔パズルを解くために必要な最小の移動回数は2 ⁿ − 1 回です( nはディスクの数)。

このパズルはフランスの数学者 エドゥアール・リュカスによって発明され、1883年に「N. クラウス（ド・シャム）」（「リュカス・ダミアン」のアナグラム）によって発見されたゲームとして初めて発表され、^{[5] [6] [7]}、後に1889年に小冊子として出版され、 ^[8]リュカスの死後に出版された「数学の再現」の書籍にも収録された。^[9]ゲームには説明書が付属しており、ゲームの起源はトンキンにあると説明されており、伝説によればベナレスの寺院のバラモンが、ゲームと同じルールに従って、64枚の金の円盤からなる「ブラフマーの聖なる塔」を動かしており、塔が完成すると世界の終わりが訪れるとされている。^[10]このパズルの古代の神秘的な性質に関する伝説のさまざまなバリエーションがすぐに現れました。^[5]

もし伝説が真実で、僧侶たちが最小の移動回数で1秒間に1枚の速度で円盤を動かすことができたとしたら、完了するまでに2の^64乗 −1秒、つまりおよそ5850億年かかることになり、^{[11]これは現在の}宇宙の推定年齢の約42倍に相当します。

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

このパズルは任意の数のディスクで遊ぶことができますが、おもちゃのバージョンでは7〜9枚のディスクが使われています。n枚のディスクでハノイの塔パズルを解くのに必要な最小移動回数は2 ⁿ − 1です。^[12]

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

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

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

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

問題を再帰的に解決する鍵は、問題がより小さなサブ問題の集合に分解できることを認識することである。それぞれのサブ問題には、私たちが求めているのと同じ一般的な解決手順が適用され^{[引用が必要]}、そして全体的な解決策はそれらのサブ問題の解決策から何らかの簡単な方法で見つかる。作成されたサブ問題のそれぞれが「より小さい」ということは、最終的に基本ケースに到達することを保証する。ハノイの塔の場合:

• ペグに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までの自然数でサイズの大きい順にディスクを識別します。したがって、ディスク 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 を移動します。

ディスクの位置は、次の規則を使用して、移動番号のバイナリ(基数 2) 表現 (初期状態は移動番号 0、すべての数字が 0、最終状態はすべての数字が 1) から直接決定できます。

• 各ディスクには1 つの 2 進数 (ビット)があります。
• 最上位 (左端) ビットは、最大のディスクを表します。値 0 は、最大のディスクが最初のペグにあることを示し、値 1 は、最後のペグ (ディスクの数が奇数の場合は右のペグ、そうでない場合は中央のペグ) にあることを示します。
• ビット文字列は左から右に読み取られ、各ビットを使用して対応するディスクの位置を判別できます。
• 前のビットと同じ値を持つビットは、対応するディスクが同じペグ上の前のディスクの上に積み重ねられていることを意味します。

  (つまり、1 または 0 が連続して並んでいる場合、対応するディスクがすべて同じペグ上にあることを意味します。)

• 前のビットと異なる値を持つビットは、対応するディスクが前のビットの 1 つ左または右の位置にあることを意味します。左か右かは、次の規則によって決定されます。
  • 最初のペグが左側にあると仮定します。
  • また、「ラッピング」も想定します。つまり、右のペグは左のペグの 1 つ「左」のペグとしてカウントされ、その逆も同様です。
  • n を、最初の大きいディスクと同じペグに配置されている大きいディスクの数とし、最大のディスクが左のペグにある場合は 1 を加えます。n が偶数の場合、ディスクは 1 ペグ右に配置され、nが奇数の場合、ディスクは 1 ペグ左に配置されます (ディスクの数が偶数の場合、そうでない場合はその逆)。

たとえば、8 ディスクの Hanoi の場合:

• 0 = 00000000 に移動します。
  • 最大のディスクは 0 なので、左 (初期) のペグにあります。
  • 他のディスクもすべて 0 なので、その上に積み重ねられます。したがって、すべてのディスクは最初のペグ上にあります。
• 2 ⁸ − 1 = 11111111を移動します。
  • 最も大きいディスクは 1 なので、中央 (最終) のペグにあります。
  • 他のディスクもすべて 1 なので、その上に積み重ねられます。したがって、すべてのディスクが最後のペグに配置され、パズルが完成します。
• 216 ₁₀ = 11011000 に移動します。
  • 最も大きいディスクは 1 なので、中央 (最終) のペグにあります。
  • ディスク 2 も 1 なので、その上の中央のペグに積み重ねられます。
  • ディスク 3 は 0 なので、別のペグにあります。nは奇数 ( n = 1) なので、1 つ左のペグ、つまり左のペグにあります。
  • ディスク 4 は 1 なので、別のペグにあります。n は奇数 ( n = 1) なので、1 つ左のペグ、つまり右のペグにあります。
  • ディスク 5 も 1 なので、右側のペグにその上に積み重ねられます。
  • ディスク 6 は 0 なので、別のペグにあります。nは偶数 ( n = 2) なので、ディスクは 1 つ右のペグ、つまり左のペグにあります。
  • ディスク 7 と 8 も 0 なので、左のペグの上に積み重ねられます。

m番目の移動のソース ペグと宛先ペグも、ビット演算を使用してmのバイナリ表現から簡単に見つけることができます。Cプログラミング言語の構文を使用すると、移動mはペグからペグへとなり、ディスクはペグ 0 から始まり、ディスクの数が偶数か奇数かに応じてペグ 1 または 2 で終了します。別の表現は、ペグからペグへです。 (m & m - 1) % 3((m | m - 1) + 1) % 3(m - (m & -m)) % 3(m + (m & -m)) % 3

さらに、移動するディスクは、移動回数 ( m ) を 2 で割った回数 (つまり、右側のゼロ ビットの数) によって決定されます。最初の移動を 1 としてカウントし、ディスクをサイズの大きい順に 0、1、2 などの番号で識別します。これにより、非常に高速な非再帰的なコンピューター実装により、以前の移動やディスクの分布を参照せずに、m 回の移動後のディスクの位置を見つけることができます。

2進数の末尾の連続するゼロの数を数えるこの操作は、問題に対する簡単な解決策を提供します。ディスクはゼロから番号が付けられ、移動mで、ディスク番号カウントの末尾のゼロが右に可能な限り最小の距離だけ移動されます（必要に応じて左に戻ります）。^[14]

グレイ コードの 2 進数システムは、パズルを解く別の方法を提供します。グレイ システムでは、数字は 0 と 1 の 2 進数の組み合わせで表現されますが、標準的な位置数システムではなく、グレイ コードは、各値が前の値と 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 つのディスクの場合のグラフは次のようになります。

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

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

一般に、 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とします。
  • ₁ = 2です
  • Nh ₊₁ ⁼ ( Nh ₎ ² + ( Nh ₎ 3_です

これにより、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 個のディスクを時計回りと反時計回りに動かすことを表すとすると、両方の式を次のように書き表すことができます。

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

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

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 n-k}$${\displaystyle r-1}$${\displaystyle T(n-k,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(n-k,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は固定)。

パズルの本来の目的を一般化すると、すべてのディスクが同じペグに載っているとは限らない特定のディスク配置から始めて、最小の移動回数で別の特定の配置に到達するという興味深いものになります。一般に、この問題を解決するための最短の移動シーケンスを計算するのは非常に困難です。Andreas Hinz によって提案された解決策は、最短の移動シーケンスでは、移動する必要がある最大のディスク (もちろん、最初の配置と最後の配置の両方で同じペグを占める最大のディスクはすべて無視できます) が正確に 1 回または正確に 2 回移動するという観察に基づいています。

この一般化された問題に関連する数学は、ランダムに選択された2つの初期および最終ディスク構成間の最短移動シーケンスの平均移動回数を考えると、さらに興味深いものになります。HinzとChan Tat-Hungは独立して、nディスクタワーの平均移動回数が次の正確な式で与えられることを発見しました^{[27] [28]}（ ^{[29] ：第1章、p. 14}も参照）。

${\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 項のみが 0 に収束しないため、漸近式: 、として が得られる。したがって、直感的に、 の分数は、ランダムに選択された構成から別のランダムに選択された構成に移行するときに実行する必要がある労力と、すべてのディスクを 1 つのペグから別のペグに移動させる「最も困難な」長さの経路を横断しなければならない難しさの比率を表すと解釈できる。定数 466/885 の出現に関する別の説明と、最短経路を計算するための新しい、いくらか改良されたアルゴリズムは、Romik によって与えられた。^[30]${\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 つの異なる面があります (通常は「赤」と「青」に色付けされています)。ディスクは、同じ極同士がくっつくように配置しないでください。各ディスクの磁石がこの不正な動きを防止します。また、各ディスクは移動時に裏返す必要があります。

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

パズルのルールは基本的に同じです。ディスクはペグ間で 1 枚ずつ移動します。大きいディスクを小さいディスクの上に置くことはできません。違いは、サイズごとに 2 つのディスク (黒と白) があることです。また、交互に色を塗ったディスクの塔が 2 つあります。パズルの目的は、塔をモノクロ (同じ色) にすることです。塔の一番下にある最大のディスクの位置が入れ替わると想定されます。

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

ハノイの塔は問題解決に関する心理学的研究で頻繁に利用されている。また、この課題の変種であるロンドン塔も存在し、実行機能障害の神経心理学的診断と治療に用いられる。^[36]

張とノーマン^[37]は、ゲームの同型（等価）表現をいくつか使用して、タスク設計における表現効果の影響を研究した。彼らは、ゲームコンポーネントの物理的設計のバリエーションを使用して、ゲームのルールの表現方法を変更することで、ユーザーのパフォーマンスに影響を与えることを実証した。この知識は、人間とコンピューターの相互作用を表現するためのTURFフレームワーク^[38]の開発に影響を与えた。

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

上で述べたように、ハノイの塔はプログラミング初心者に再帰アルゴリズムを教えるのに人気があります。このパズルの図解バージョンは、Mx hanoi と入力してアクセスできる emacs エディタにプログラムされています。Prologで書かれたサンプルアルゴリズムもあります。^{[引用が必要]}

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

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

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

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

1966年のドクター・フーの物語『天空の玩具屋』では、同名の悪役がドクターに、積み重ねるとピラミッド型になる10個のピース​​、1,023回の手数を持つ「ハノイの塔」ゲーム「トリロジックゲーム」を強制的にプレイさせる。^{[42] [44]}

2007 年、ハノイの塔問題のコンセプトは『レイトン教授と悪魔の箱』のパズル 6、83、84 で使用されましたが、ディスクはパンケーキに変更されていました。このパズルは、レストランのシェフが、元のパズルの基本原理 (つまり、パンケーキを移動できる 3 つの皿、大きいパンケーキを小さいパンケーキの上に置くことができない、など) に基づいて、パンケーキの山を 1 つの皿から別の皿に移動しなければならないというジレンマに基づいています。

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

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

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

これは2002年のサバイバータイランドで初めてチャレンジとして使われましたが、リングではなく、寺院に似たピースが作られました。シーアンがパズルの完成方法を十分に知っていたにもかかわらず、スーク・ジャイはジェドを追い払うためにチャレンジを投げました。この問題は、サバイバーTVシリーズのアメリカ版の2011年のエピソードで報酬チャレンジの一部として取り上げられました。両方のプレーヤー（オジー・ラストとベンジャミン・「コーチ」・ウェイド）はパズルの解き方を理解するのに苦労し、仲間の部族のメンバーに助けられました。

Genshin Impactでは、このパズルは Faruzan のハングアウト クエスト「早期学習メカニズム」で紹介されており、彼女はこれをメカニズムとして見て、子供向けのおもちゃのプロトタイプを作成するために使用していると述べています。彼女はこれをパゴダスタックと呼んでいます。

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

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