ハノイの塔：よくある質問

コツはあります。しかも頭を使うものではなく、機械的なものです。奇数手目には、一番小さい円盤を毎回同じ向きに塔1つ分動かします。円盤が奇数枚なら左、偶数枚なら右で、端まで行ったら反対側に回るので、3枚なら最初の一手で A から C へ移ります。偶数手目には、一番小さい円盤に触れない正しい手が必ずひとつだけあるので、考えずにそれを指します。この2つを交互に繰り返せば、一歩も先読みせずに完璧なゲームになります。 攻略法のページで詳しく説明しています。

左の塔に山をまるごと、一番小さい円盤を上にして置いた状態から始めます。目的は、同じ山を右の塔に作ることです。ルールは3つ。一度に1枚、動かすのは塔の一番上だけ、小さい円盤の上に大きい円盤は置かない。3枚の最短のゲームは7手で、3つのまとまりに分かれます。A→C、A→B、C→B で小さい2枚を真ん中の塔に積み、A→C で一番大きな円盤を移し、B→A、B→C、A→C でその上に2枚を積み直します。 練習用の盤面つきの遊び方。

覚えるのは簡単で、難しいのは一点だけです。円盤を1枚増やすごとに、ゲームの長さが2倍になるのです。3枚なら7手で、多くの人（6歳くらいからの子どもも）が最初の挑戦で解けます。5〜6枚あたりから当てずっぽうでは解けなくなり、方法が必要になります。その方法で難しいのは、ゴールが右なのに山を真ん中の塔に積み上げるような、後戻りに見える手を信じることです。再帰の考え方がわかれば、どの枚数も同じパズルになります。 再帰の考え方がパズルのすべてである理由。

ルービックキューブのように、ハノイの塔のスピード記録を公認する団体はありません。そのため主張される記録は比べようがなく、たいていは唯一大事な数である円盤の枚数さえ書かれていません。代わりに計算してみましょう。円盤 n 枚の完璧なゲームは 2ⁿ − 1 手で、慣れた人なら1秒に約2手のペースを保てます。すると3枚で約4秒、10枚（1,023手）で約9分、15枚（32,767手）で約4時間半になります。このサイトの盤面は、枚数ごとの最少手数をブラウザに保存し、結果画面にタイムを表示します。 計算機でどの枚数でもかかる時間がわかります。

2ⁿ − 1 です。これは知られている最良の結果ではなく、証明された下限です。3枚で7手、4枚で15手、5枚で31手、10枚で1,023手、15枚で32,767手です。証明は2つの部分からなります。再帰的な方法でこの手数が達成できること、そしてどの解もこれより短くはできないことです。一番大きな円盤は少なくとも一度は動かさなければならず、その上にある小さい円盤はすべて、先に予備の塔へどかし、あとで戻す必要があるからです。 証明の2つの部分を、すべて。

T(n) = 2·T(n − 1) + 1、ただし T(0) = 0 です。これは解き方からそのまま読み取れます。n 枚を移すには、n − 1 枚をどかし、1枚を移し、その n − 1 枚を戻します。つまり小さい解が2つと、1手です。これを展開すると T(n) = 2ⁿ − 1 となり、帰納法で確かめられます。T(n − 1) = 2ⁿ⁻¹ − 1 なら、T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1 です。 漸化式を1ステップずつ解く。

手数は指数的に増えますが、計算量の意味では難しい問題ではありません。アルゴリズムは数行で書け、次の一手は定数時間で決まり、解が指数的に長いのは答えそのものが長いからにすぎません。2ⁿ − 1 個の手を出力するには、2ⁿ − 1 ステップ未満では済まないのです。NP 困難ではなく、3本の塔で任意の2つの正しい配置の間の最短経路を求めるのも効率よく解けます。本当に難しいのは4本の塔の版で、その最適解は1941年に予想され、2014年にティエリー・ブーシュが証明するまで未解決でした。 アルゴリズムとその計算コスト。

フレーム・スチュワートの方法を使います。4本の塔では、n − 1 枚をひとかたまりで動かしません。区切り k を選び、上の k 枚を4本すべてを使って予備の塔へ移し、残りの n − k 枚を3本だけで目的の塔へ移し（予備の塔はふさがっているので、この部分は普通のパズルです）、最後に k 枚を上に積みます。すべての k を試して最良のものを選ぶと最適な手数になり、劇的に減ります。15枚なら、3本の32,767手が4本では129手になります。 4本の塔のパズルで遊ぶ。

再帰で表した分割統治法です。標準的な解法はひとつの関数で、n − 1 枚を出発の塔から予備の塔へ、円盤 n を出発から目的へ、その n − 1 枚を予備の塔から目的へ移します。n が0になったときの基底ケースでは何もしません。再帰をまったく使わない同等の反復アルゴリズムもあります。一番小さい円盤を決まった向きに塔1つ分動かし、次に唯一のほかの正しい手を指す、を繰り返すものです。最適解はひとつしかないので、どちらもまったく同じ手順を生み出します。 アルゴリズムを1行ずつ。

再帰関数ひとつと引数3つです。void hanoi(int n, char from, char to, char via) — n が0なら return し、そうでなければ hanoi(n − 1, from, via, to) を呼び、from → to の手を出力し、hanoi(n − 1, via, to, from) を呼びます。呼び出しは hanoi(3, 'A', 'C', 'B') です。呼び出し側で手を使いたいなら、出力する代わりに std::vector<std::pair<char, char>> に集めましょう。また n は普通の int のままにしてください。符号なしの引数だと、誤って渡した負の数が黙って約40億になり、n &lt; 0 の簡単なチェックで止まる代わりに、スタックがあふれるまで再帰が続いてしまいます。 C++ の完全なプログラムを1行ずつ解説。

スタックの使い方は2通りあり、分けて考えるのが大切です。まず、塔そのものがスタックです。どの塔も後入れ先出しで、触れるのは一番上の円盤だけ。1手はある塔からの pop と別の塔への push なので、ルールのチェックは行き先の一番上との比較1回で済みます。これとは別に、明示的なスタックで再帰を置き換えることもできます。仕事全体 (n, from, to, via) を push し、ループで仕事を pop して、円盤が残っていればその3つの部分を逆順に push します。2回目の移動、円盤 n の1手、1回目の移動の順です。スタックは最後に入れたものを最初に返すので、逆順が重要です。再帰版では、言語の実行環境がまさにこれを代わりにやってくれています。 再帰をまったく使わない解法。

AI では、このパズルは公式ではなく探索問題です。各状態は円盤ひとつひとつをどの塔に置くかの割り当てなので 3ⁿ 通りあり、正しい手はその間を結ぶ辺です。幅優先探索、A*、あるいは「目的の塔にまだない円盤の数」のようなヒューリスティックを使った IDA* などの探索で、初期状態からゴールまでの最短経路を見つけます。ニューウェル、ショー、サイモンの General Problem Solver 以来の定番のテスト問題です。手段目標分析と目標分解のわかりやすい例だからで、「一番大きな円盤を動かす」という下位目標は、進んだ分を戻すように見える別の下位目標を先に満たさないと達成できません。なお、再帰アルゴリズムは探索ではありません。既知の解そのものであり、使わない状態を調べることはありません。 心理学の課題としての同じパズル。