ハノイの塔戦略：2^n − 1 手で解く (2026)

1. ゲーム全体は一つの数: 2^n − 1

n 枚のディスクに対して可能な最小手数は 2^n − 1 で、このビルドはそれを表示し、それに対して採点します。3 枚は 7 手、4 枚は 15 手、5 枚は 31 手、6 枚は 63 手、7 枚は 127 手、8 枚は 255 手です。これは任意の目標ではありません — 数学的な下限であり、人間はこれより良くできません。

「解いた」人の大半は最適の 2〜3 倍の手数を要します。なぜならディスクを場当たり的に動かし、無駄な手は最後になって初めて気づくからです。このビルドのカウンタと Perfect! バナーは、その無駄を可視化します: 勝利時に手数が 2^n − 1 と等しい場合にのみ Perfect! に昇格します。そのバナーを見るまでは、パズルを解いたのではなく、ただ終えただけです。したがって最初の目標は「塔を動かす」ことではなく「塔を 2^n − 1 手で動かす」ことで、以下はすべてその道筋です。

2. 下限に到達する再帰レシピ

最適解は再帰的な形を持っており、一度見るとパズルは探索からチェックリストへと変わります。n 枚のディスクをペグ A からペグ C へ、ペグ B を予備として移すには:

1. 上の n − 1 枚を A から B へ移す（C を予備として）。
2. 最大のディスクを A から C へ移す。
3. n − 1 の塔を B から C へ移す（A を予備として）。

これがアルゴリズムのすべてです。ステップ 2 は最大ディスクの唯一の移動であり、ステップ 1 と 3 は同じ問題を一回り小さくしたものです。最大ディスクは、その上に何も乗っておらず、移動先が空のときだけ動かせるため、まずそれを解放するしかありません — そして解放するとは、より小さい塔を解くことであり、それはさらに自分の最大ディスクを解放する必要があり、単一のディスクに至るまで続きます。

実用的な結論: 最大ディスクは正確に 1 回だけ、解の中央で動く。最大ディスクが 1 回より多く動いたなら、最適経路には乗っていません — 再び埋めてしまい、もう一度解放する必要があります。注意してください: 底のディスクが何度も持ち上げられるセッションは、2^n − 1 を大幅に超えて終わるセッションです。

3. 手数を奪う 3 つのミス

最大ディスクを早く動かしすぎる。 そのペグにそれだけが残るまで動かせないので、n − 1 の塔が予備ペグに完全に駐車される前にするすべての手は、唯一重要な手を遅らせるだけです。初心者はしばしば上のディスクを「始めるために」シャッフルし、底のディスクがまだ固定されていることに気づくのが後になります。

空のペグを装飾として扱う。 空のペグは時々使う予備ではありません — 再帰を可能にする組み立て場です。3 ペグのゲームでは、常に 1 本が構築中の塔を支え、1 本が解体中の塔を支え、3 本目が空いています。3 つの役割を意識的に使わないなら、無視した 1 本を迂回する余分な作業をしています。

貪欲に遊ぶ。 今一番良く見える合法手が、次に再帰が欲しい手であることは稀です。「最小ディスクを動かす」は常に合法なので生産的に感じますが、最適な手順は小さいディスクと大きいディスクを固定パターンで交互に動かします（ディスク数が奇数なら最小ディスクは A → C → B → A、偶数なら A → B → C → A と巡回します）。考えることをやめて最小の合法ディスクを動かし続ければ、終わります — しかし 2^n − 1 では終わりません。

4. ディスクの梯子を登り、いつ止まるかを知る

難易度は線形ではなく指数的です。手数がそれを正直に物語ります:

• 3 枚 / 7 手 — ここで再帰を学ぶ。解全体を頭に保持できます。
• 4 枚 / 15 手 — レシピを信頼する必要がある最初のサイズ。
• 5 枚 / 31 手 — 本物のパズル; 1 つのミスで 10 手オーバー。
• 6 枚 / 63 手 — 1 セッション; 一気に終える計画を立てないと糸を失います。
• 7 枚 / 127 手 — プロジェクト; 元に戻すを意図的に使う。
• 8 枚 / 255 手 — マラソン; ゲームは許しますが、ほとんどのセッションは 4〜6 で生きるべきです。

正直なトレーニング経路は 3 → 4 → 5、そしてそれから 6 です。8 に「大きいのを見るため」に飛ぶのは何も教えません。255 手の即興は練習ではなく疲労です。ディスク数メニュー (3〜8) と URL パラメータ ?disks=n でサイズを固定できるので、1 週間サイズを固定し、昇格する前にその上で Perfect! バナーを追いかけてください。

5. 元に戻すを松葉杖ではなく教師として使う

元に戻すは 1 手戻り、勝利状態を消します。したがって再帰を学ぶ最もクリーンな方法です: 迷うまで遊び、理解していた最後の位置に戻り、推測ではなくレシピから次の手を導いてください。ゲームにタイマーがないので、考えるために立ち止まってもペナルティはありません — 測定されるのは手数だけです。

役立つ 2 つの習慣: ?disks=4（または任意）で同じシードを、Perfect! を 2 回連続で出すまで繰り返すこと、そして動かす前にどのディスクをなぜ動かすかを声に出して言うことです。どのディスクでなぜか言えないなら、推測しています。推測こそがカウンタを 2^n − 1 の上に押し上げるものです。ゲームは同じ ?disks= の値に対して同じ塔を再配布するので、毎回新しいランダム配置から再スタートするのではなく、1 つの位置を練習できます。

FAQ

これはゲームページのルールとどう違いますか?

ゲームページは盤面の仕組みを説明します — 3 本のペグ、頂上ディスクのみ、大きいものが小さいものを覆うことは決してない、ドラッグまたはタップ、最適に対するカウンタ、元に戻す、3〜8 枚のディスク、タイマーなし。このガイドはそれを既知として、その上の層を扱います: 2^n − 1 の下限、再帰レシピ、3 つのミス、ディスクの梯子、練習方法。まずルールを読み、それから Perfect! バナーを追いかけてください。

2^n − 1 は本当に可能な最小ですか?

はい。最大ディスクは少なくとも 1 回動かなければならず、動かすにはその上の n − 1 枚がペグから退き、道を空ける必要があります。帰納法により、それには少なくとも前後にそれぞれ 2^(n−1) − 1 手、さらに最大ディスク自身の 1 手が必要です。3 本のペグが問題を非自明にする最小であり、3 本のペグでは下限は正確に 2^n − 1 です。4 本ペグの変種（Reve のパズル）はより低い下限を持ちますが、このゲームは 3 本を使います。

なぜバナーは「Perfect!」と時々しか言わないのですか?

「Perfect!」は正確に 2^n − 1 手で解いた場合にのみ予約されています。より多くの手で解いても勝ちです — 「Solved!」バナーが発火し、手数が最適に対して表示されます — しかし Perfect! は手数が下限と等しい場合にのみ昇格します。一度も見たことがないなら、手数は下限より上です; カウンタがどれだけ上かを教えてくれます。

すべての配置が解けますか?

はい。初期配置は常に 1 本のペグ上の完全な塔であり、レシピは 3 から 8 までの任意の n について解きます。シャッフルも行き止まりもありません — 不正な手は単に拒否され、何も変わりませんので、角に自分を追い込むことはできません。常に元に戻すで既知の良い状態に戻れます。

どのディスク数で練習すべきですか?

3 で Perfect! を 2 回連続で出せるまで始めて、次に 4、次に 5 です。ほとんどのプレイヤーは 5 枚（31 手）で停滞し、そこは留まるのに良い場所です — 6 以上はより長いセッションを望むときのためであり、学習のためではありません。練習に 8 は避けてください; 255 手の即興は練習ではなく疲労です。

どこで遊べますか?

このサイトの tower-of-hanoi ページ上で、まさに。このパズルは 1883 年に Édouard Lucas が出版した公有領域の数学問題なので、バイト単位で再利用された上流ファイルはありません; ルールモジュール、ページシェル、スタイルシート、アナリティクスブリッジ、タッチシムはすべて Playnesta オリジナルで MIT です。GUI レイアウトは AJLoveChina/Hanoi @ 917b8d6 (MIT) に着想を得ており、機構参考としてのみ読み、ここでは再配布されません。Playnesta Games がこの具体的なウェブ実装の開発者兼発行者です。