ハノイの塔の解き方と手数の公式

最小手数の公式：なぜ 2ⁿ－1 なのか

円盤がn枚のとき、最小手数は 2ⁿ－1 手です。円盤3枚なら7手、4枚なら15手、10枚なら1,023手になります。

この公式は「覚えるもの」ではなく、解き方の構造から自然に出てきます。考え方は次の通りです。

n枚の円盤を柱Aから柱Cへ移すには、3つの作業に分解できます。

1. 上のn－1枚を柱Aから柱Bへ移す
2. 一番大きい円盤（n枚目）を柱Aから柱Cへ1手で移す
3. 柱Bに移したn－1枚を柱Cへ移す

1と3は「n－1枚を移す問題」と同じ形です。これを式にすると、n枚に必要な手数T(n)は次のようになります。

T(n) = T(n－1) + 1 + T(n－1) = 2×T(n－1) + 1

T(1)＝1（1枚なら1手）を起点に展開すると、T(n)＝2ⁿ－1が得られます。この「自分と同じ形の問題に分解する」考え方を再帰と呼びます。ハノイの塔はプログラミングで再帰を学ぶ題材としても有名で、解法そのものがアルゴリズムの教科書に載るほど整った構造を持っています。

3枚を7手で解く：手順を追う

公式を実感するために、3枚（柱A→柱C）を実際に動かします。円盤を小さい順に1・2・3と呼び、1が最小です。

• 1、動かす円盤：円盤1、移動元 → 移動先：A → C
• 2、動かす円盤：円盤2、移動元 → 移動先：A → B
• 3、動かす円盤：円盤1、移動元 → 移動先：C → B
• 4、動かす円盤：円盤3、移動元 → 移動先：A → C
• 5、動かす円盤：円盤1、移動元 → 移動先：B → A
• 6、動かす円盤：円盤2、移動元 → 移動先：B → C
• 7、動かす円盤：円盤1、移動元 → 移動先：A → C

4手目が分岐点です。ここで最大の円盤3を目的地Cへ運び、残りの2枚をCの上に積み直します。「上をどかして、大きいのを運んで、また上を戻す」という3段構えが、手順全体の骨格です。

4枚以上になっても同じ骨格が繰り返されます。枚数が1増えると手数が2倍強になるため、円盤20枚だと最低でも1,048,575手（約100万手）かかります。人間が毎秒1手動かし続けても12日かかる計算になります。

手詰まりを防ぐ判断基準

実際にプレイしているとき、手が止まる場面には共通のパターンがあります。

大きい円盤を動かそうとして行き先がないこれは「上のn－1枚を1か所に集め切れていない」サインです。大きい円盤を動かす前には、それより小さいすべての円盤が1本の柱にまとまっている必要があります。現在の状態でその条件を満たしているか確認するのが、詰まったときの最初のチェックです。

同じ状態に戻ってしまう意識せずに手を動かすと、数手前と同じ配置に戻ることがあります。3枚の場合、正解の7手以外にも手は動かせるため、うっかりループにはまりやすいです。「今どの段階の分解をやっているか」を柱ごとの枚数で確認しながら進めると、迷子になりにくくなります。

奇数枚と偶数枚で最初の動かし先が変わる円盤が奇数枚のとき、最小の円盤（円盤1）は最初に目的地（柱C）へ動かします。偶数枚のときは中間地点（柱B）へ動かします。この法則を知っておくと、1手目の迷いがなくなります。

再帰の感覚をつかむと枚数が増えても怖くない

4枚・5枚と挑戦するとき、全手順を暗記しようとするのは非効率です。代わりに「今、自分は何枚の問題を解いているか」を意識します。

たとえば4枚の場合、手順の途中で「3枚の問題」が2回出てきます。3枚の解き方がわかっていれば、その部分は自動的に解けます。「今は4枚問題の前半（3枚を柱Bへ）」「今は4枚問題の後半（3枚を柱Cへ）」という2つの局面に意識を絞ると、全15手を分割して考えられます。

この入れ子構造がわかると、10枚でも100枚でも同じ方針で解けます。手数は指数関数的に増えますが、考え方は変わりません。「今どの枚数の問題を解いているか」「その問題の次の大きい円盤をどこへ運ぶか」という2点だけ追い続ければ、原理的にはどんな枚数でも解けます。

次の行動

3枚のハノイの塔をブラウザで検索して、7手ちょうどでクリアできるか試してみてください。クリアできたら枚数を1枚増やして、15手を目標にしてみましょう。アソバースにはパズル系のブラウザゲームが投稿されていますので、解法を身につけたあとに似た構造のゲームを探してみるのも一つの楽しみ方です。