ハノイの塔

このおもちゃのパズルを解く簡単な方法は、1) 一番上のピースを動かすことと、2) 別のピースを動かすことを交互に行うことです。

1. 上部を動かすときは、常に同じ方向に次の位置へ移動させます。これは、最初のピースの数が偶数の場合は右方向、奇数の場合は左方向です。

私たちは、塔が円形に並んでいる、あるいはパズルの図が水平方向に一周している、つまり最初の塔から左に移動すると3番目の塔に、3番目の塔から右に移動すると最初の塔に戻ってくる、と想像します。

つまり、ステップ1、3、5、7…では、ピースの数が偶数の場合はA > B > C > A…の順に、ピースの数が奇数の場合はA > C > B > A…の順に上部を配置します。

2 の場合、別の駒を動かすときは、常に合法な動きは 1 つだけです。なぜなら、どの駒も最小の駒の上に移動させることはできず、他の駒の任意の組み合わせのうち、1 つだけが他の駒に合うからです。

ステップ1、2、1、2、…を正しく実行すれば、最小の手数でパズルを完成させることができます。^{[ 13 ]}

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

• ペグにA、B、C、
• nをディスクの総数とし、
• ディスクに1（最小、最上段）からn（最大、最下段）までの番号を振ってください。

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

1. 同じ一般的な解決手順に従って、 m − 1 枚のディスクをソースから予備のペグに移動します。ルールは違反されないものとします。これにより、ディスクm がソースのペグの最上部のディスクとして残ります。
2. ディスクmをソースペグからターゲットペグに移動します。これは、仮定により有効な移動であることが保証されています。これは簡単な手順です。
3. 先ほど予備のディスクの上に置いたm − 1 枚のディスクを、同じ一般的な解決手順に従って、予備のディスクから目標のペグに移動させ、ルールに違反することなくディスクmの上に配置します。
4. 基本ケースは、ディスクを0枚移動すること（ステップ1と3）、つまり何も行わないことであり、これは規則に違反しません。

完全なハノイの塔の解法では、n 枚の円盤を始点の杭 A から終点の杭 C に移動させ、B を予備の杭として使用します。

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

n 枚のディスクを使ったパズルにおけるディスクの位置は、移動番号mの二進数表現から直接求めることができます。例えば、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のバイナリ表現から次の規則に従ってマッピングできます。^{[ 14 ]}

• mには、ディスクごとに1 つのバイナリ数字 (ビット) があります。

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

1. 各ディスクは、パリティの順序を逆にして、別のディスクまたは空のベースの上に積み重ねられます。つまり、5>4>3（3が4の上にあり、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 になります。
  • ディスク8の最大のビットは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はペグ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の右側に連続するゼロビットの数) に 1 を加えた数によって決定されます。上記の例では、移動 216 の場合、右側に 3 つの 0 があるため、ディスク 4 (3 + 1) がペグ 2 からペグ 1 に移動します。

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

特定のハノイの塔の円盤の数に等しいビットサイズのグレイコードで数える場合、ゼロから始めて数え上げていくと、各移動で変化するビットは移動する円盤に対応し、最下位ビットは最小の円盤、最上位ビットは最大の円盤に対応する。

1から数えて、ディスクを0から始まる番号で大きさの順に識別すると、 m回目の移動で移動するディスクの順序数は、 mを2で割り切れる回数になります。

この手法では、どのディスクを移動させるかは特定できますが、どこに移動させるかは特定できません。最小のディスクの場合、常に 2 つの可能性があります。他のディスクの場合、すべてのディスクが同じペグにある場合を除き、常に 1 つの可能性がありますが、その場合は、最小のディスクを移動させるか、目的がすでに達成されているかのどちらかです。幸いなことに、最小のディスクをどこに移動させるかを示すルールがあります。f を開始ペグ、tを目的地ペグ、rを残りの 3 番目のペグとします。ディスクの数が奇数の場合、最小のディスクは、 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

すべての移動が隣接するペグ間で行われる必要がある場合（つまり、ペグ 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と定義される円形に配置されます。ディスクの移動方向は時計回りでなければなりません。^{[ 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枚の円盤を時計回りと反時計回りに動かすものとすると、以下の2つの式を記述できます。

巡回ハノイ問題の解には、いくつかの興味深い特性がある。

1. 円盤の塔をある杭から別の杭へ移動させる際の移動パターンは、中心点に関して対称である。
2. 最も小さい円盤が、最初と最後に動く円盤となる。
3. 最小サイズの円盤のグループによる動きと、他の円盤の単独の動きが交互に繰り返される。
4. C(n)とA(n)で指定されるディスクの移動回数は最小である。

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

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

Frame–Stewartアルゴリズム（およびその他の同等の方法）を適用して問題を解決するために必要な最小移動回数の正式な導出については、次の論文を参照してください。^{[ 22 ]}

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

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

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

この一般化された問題に関連する数学は、ランダムに選択された 2 つの初期ディスク構成と最終ディスク構成間の最短移動シーケンスにおける平均移動数を考慮すると、さらに興味深いものになります。Hinz と Chan Tat-Hung は独立して^{[ 28 ] [ 29 ]} ( ^{[ 30 ] :第 1 章、p. 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項のみがゼロに収束しないため、漸近式が得られます。${\displaystyle 466/885\cdot 2^{n}-1/3+o(1)}$、 として${\displaystyle n\to \infty }$したがって、直感的に、この割合を解釈することができます。${\displaystyle 466/885\approx 52.6\%}$これは、ランダムに選択された構成から別のランダムに選択された構成へ移動する際に実行しなければならない作業の比率を、長さの「最も困難な」経路を横断しなければならない難易度と比較したものである。$2^n-1$これは、すべてのディスクを1つのペグから別のペグに移動させることを伴う。定数466/885の出現に関する別の説明と、最短経路を計算するための新しくやや改良されたアルゴリズムは、Romikによって提示された。^{[ 31 ]}

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

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

パズルのルールは基本的に同じで、ディスクはペグ間で1枚ずつ移動されます。大きいディスクを小さいディスクの上に置くことはできません。違いは、各サイズごとに2枚のディスク（黒と白）があることです。また、交互に色が変わるディスクのタワーが2つあります。パズルの目的は、タワーを単色（同じ色）にすることです。タワーの一番下にある最大のディスクは、位置を交換するものと想定されています。

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