ハノイの塔のアルゴリズム

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

どこを見るか

• 役割が入れ替わる。塔Bは最初の呼び出しにとっては予備で、その呼び出しが作る呼び出しにとっては移動先です。再帰の段ごとに3本の塔が付け替えられ、その付け替えこそがすべての仕掛けです。
• スタックは深くならない。3枚のとき、同時に走っている呼び出しは最大でも4個——3から0までの枚数ごとに1つ——です。プログラム全体では15個の呼び出しをするのに。
• 半分の呼び出しは何もしない。その15個のうち8個は円盤0枚の呼び出しで、すぐ戻ります。いちばん単純な基底の場合を選んだ代金です。
• 動かす行はちょうど 2ⁿ − 1 回実行される。3枚なら7回、実行全体の43ステップの中で。

1つ目は、プログラムが動いている最中にはいちばん気づきにくいものです。それが起きても盤面では何も動かず、塔の下の名前が変わるだけだからです。ここでは静止させてあります。最初の呼び出し、1手目までの途中にある2つ、そして山を戻す呼び出しです。

1. hanoi(3, A, C, B)

   最初の呼び出し：3枚すべてをAからCへ移します。残るBが予備になります。 移動元A、移動先C、予備B。

2. hanoi(2, A, B, C)

   その最初の呼び出し。円盤3は、上に円盤1と2が載ったままでは動けず、その2枚は円盤3が向かうCへは行けません。だから、少し前まで予備だったBが移動先になり、Cが予備になります。 移動元A、移動先B、予備C。

3. hanoi(1, A, C, B)

   1段下がって、同じ入れ替えがもう一度。円盤2の上を空けるため、円盤1がCへ行き、Bがまた予備になります。 移動元A、移動先C、予備B。

4. hanoi(2, B, C, A)

   円盤3は渡り終えました。根の2つ目の呼び出しが、円盤1と2をBからその上へ戻します。だから今度はBが移動元で、すべての円盤が最初にあったAが予備です。 移動元B、移動先C、予備A。

2つ目は、確かめるより疑うほうが簡単です。そこで、実行全体をスタックの高さつきで示します。

• この実行は43ステップで、呼び出しは全部で15回です。
• スタック上の呼び出し数は0と4のあいだで増減し、そのうち8ステップで4に達します。動かす円盤のない呼び出しが始まって戻るたびです。
• 深さ4は n = 3 のときの n + 1 で、実行のどのステップもそれを超えません。

再帰木

それぞれの呼び出しを、それを作った呼び出しの下に置いた箱として描くと、プログラムは木になります。さらに各箱を、その呼び出しが行う手の番号の上に置くと、別のことが見えてきます。箱を左から右へ読むと、手が順番に並ぶのです。3枚なら、最初の呼び出し自身の手——いちばん大きい円盤——はちょうど真ん中の4手目で、その両側に2枚ぶんの3手の解がそのまま並びます。

1. 1手目：n = 1の呼び出し（AからCへ）が円盤1を動かします。
2. 2手目：n = 2の呼び出し（AからBへ）が、n = 1の2つの呼び出しの間で円盤2を動かします。
3. 3手目：n = 1の呼び出し（CからBへ）が円盤1を動かします。
4. 4手目：n = 3の呼び出し（AからCへ）が、n = 2の2つの呼び出しの間で円盤3を動かします。
5. 5手目：n = 1の呼び出し（BからAへ）が円盤1を動かします。
6. 6手目：n = 2の呼び出し（BからCへ）が、n = 1の2つの呼び出しの間で円盤2を動かします。
7. 7手目：n = 1の呼び出し（AからCへ）が円盤1を動かします。

この対称性はどの枚数でも成り立ちます。2ⁿ⁻¹手目はいつでもいちばん大きい円盤が渡る手で、その前後は(n − 1)枚の解を2回、2本の塔の役割を入れ替えて並べたものです。どんなに長い手順でも一目で読めるのはそのためで、5枚の解が「4枚の解・1手・4枚の解」になっているのもそのためです。

なぜ正しいのか

このアルゴリズムはルールを破らず、必ず終わります。その証明は全部書けるほど短いものです。すべてのnについて、主張はこうです。

移動元の塔の上から n 枚が円盤 1 から n であり、ほかのどこにある円盤も n より大きいなら、hanoi(n, source, target, spare) はその n 枚を移動先へ、ルールを守って移し、ほかには何も触らない。

n = 0 のとき、動かすものは何もなく、何にも触れません。

n − 1 について主張が成り立つとします。すると3つの段階はどれもルールを守っています。

1. 最初の呼び出しが円盤1からn − 1を予備の塔へ移します。その資格があります。ほかのどの円盤も、円盤nを含めて、n − 1より大きいからです。
2. 円盤nが移動先へ動きます。いま上には何もなく、移動先にはnより大きい円盤しかありません。
3. 2つ目の呼び出しが円盤1からn − 1を予備から移動先へ移します。資格がある理由は同じで、いまその下にある円盤nのほうが大きいからです。

n枚すべてが移動先にあり、ほかは何も動いていません。数学的帰納法により、主張はすべてのnで成り立ちます。パズル全体は、移動元にすべての円盤がある場合にあたります。

1. 仮定n − 1 についての主張

   仮定は、n − 1枚に対する呼び出しが、言われたところへそれらをルールどおりに移し、ほかには何も触らない、というものです。ここに当てはめると、円盤1からn − 1を移動元から予備の塔へ運びます。その資格はあります。置く可能性のあるどの円盤も——円盤nを含めて——運んでいるどの円盤より大きいからです。

2. ここで証明1手の正しい移動

   証明が自分で論じなければならない段階はここだけで、しかも1手です。円盤nの上は、前の段階で空きました。移動先にはnより大きい円盤しかありません。小さいものはすべて予備の塔にあるからです。だからこの手は正しい手です。

3. 仮定n − 1 についての主張、もう一度

   同じ仮定をもう一度使い、円盤1からn − 1を予備から移動先へ運びます。正しい理由は前と同じで、いまその下にある円盤nのほうが大きいからです。n枚すべてが移動先にあり、ほかは何も動いていません。これが n についての主張です。

漸化式を正しく解く

T(n)を、n枚のときにアルゴリズムが行う手数とします。この関数はn − 1枚に対する呼び出しを2回と、自分自身の1手を行い、円盤がないときは1手も行いません。

解くには、漸化式を自分自身に代入してパターンを探します。これを展開、またはテレスコーピングと呼びます。

パターンを見つけることは証明ではないので、帰納法で確かめます。T(0) = 0 = 2⁰ − 1。そして T(n − 1) = 2ⁿ⁻¹ − 1 なら、T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1。閉じた式はすべてのnで厳密に成り立ちます。

3つ目の道もあり、それはすでに見た絵です。上の再帰木は完全二分木です。根はn枚を動かし、その下の2つの呼び出しはそれぞれn − 1枚、そのまた下の4つはn − 2枚、と続きます。したがって深さkには2ᵏ個の呼び出しがあり、最下層は深さn − 1で、そこにある呼び出しはどれもちょうど1手を行います。各層を足し合わせると、手数は等比級数として出てきます。

展開、帰納法、木——3つの方法で答えは1つ。これを知っておく価値があるのは、しきりに勧められる4つ目の方法があり、そしてそれが間違っているからです。

同じ計算で呼び出しの数も数えられます。n {">"} 0 のどの呼び出しもさらに2つの呼び出しを作るので、C(n) = 2C(n − 1) + 1、C(0) = 1 となり、展開すると 2ⁿ⁺¹ − 1。これは、円盤を動かす 2ⁿ − 1 個の呼び出しと、すぐ戻る 2ⁿ 個の呼び出しの合計です。

時間と空間の計算量

どの呼び出しも、2つの再帰呼び出し以外には定数時間の仕事しかしません。したがって実行時間は呼び出しの数に比例し、Θ(2ⁿ)です。どんなに賢いアルゴリズムでもこれを下回れません。出力そのものが 2ⁿ − 1 手の長さで、しかも 2ⁿ − 1 は「いまのところの最良」ではなく証明された最小だからです。これより短い解がないことの証明には専用のページがあります：なぜ最小が 2ⁿ − 1 なのか。

メモリは話が別です。呼び出しは全部が同時に存在するわけではありません。ある呼び出しは、その兄弟が始まる前に終わるので、スタックには各段につき1つ、nから0までしか載りません。使う空間はΘ(n)——伝説の64枚ならスタックフレームが65個で、どんな計算機も何とも思わない量です。尽きるのは時間のほうです。18,446,744,073,709,551,615手を1秒に10億手で進めても、なお584年かかります。

その数字は伝説のもので、その伝説は見かけより若いものです。64枚の黄金の円盤を僧たちが動かし、終わったときに世界が終わるという寺院の話が初めて印刷に現れるのは1884年、前年にパリで売り出されたパズルを宣伝する記事の中で、しかも実在しない教授の名前でのことでした。僧たちの速さ、1秒に1手なら、世界にはまだ5,850億年残っています。いまの宇宙の年齢のおよそ40倍です。パズルと物語の両方を作った数学者はエドゥアール・リュカで、2¹²⁷ − 1 が素数であることを手計算で示し、宴席で給仕が落とした皿による切り傷から感染症にかかり、49歳で亡くなりました。

この式に数字を入れると、2種類のコストははっきり分かれます。円盤を1枚足すごとに手数と呼び出しは倍を少し超えて増え、スタックの最大の深さは1つ増えるだけです。

最少手数の計算機は、どんな枚数でも手数と時間を出します。最後の行——伝説の枚数——には専用のページがあります。

再帰を使わずに

同じ手順は、2つの規則を持つただのループでも作れます。

• 奇数番目の手：いちばん小さい円盤を、決まった向きに1つ隣の塔へ動かす。枚数が奇数なら A → C → B、偶数なら A → B → C。
• 偶数番目の手：いちばん小さい円盤に触らない唯一の正しい手を指す。そういう手は必ずちょうど1つあります。

この2つの規則は、再帰の解を手ごとにそのまま再現します。反復による解法のページが理由を示し、盤面の上で再生します。

塔をまったく保持しない、もっと奇妙な版もあります。m手目の円盤・移動元・移動先は、どれもmの2進表記から読み取れるのです。そのつながりと、その中に隠れているグレイコードは、ハノイの塔・2進数・グレイコードにあります。

途中の配置から始める

教科書どおりの関数は、すべての円盤が移動元の塔にあることを前提にしています。途中まで進んだパズルを渡しても、何も言うことがありません。場合をもう1つ足せば直ります。いちばん大きい円盤を見てください。

• すでに目標の塔にある？その円盤に必要な手はありません。より小さい円盤を、同じ塔へ送るつもりで解きます。
• ほかの場所にある？より小さい円盤を、いまいる塔でも行き先でもない塔へどかし、その円盤を動かして、あとは前と同じように続けます。

この版はどんな正しい配置からでも最短の解を見つけます。ハノイの塔のソルバーが動かしているのが、まさにこれです。

確かめてみる

このページがすでに答えた3つの問いです。開く前に自分で考えてみてください。出てこなければ、答えに書かれている節がもう一度読むべきところです。

1. 3枚は7手です。では5枚は何手で、そのうち円盤5自身を動かすのは何手でしょう。

   答えを見る

   31手、つまり 2⁵ − 1 です。そしてそのうち、いちばん大きい円盤を動かすのはちょうど1手です。いちばん大きい円盤以外はどれも複数回動きます。解の2つの半分が、それぞれその円盤を動かさなければならないからです。 漸化式を正しく解く.

2. hanoi(3, A, C, B) は最初の呼び出しとして hanoi(2, A, B, C) を作ります。なぜその呼び出しの移動先は C ではなく B なのでしょう。

   答えを見る

   円盤3がCへ行くからです。そしてCが空いていなければ、そこには置けません。だから上の2枚はどこか別の場所に預けるしかなく、その別の場所はBだけです。ある呼び出しが狙っている塔は、その呼び出しが作る最初の呼び出しが空けておかなければならない塔になります。だから3つの引数のうち2つが、入るときに入れ替わるのです。 どこを見るか.

3. 20枚を解くと2,097,151回の呼び出しをします。そのうち同じ瞬間にスタックに載っているのは、最大で何個でしょう。

   答えを見る

   21個です。20から0までの枚数ごとに1つずつ。ある呼び出しは兄弟が始まる前に終わるので、呼び出しが全部同時に存在することはありません。仕事は指数的でも、メモリは線形です。 時間と空間の計算量.

あなたの言語でのアルゴリズム

同じ関数を6つの言語で。それぞれに実行できるプログラム、1行ずつの解説、隣で動く盤面、そしてその言語ならではの事情がついています。64枚の手数を数えようとした瞬間に、その事情が効いてきます。この6ページは英語です。

• Pythonのハノイの塔ENRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• JavaScriptのハノイの塔ENWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Javaのハノイの塔ENWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Cのハノイの塔ENUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• C++のハノイの塔ENCollecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• C#のハノイの塔ENTop-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

このページの用語

基底の場合

再帰関数が、自分を呼ばずにそのまま答えを返す版のこと。再帰を止めるのがこれです。ここでは n = 0：動かす円盤がないので、することはなく、呼び出しは戻ります。どれだけ深い呼び出しの連なりも、最後はここで終わります。

再帰の場合

基底の場合以外のすべて。同じ問題の小さい版を解き、その答えから自分の答えを組み立てる部分です。ここでは、n − 1枚をどかし、円盤nを動かし、そのn − 1枚を戻す、という3行がそれにあたります。

コールスタック

始まってまだ終わっていない関数呼び出しの並びで、新しいものほど後ろにあります。呼び出しは始まるときに積まれ、戻るときに外されます。つまりスタックは、プログラムが「どこへ戻るか」を覚えておく仕組みです。上のパネルが描いているのがこれで、実際のメモリでもあります。だからその深さがアルゴリズムの空間コストになります。

スタックフレーム

コールスタックの1つぶん。ある1回の呼び出しに属する引数とローカル変数のことです。パネルのスタックの各行が1つのフレームで、その呼び出し自身の n と、どの塔が移動元・移動先・予備かという自分なりの見方を持っています。64枚には65個のフレームが要りますが、それは何でもありません。問題は手数のほうです。

テレスコーピング

展開とも呼ばれます。漸化式を自分自身に、パターンが見えるまで代入していき、最後に代入の回数を決めて、既知の初期値だけが残るようにする解き方です。途中の項が望遠鏡（テレスコープ）の筒のようにたたまれることからこの名前があります。

Θsaid “ビッグシータ”

上からも下からも押さえる増え方のこと。Θ(2ⁿ) は、コストが 2ⁿ より速くならないというだけでなく、2ⁿ のように増える、という意味です。O(2ⁿ) なら天井だけの約束になります。ここで正直な記法は Θ です。このアルゴリズムは本当に 2ⁿ − 1 手を行い、運よく早く終わることがないからです。

よくある質問

ハノイの塔の再帰アルゴリズムはどう動くのですか？

n枚を移動元の塔から移動先の塔へ移すために、まず上のn − 1枚を予備の塔へ移し、次にいちばん大きい円盤を移動先へ移し、最後にそのn − 1枚を予備から移動先へ移します。この2つの小さい移動はどちらも円盤が1枚少ないだけの同じ問題なので、関数は自分を呼びます。そして動かす円盤がない呼び出しは、ただ戻ります。

ハノイの塔は分割統治ですか、動的計画法ですか？

分割統治です。問題はn − 1枚の部分問題2つに分けられ、それぞれが再帰で解かれ、結合はいちばん大きい円盤を1回動かすことです。動的計画法ではなく、メモ化しても得はしません。部分問題が本当に重複するにもかかわらず、です。塔が3本なら、移動元・移動先・予備の名づけ方は6通りしかないので、3枚を解く途中で hanoi(1, A, C, B) は確かに2回呼ばれます。それを覚えておいても何も得られません。部分問題の答えは 2ᵏ − 1 手のリストで、その長さのリストを再生する費用は、作る費用と同じだからです。ここでは仕事そのものが出力であり、どんな表を作っても出力は短くなりません。

ハノイの塔の漸化式にマスター定理は使えますか？

使えません。マスター定理が対象とするのは T(n) = aT(n/b) + f(n) の形、つまり部分問題が元の何分の1かである場合です。ハノイの塔の漸化式は T(n) = 2T(n − 1) + 1 で、部分問題は1枚小さいだけであり、何分の1でもありません。展開すればそのまま T(n) = 2ⁿ − 1 が出て、帰納法がそれを確かめます。

再帰はどこまで深くなりますか？

基底の場合を n = 0 とすると、同時にスタックに載る呼び出しは多くても n + 1 個です。n から0までの枚数ごとに1つずつ。基底の場合を n = 1 にすれば n 個になります。どちらでも深さは線形にしか増えません。だから再帰の解法は、指数的な回数の移動を行っても、メモリは O(n) しか要らないのです。

再帰の解法は関数を何回呼びますか？

基底の場合が n = 0 のとき 2ⁿ⁺¹ − 1 回です。円盤を動かす 2ⁿ − 1 回の呼び出しと、動かすものが見つからずに戻る 2ⁿ 回の呼び出しの合計です。3枚なら15回。基底の場合を n = 1 にして書けば、同じプログラムがちょうど 2ⁿ − 1 回、1手につき1回だけ呼びます。

反復版は再帰版より速いですか？

意味のある差はありません。どちらも 2ⁿ − 1 手を作らなければならないので、どちらも 2ⁿ に比例する時間がかかります。反復版は関数呼び出しの費用を避けられ、スタックを使い切ることもありませんが、ここでの再帰の深さはたかだか n 段です。待てるだけの枚数なら、スタックが尽きる心配は現実には起きません。

ハノイの塔のアルゴリズムをフローチャートにするとどうなりますか？

たいした図にはなりません。それが正直な答えです。フローチャートは制御が箱の中を一度だけ流れていく様子を描きますが、このアルゴリズムの2つ目の箱は、フローチャート全体をもう一度、3段下で、塔を2つ入れ替えて、円盤を1枚減らして描いたものです。フローチャートにはそれを表す記法がありません。だから再帰の解のフローチャートは、間違っているか、「hanoi を呼ぶ」と書かれた2つの箱がある1回ぶんの絵かのどちらかで、後者は4行の擬似コードが教えること以上を何も教えません。それを表せる図は再帰木です。どの呼び出しも、それを作った呼び出しの下に描かれ、各箱は自分が行う手の上にあります。それはこのページにあり、箱を左から右へ読めば手が順番に並びます。

すでに途中まで解いたパズルも、このアルゴリズムで解けますか？

教科書どおりの版では解けません。すべての円盤が1本の塔にあることを前提にしているからです。場合を1つ足せば一般化できます——いちばん大きい円盤がすでに目標の塔にあるなら、それは飛ばして上の円盤を解く——そしてその版は、どんな正しい配置からでも最短の解を見つけます。このサイトのソルバーが動かしているのが、まさにそれです。 ソルバーを開く →