ハノイの塔を杭 3・4・5 本でブラウザに実装した。サイズを選ぶとタブの中で全局面を幅優先でたどり（4 本 12 枚なら 16,777,216 局面）、どの局面でも「ゴールの杭に全部積むまであと何手か」を表示する。円盤を持ち上げると、各杭に「そこに置いたら何手になるか」が出る。杭が 4 本になると最短手順は公式では出ない。Frame–Stewart の手順（1941）が最適だと証明されたのは 2014 年（Bousch）で、しかも完成した塔からいちばん遠い局面は、別の杭に移った塔とは限らない。Richard Korf の全探索（AAAI 2004）によると、15 枚では塔を移すのに 129 手なのに、130 手離れた局面が 588 個ある。論文には「この驚くべき異常には説明がない」と書かれている。この表を C の 2 ビット幅優先探索（417 ≈ 172 億局面、4 GiB）で 17 枚まで全行再現し、588 局面が「一番大きい円盤を 1 回だけ動かす」経路の分解でどう 130 手になるかを調べた。Wikipedia（英・日）・OEIS・論文 2 本の公表値はスクリプトで抜き出して照合し、78 個中 76 個が一致。合わなかったのは、Korf の表 3 の 1 枚の行（論文の規則どおり数えると 2、表は 1）と、日本語版 Wikipedia の m 手目のビット演算の式（円盤が偶数枚だと塔は右端でなく真ん中の杭に移る）の 2 つ。テスト 10 件。ソルバー内蔵パズル第 79 弾。
デモ: https://sen.ltd/portfolio/tower-of-hanoi/
リポジトリ: https://github.com/sen-ltd/tower-of-hanoi
ルールと局面の表し方
杭が p 本、円盤が n 枚。一度に 1 枚、いちばん上の円盤を別の杭に移す。小さい円盤の上に大きい円盤は置けない。
局面は「各円盤がどの杭にあるか」で決まる。どの杭でも円盤は大きい順に積まれているしかないので、それ以上の情報はない。そこで局面を p 進数の整数にする。円盤 k（0 がいちばん小さい）の杭が k 桁目。
export function moves(shape: Shape, s: number): Move[] {
const top = tops(shape, s); // 各杭のいちばん上（= いちばん小さい）円盤、空なら -1
const out: Move[] = [];
for (let a = 0; a < shape.pegs; a++) {
if (top[a] < 0) continue;
for (let b = 0; b < shape.pegs; b++) {
if (b === a || (top[b] >= 0 && top[b] < top[a])) continue;
out.push({ disk: top[a], from: a, to: b, next: s + (b - a) * shape.pegs ** top[a] });
}
}
return out;
}
手は「円盤 top[a] の桁を a から b に書き換える」だけなので、次の局面は s + (b − a)·p^top[a] の足し算で出る。局面数は pn。
タブの中の幅優先
ゴール（全部がゴールの杭）から幅優先で全局面の距離を Uint16Array に書く。手は可逆なので、ゴールからの距離 = ゴールまでの距離。Web Worker で回して、表ができたらボタンが効くようになる。
- Hint / Solve は距離が 1 減る手を選ぶだけ
- Farthest は距離が最大の局面から 1 つ選ぶ
- 右のヒストグラムは距離ごとの局面数
上限は 3 本 14 枚（4,782,969 局面）、4 本 12 枚（16,777,216）、5 本 10 枚（9,765,625）。4 本 12 枚は手元のヘッドレス Chromium で 7 秒ほどかかった。
Frame–Stewart と、それが最適だという証明
杭 3 本なら最短は 2n − 1 手で、どの局面からも完成形までの距離は O(n) の式で出る（大きい円盤から順に「ゴールに無ければ 2k を足して、ゴールを第 3 の杭に切り替える」）。テストでは 7 枚までの全局面で、この式と幅優先の距離が一致することを確かめている。
杭 4 本では、Frame と Stewart が 1941 年に次の手順を出した。上の k 枚を 4 本全部を使って空いている杭に移し、残り n − k 枚を 3 本で移し、k 枚を戻す。手数 2T(k) + 2n−k − 1 を最小にする k を選ぶ。これが本当に最適だと証明されたのは 2014 年（Bousch）で、それまでは探索で確かめるしかなかった。
ここでは 4 本 17 枚まで、全探索で求めた最短手数が Frame–Stewart の数（OEIS A007664）と一致することを確認した。英語版 Wikipedia の「4 本のとき最適な k は n − ⌊√(2n+1)⌉ + 1」も、n = 2..1000 のすべてで最小値を与える k の 1 つになっていた（999 個中 955 個の n では最小を与える k が複数ある）。
Korf の表を C で作り直す
Korf (2004) の表 2 は「4 本・n 枚で、全部が 1 本の杭にある局面から幅優先したときの最大深さ（半径）、局面数 4n、いちばん広い層の局面数」を 1〜20 枚について載せている。17 枚で 417 = 17,179,869,184 局面。1 局面 2 ビットなら 4 GiB で、手元のマシン（24 GB）に載る。
2 ビット幅優先は、各マスに 4 つの状態だけを持つ。
| 値 | 意味 |
|---|---|
| 0 | 未訪問 |
| 1 | いま展開する層（深さ d） |
| 2 | 次の層（深さ d + 1） |
| 3 | 展開済み |
1 層ぶん「1 のマスを全部展開して、隣の 0 を 2 にする」を回したら、1 → 3、2 → 1 に書き換える。この書き換えは 64 ビット語ごとのビット演算 1 回で済む。
// frontier (1) -> closed (3), next (2) -> frontier (1)
uint64_t l = x & 0x5555555555555555ULL, h = (x >> 1) & 0x5555555555555555ULL;
A[w] = (l | h) | (l << 1);
展開はスレッドで分け、隣を 0 → 2 にするところは __atomic_fetch_or で書く。同じ層では誰が書いても値は 2 なので、競合しても結果は同じ。「前は 0 だった」を返したスレッドだけが数える。層の数え上げのついでに、depth <d> <局面数> <正準形の数> を 1 行ずつログに出す。正準形は「空いている 3 本の杭を入れ替えても同じ」とみなしたときの代表で、3 本の杭をいちばん下の円盤の大きさでソートした形になっているものを数えればよい。
tools/radius.c を 1〜17 枚で回した結果（ログは tools/runs/ にコミットしてある）:
| 枚数 | 塔を移す手数 | 半径 | 半径にある局面 | いちばん広い層 |
|---|---|---|---|---|
| 1 | 1 | 1 | 3 | 3 |
| 3 | 5 | 5 | 12 | 30 |
| 10 | 49 | 49 | 12 | 109,890 |
| 14 | 113 | 113 | 6 | 14,368,482 |
| 15 | 129 | 130 | 588 | 48,286,104 |
| 16 | 161 | 161 | 6 | 162,989,898 |
| 17 | 193 | 193 | 6 | 572,584,122 |
（全 17 行はデモページにある。）表 2 の 17 行は半径・局面数・幅がすべて一致した。15 枚だけ半径が塔を移す手数を 1 上回り、その深さにちょうど 588 局面ある。Korf (2004) の本文の「588 states at depth 130」とも、Korf & Felner (2007) の「there exist 588 states that are 130 moves from the standard initial state」とも一致する。OEIS には Korf の値から作った半径の数列 A382111 があり、17 項目まで一致した。
TypeScript 側の幅優先（ページで使っているもの）は、10 枚までの全層の局面数が C のログと 1 つ残らず一致することを npm run stats が毎回確かめる。C のログと src/ のコードがずれたら止まる。
表 3 と「切り上げ」
表 3 は別の探索で、「塔を移す手順は前半と後半が対称なので、半分の深さまで探せばよい」という探索の規模を載せている。列は「最短手数」「半分の深さ（切り上げ）までの局面数」「その深さの局面数」で、空いた杭の入れ替えで割った数。
上の正準形の数を使うと、2〜17 枚の 16 行は「深さ ⌈手数/2⌉ まで」でぴったり一致した。1 枚の行だけ、この規則では 2（深さ 0 と 1 に 1 つずつ）になるのに、表は 1 と書いている。1 枚のときは手数 1 の半分を切り捨てて深さ 0 で止めた、と読めば 1 になる。
588 局面の中身
588 個を「空いた 3 本の杭の入れ替え」で割ると 98 組（どの組もちょうど 6 個）。98 組すべてで、いちばん大きい円盤がスタートの杭に無い。大きい方から 4 枚の位置を、いちばん大きい円盤のある杭を A として書くと、
- A・スタート・B・C（49 組）
- A・A・B・C（49 組）
で、3 番目と 4 番目に大きい円盤は残り 2 本の杭に分かれている。
比較のために他の枚数を見ると、4〜17 枚のほとんどで半径にある局面は 6 個で、3 個は別の杭に移った塔、3 個は「いちばん大きい円盤だけが別の杭、残りはスタートの杭」だった（3 枚と 10 枚は 12 個）。15 枚では、別の杭に移った塔すら半径に届かない。
いちばん大きい円盤が動く瞬間で分ける
588 局面からスタートの杭に全部戻す（手は可逆なので、スタートから 588 局面に行くのと同じ）には、どこかでいちばん大きい円盤 D をスタートの杭に乗せなければならない。その瞬間、残り 14 枚は D が今いる杭とスタートの杭以外の 2 本にしか置けない。この「14 枚が 2 本の杭だけにある配置」をゲートウェイと呼ぶ（214 = 16,384 個）。
D が 1 回しか動かないなら、距離は
min over ゲートウェイ g of { d₁₄(今の 14 枚 → g) + 1 + d₁₄(g → スタートに 14 枚) }
になる。D は最大なので 14 枚の動きを邪魔しない。tools/anomaly.c は 14 枚の空間（414 = 268,435,456 局面）で「ゲートウェイごとに帰りの手数を初期値にした多始点の幅優先」を 1 回回してこの値を全局面について出し、15 枚の正確な距離（1 局面 1 バイト、1 GiB）と比べる。
結果:
- D が空いた杭の 1 本にある 268,435,456 局面すべてで、この値は正確な距離と一致した。 どの局面にも D を 1 回しか動かさない最短経路がある
- スタートからいちばん近いゲートウェイは 64 手で、そういうゲートウェイは 2 個しかない。別の杭に移った 14 枚の塔もそのどちらかに 64 手で行けるので、塔は 64 + 1 + 64 = 129
- D がその杭にある 196 個の最遠局面のうち、184 個は残り 14 枚がその 2 個のゲートウェイから 65 手、12 個は 66 手離れている。それ以外のゲートウェイを使っても合計は 129 を下回らず、どれも +1 で 130
例えば 333133010013201（円盤ごとの杭、小さい方から）では、最小の 129 + 1 を与える分け方が 50 + 1 + 79、52 + 1 + 77、65 + 1 + 64 の 3 通りある。いちばん近いゲートウェイに向かえば行きが塔より 1 手長く、遠いゲートウェイに向かえば行きは短くなるが帰りがちょうどその分長くなり、どれも 129 を割らない。
これで「なぜ 15 枚なのか」まで説明できたわけではない。言えるのは、588 局面は「D を 1 回動かすだけの経路」で距離が決まっていて、14 枚の部分がどのゲートウェイ経由でも塔より 1 手不利な位置にある、というところまで。
Wikipedia と OEIS の値
466/885 を厳密に
英語版には、杭 3 本で 2 つの局面をランダムに選んだときの平均距離の厳密式（Hinz, Chan）が載っている。
466/885 · 2n − 1/3 − 3/5 · (1/3)n + (12/59 + 18/1003 √17)((5+√17)/18)n + (12/59 − 18/1003 √17)((5−√17)/18)n
浮動小数で比べると「だいたい合う」しか言えないので、ℚ(√17) で計算した。後ろの 2 項は共役なので、(5 + √17)n = p + r√17 を BigInt で回せば有理数部分の 2 倍になる。係数は wikitext の \frac{..}{..} から抜き出したものをそのまま使っている。
let p = 1n, r = 0n;
for (let i = 0; i < n; i++) [p, r] = [5n * p + 17n * r, p + 5n * r];
// (c + e√17)(p + r√17)/18^n とその共役の和 = 2(cp + 17er)/18^n
const rational = c.mul(new Q(p)).add(e.mul(new Q(17n * r)));
この式 × 9n が、3n 局面の**順序対すべて（同じ局面どうしを含む）**の距離の総和と、n = 1..7 で整数として一致した（n = 7 で 320,782,470）。平均は「同じ局面を選ぶ場合も含めた 9n 通り」で割ったもの。
グラフについての主張
- 「どの局面からも、1 本の杭に全部集める最短経路はちょうど 1 本」: 5 枚までの全局面で確認
- 「どの 2 局面の間にも最短経路は 1 本か 2 本」: 5 枚までの全対で最大 2
- 「自己交差しない最長経路も 1 本か 2 本」: 3 枚まで全対を DFS で確認、最大 2
- 自己交差しない経路（同じ局面を 2 度通らない経路）の数 Nh = 2, 12, 1872, 6563711232（OEIS A125295）: Wikipedia は漸化式 Nh+1 = Nh2 + Nh3 で出しているので、こちらは漸化式を使わず、81 頂点のグラフで経路を 1 本ずつ全部たどって数えた（
tools/paths.c、12 スレッドで 554 秒）。4 枚で 6,563,711,232 本、一致
隣の杭にしか動かせない版、2 進数の解
- 隣どうしの杭にしか動かせないとき、端から端まで 3n − 1 手、その経路は 3n 局面を全部通り、全部が真ん中の杭に揃うのは (3n − 1)/2 手目: 8 枚まで幅優先で確認
- 8 枚の 216 手目の局面（2 進数 11011000 から各円盤の位置を読む例）と、その手で円盤 4 が杭 2 から杭 1 に動くこと: 一致
- m 手目の移動元・移動先を C の式で出す 2 つの書き方
(m & m - 1) % 3→((m | m - 1) + 1) % 3と(m - (m & -m)) % 3→(m + (m & -m)) % 3: wikitext から式の文字列を抜き出し、C と JavaScript で演算子の優先順位が同じなのを利用してnew Function('m', 'return ' + 式)でそのまま評価した。「奇数枚ならこのまま、偶数枚なら杭 1 と 2 を入れ替える」という但し書きどおりに、1〜12 枚で再帰解と一致
合わなかった 1 つ: 日本語版のビット演算
日本語版 Wikipedia にも同じ式がある。
「(n&(n-1))%3 番目の棒にある円盤を ((n|(n-1))+1)%3 番目の棒に移動する」
節の冒頭は「すべて左端の棒にある状態からすべて右端の棒に移動させる場合」。ところが英語版にある偶奇の但し書きが無い。そこで、式のとおりの手を実際の盤で 2n − 1 回指してみた（元の杭のいちばん上の円盤を動かし、置けない手があれば失敗）。1〜12 枚で、塔が最後にどこにあるか:
R M R M R M R M R M R M （R = 杭 2、M = 杭 1）
どの手も合法で塔は完成するが、偶数枚では杭 1 にできる。左端を 0 番とするなら杭 1 は真ん中で、杭の番号の付け方をどう変えても、偶数枚と奇数枚の両方で右端に行くことはない。日本語版の他の主張（2 進数から各円盤の位置を読む規則、最小の円盤の回り方、264 − 1 = 18,446,744,073,709,551,615、1 秒 1 手で約 5845 億年、杭が円盤より多いときの 2n − 1）はすべて一致した。
公表値は手で写さない
tools/fetch-literature.mts が次のものを取ってきて tools/literature.json に書く。
- Wikipedia（英・日）の wikitext と版番号（API 経由）。数値・式・C の式の文字列は正規表現で抜く
- OEIS の JSON（A007664、A382111、A125295、A000225、A001511、A024023）。A125295 の 5 項目以降は倍精度に収まらないので文字列でも持つ
- Korf (2004) と Korf & Felner (2007) の PDF を
pdftotextで
論文は 2 段組で、ここでつまずいた。pdftotext -layout だと表の列はきれいに揃うが、本文は左右の段が 1 行ずつ交互に混ざり、「588 states at depth 130」の文が途中で切れて正規表現に引っかからない。レイアウトなしだと本文は読む順になるが、表は列ごとにばらばらになる。そこで同じ PDF を 2 通りに変換し、表は -layout 版から、本文の文は読む順の版から抜いている。
npm run stats は src/checks.ts のチェックと C のログの照合を全部回し、公表値と計算値を並べた src/stats.json を書く。予期しない不一致があれば非ゼロで終わる。デモページの表もこの記事の数字も、このファイルから取っている。
| 出典 | 照合数 | 一致 |
|---|---|---|
| Korf (2004) 表 2（1〜17 枚） | 17 | 17 |
| Korf (2004) 表 3（1〜17 枚） | 17 | 16 |
| Korf 2004 / Korf & Felner 2007 の 588 の文 | 2 | 2 |
| OEIS（A007664 ×2、A382111、A000225、A001511、A024023、A125295） | 7 | 7 |
| Wikipedia 英語版（OEIS と重なる 3 個を含む） | 29 | 29 |
| Wikipedia 日本語版 | 6 | 5 |
| 計 | 78 | 76 |
まとめ
- 局面は p 進数 1 つ。 手は 1 桁の書き換えで、足し算 1 回。4 本 12 枚の 1,677 万局面までタブで全部解ける
- 2 ビット幅優先で 17 枚まで。 「未訪問・今の層・次の層・済み」の 4 値と、層ごとのビット演算 1 回の書き換え。4 GiB で 172 億局面
- Korf の表は 17 行とも再現する。 15 枚だけ半径 130 > 129 で、588 局面。表 3 は 1 枚の行だけ、論文自身の「切り上げ」の規則と合わない
- 588 は「大きい円盤を 1 回だけ動かす」経路で決まっている。 残り 14 枚は、いちばん近い 2 個のゲートウェイから 65 手（184 個）か 66 手（12 個）。どのゲートウェイ経由でも塔より 1 手遠い
- 式は書かれたとおりに評価する。 466/885 は ℚ(√17) で、C の式は文字列のまま実行して。日本語版のビット演算の式は、偶数枚では塔が真ん中の杭に行く
テスト 10 件。ソルバー内蔵パズル第 79 弾。
参考文献:
- R. E. Korf, "Best-First Frontier Search with Delayed Duplicate Detection", AAAI-04, pp. 650–657 (2004), https://cdn.aaai.org/AAAI/2004/AAAI04-103.pdf
- R. E. Korf, A. Felner, "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem", IJCAI-07 (2007), https://www.ijcai.org/Proceedings/07/Papers/374.pdf
- T. Bousch, "La quatrième tour de Hanoï", Bull. Belg. Math. Soc. Simon Stevin 21 (2014) 895–912
- Wikipedia, "Tower of Hanoi"（revision 1375651786, 2026年9月19日版。2026年9月30日参照）
- Wikipedia, 「ハノイの塔」（版 109772663, 2026年6月1日版。2026年9月30日参照）
- OEIS A007664, A382111, A125295, A000225, A001511, A024023
デモ: https://sen.ltd/portfolio/tower-of-hanoi/
リポジトリ: https://github.com/sen-ltd/tower-of-hanoi