ハノイの塔を変形する:柱を4本にすると手数はどうなるか

3本の基準線を押さえる

3本の場合、円盤がn枚のときの最少手数は 2ⁿ − 1 手と知られています。1枚なら1手、2枚なら3手、3枚なら7手です。理由は次のとおりです。

• 一番大きい円盤を動かすには、その上のn−1枚をすべて別の柱へ退避させる必要があります。
• 大きい円盤を1手で移します。
• 退避させた n−1 枚を、その上へ載せ直します。

つまり T(n) = 2T(n−1) + 1 です。枚数が1枚増えるたびに手数がほぼ倍になります。

実験の前に、この基準線を自分のプログラムで再現できるか確認しておきます。4本の結果が正しいかどうかは、3本の結果が公式どおりに出るかで判断できるからです。3本で 2ⁿ − 1 に一致しないなら、4本の数字は信用できません。

4本で増える「逃げ場」の使い方

柱が1本増えると、小さい円盤を一時的に置ける場所が増えます。この性質を使った解き方として、フレーム–スチュワート法がよく知られています。考え方は次のとおりです。

1. 上から k 枚を、4本すべてを使って一時的な柱へ移します。
2. 残る n−k 枚を、使える柱が3本に減った状態で目的の柱へ移します。一時的な柱はすでに円盤で塞がっているため使えません。
3. 最初の k 枚を、再び4本を使って目的の柱へ載せます。

式にすると、T₄(n) = min（k は1以上n未満）{ 2T₄(k) + 2ⁿ⁻ᵏ − 1 } です。k をどう選ぶかで手数が変わり、最小になる k を探すのがこの方法の核心です。

小さい例で確かめられます。柱をA〜Dとし、円盤を小さい順に1・2・3とします。3枚すべてがAにあり、Dへ移す場面を考えます。次の5手で完了します。

1. 円盤1をBへ。
2. 円盤2をCへ。
3. 円盤3をDへ。
4. 円盤2をDの円盤3の上へ。
5. 円盤1をDの円盤2の上へ。

3本なら7手かかる3枚が、4本なら5手で済みます。小さい円盤をそれぞれ別の柱へ逃がせるためです。

4本の場合にこの方法が本当に最短かどうかは、長く未解決の問題として扱われてきました。4本の場合は最適性が示されたとする報告があります。ただし詳細は文献で確認してください。この記事の実験は、証明ではなく、小さい枚数について総当たりの数字とこの式が一致するかを自分で確かめるものです。

実験の設計:幅優先探索で最少手数を数える

問いと準備

問いは次の2つです。

• 円盤が1〜8枚のとき、3本と4本の最少手数はそれぞれ何手か。
• 4本の最少手数は、上のフレーム–スチュワートの式の予想値と一致するか。

準備するものは、Node.js またはブラウザの開発者コンソールと、下のコードだけです。外部ライブラリは使いません。

盤面の表し方

円盤ごとに「どの柱にあるか」を記録し、柱の数を底とする数として1つの整数にまとめます。円盤0が一番小さく、最初はすべて柱0にあるので状態は0です。ゴールはすべて最後の柱にある状態で、P ** n − 1 に当たります。

円盤の位置さえ決まれば、柱の中の積み順は一意に決まります。大きい円盤が小さい円盤の上に載ることはないからです。位置の組だけで盤面を表せるのはこのためです。

幅優先探索は、1手で行ける盤面を順に広げていく方法です。最初にゴールへ到達した時点の手数が最少手数になります。

コード

function solve(n, P) {
  const goal = P ** n - 1;
  const dist = new Map([[0, 0]]);
  let frontier = [0];
  while (frontier.length) {
    const next = [];
    for (const s of frontier) {
      if (s === goal) return { moves: dist.get(s), seen: dist.size };
      const pos = [];
      let x = s;
      for (let i = 0; i < n; i++) { pos.push(x % P); x = (x - pos[i]) / P; }
      const top = new Array(P).fill(-1); // 各柱の一番小さい円盤
      for (let i = n - 1; i >= 0; i--) top[pos[i]] = i;
      for (let a = 0; a < P; a++) {
        if (top[a] < 0) continue;
        for (let b = 0; b < P; b++) {
          if (a === b || (top[b] >= 0 && top[b] < top[a])) continue;
          const t = s + (b - a) * P ** top[a];
          if (!dist.has(t)) { dist.set(t, dist.get(s) + 1); next.push(t); }
        }
      }
    }
    frontier = next;
  }
}
for (let n = 1; n <= 8; n++) {
  const t0 = performance.now();
  const r3 = solve(n, 3), r4 = solve(n, 4);
  console.log(n, r3.moves, r4.moves, r3.seen, r4.seen,
    Math.round(performance.now() - t0) + "ms");
}

動かす円盤は、その柱で一番小さい円盤に限ります。移動先は、空の柱か、一番小さい円盤が動かす円盤より大きい柱です。この2つの条件だけがルールです。

実行手順

1. 上のコードをそのまま貼り付けて実行します。
2. 1行につき「枚数、3本の最少手数、4本の最少手数、各探索で調べた盤面数、所要時間」が出ます。
3. 枚数を9、10と増やす場合は、先に4本だけの処理時間を確認してから進めます。4本の盤面の総数は 4ⁿ 通りなので、枚数が1枚増えるたびに探索量は約4倍になります。

記録の取り方と結果の読み方

次のような表を用意して、枚数ごとに埋めます。

• 1〜8、3本の最少手数：、2ⁿ−1との一致：、4本の最少手数：、式の予想値：、調べた盤面数：、所要時間：

記録の単位と回数は次のとおりです。

• 最少手数は枚数ごとに1回記録します。結果は決定的で、乱数を使わないため、同じ入力なら何度回しても同じ数になります。
• 所要時間は同じ条件で3回測り、中央値を使います。ブラウザは他の処理の影響を受けるためです。
• 調べた盤面数は、探索の重さを比べるために記録します。

予想値の側は、式で計算できます。4本の最少手数は、枚数1〜8で 1、3、5、9、13、17、25、33 になると予想されます。これは上のフレーム–スチュワートの式を計算した値です。自分のプログラムの出力と突き合わせてください。

結果は次の基準で読みます。

• 3本の列が 2ⁿ−1 になり、4本の列も予想値と一致すれば、プログラムは正しく、式も小さい枚数では最短と合っています。
• 3本が 2ⁿ−1 にならなければ、4本の数字は参考になりません。ルール判定を先に見直します。
• 3本は合うのに4本だけがずれるなら、柱の数を渡す部分、ゴールの計算、状態の符号化のどこかに誤りがあります。
• 4本の列の差（隣り合う枚数の手数の増え方）にも注目します。3本では差が 1、2、4、8…と毎回倍になりますが、4本では同じ大きさの増え方がしばらく続いてから次の段に上がります。この「段になって増える」形が自分の数字にも出るかを見ます。

つまずきやすい点

• 1枚だけの場合は、ゴールに着くまで探索が回りません。solve(1, 4) が1を返すかを最初に確かめます。
• 柱を番号で入れ替えて数える誤りに注意します。柱が4本だと「どの柱がゴールか」を取り違えやすくなります。コードではゴールを最後の柱に固定しています。
• top の更新順を間違えると、一番小さい円盤が取れません。大きい番号から順に代入し、最後に小さい番号が残る順序にします。
• 枚数を増やしすぎると、メモリ不足やブラウザの停止が起こります。まず8枚までで挙動を確かめ、そこから広げます。
• 最短の手順そのものと最少手数は別物です。この実験が求めるのは数だけで、経路は保存していません。ヒント機能に使いたいときは、各盤面に「ひとつ前の盤面」も記録して、ゴールからたどり直します。

この数字をゲームの設計に使う

実験で得た数字は、そのまま試作の設計値になります。

• 星の基準や「目標手数」は、最少手数に余裕を足して決められます。3本の感覚で目標を置くと、4本版では合わなくなります。
• 難易度の上がり方も違います。3本は枚数が1枚増えるたびに倍になり、4本は増え方が段になるため、同じ「枚数を増やす」操作でも手応えが変わります。表の差を見て、何枚から何枚までを遊べる範囲にするかを決められます。
• 画面の作り方にも影響します。柱が4本になると横幅が狭くなるため、スマートフォンの縦画面での見え方や、タップで選ぶ操作の判定幅を早めに確かめます。
• 最少手数が分かるので、「一手戻す」や「残り最短手数の表示」のようなヒント機能も作れます。そのとき、盤面から最短手数を引ける表を実行時に作るのか、事前に計算して持つのかは、枚数の上限と処理時間で決めます。

条件を変えるなら、柱を5本にする、隣り合う柱にしか動かせないようにする、といった変形もできます。コードでは P の値や移動の条件を書き換えるだけで試せます。

次の行動

まず上のコードで、枚数1〜8の表を埋めてください。次に、予想値と一致したかを確かめ、一致しない行があれば原因を探します。

そのうえで、4本のハノイを1つのHTMLにまとめ、最少手数を目標に表示する試作を作ってみてください。アソバースにはHTMLを直接アップロードして公開できるので、他の人に遊んでもらうこともできます。投稿の条件は、現在の案内で確認してください。

参考資料

• Frame–Stewart アルゴリズム(ハノイの塔の4本以上の柱への拡張に関する一般的な解説)
• 数列の公開データベース OEIS(4本のハノイの塔の最少手数に関する項目)