ペグ・ソリテア（英国式 33 穴盤・欧州式 37 穴盤）を、ソルバー内蔵でブラウザに実装した。中央の穴だけ空けて始める英国盤の問題について、1 手ごとに到達できる局面を盤の 8 対称で 1 代表に畳んで幅優先で全部たどり、Node 1 プロセス 126 秒で 187,636,299 局面（対称を除いて 23,475,688）を数え切った。1 局面ごとに「そこへ至るジャンプ列の数」を運び、対称で畳んだまま割り算で戻す工夫で、中央に 1 本残して終わる解は 40,861,647,040,079,968 通り。行き止まり・勝ち残り局面・ジャンプ列の数を含め、OEIS の 6 本の数列（A335656 / A112737 / A350561 / A350998 / A351286 / A112738）と全項一致した。勝ち残りの判定は探索ゼロで、「ジャンプ列を逆にしてペグと穴を入れ替えても合法」という双対性だけで出る。そして Wikipedia 英語版の「到達できる 23,475,688 局面は全配置 2^33 の約 2.2%」は、実際には 0.27%。2.2% になるのは対称で畳まない 187,636,299 の方（2.18%）で、分子と分母で数え方が食い違っていた。GF(4) の不変量（位置クラス）は、最後の 1 本が残りうる穴を探索前に絞り、欧州盤の中央問題が解けないことを 0 ノードで示し、欧州盤で解ける単一空所の出発点が Brassine (1981) の 3 つしかないことをそれ単独で決める。ソルバーは死局面メモと後ろ向きの終盤表に加え、盤の対称性が誘導する 8 通りの手順序を予算を分けて回すことで、英国盤の単一空所問題 125 問のうち盤順序だけでは 70 問しか解けなかったものを 125 問まで解く。テスト 15 件。ソルバー内蔵パズル第 75 弾。
デモ: https://sen.ltd/portfolio/peg-solitaire/
リポジトリ: https://github.com/sen-ltd/peg-solitaire
ルール
- 盤の穴のうち 1 つだけ空けて、残りすべてにペグを立てる
- ペグは縦か横に隣のペグを跳び越えて、そのすぐ先の空いた穴に移る。跳び越されたペグは取り除く
- 跳べなくなったら終わり。ペグが 1 本だけ残れば成功。最初に空けた穴にちょうど残れば完璧
英国盤は 7×7 から四隅の 2×2 を除いた十字形の 33 穴、欧州（フランス）盤はそこに内側の角を 4 つ足した 37 穴。ジャンプの種類は英国盤 76、欧州盤 92 ある。
穴に 0 から番号を振り、ペグのある穴をビットで表せば、局面は 33〜37 ビットの整数になる。JavaScript の number は 2^53 まで正確なので 1 個の number で持てるが、ビット演算は 32 ビットまでしか効かない。ホットループでは下位 32 ビットと上位を別々の int にして、ジャンプはマスク 2 個の比較と XOR で済ませる。
// 跳ぶ側 2 本 (from, over) にペグがあり、着地点 (to) が空いていれば合法
if ((lo & f) === f && (hi & fh) === fh && (lo & t) === 0 && (hi & th) === 0) {
const nlo = lo ^ (f | t), nhi = hi ^ (fh | th); // 3 か所を反転
...
}
探索の前に分かること: 位置クラス
4 元体 GF(4) = {0, 1, p, p²}（p² = p + 1）を使う。行 r・列 c の穴にあるペグに、A 用に p^(r+c)、B 用に p^(r−c) を割り当て、盤上の全ペグについて足す。一直線に並ぶ 3 穴の値は p^k, p^(k+1), p^(k+2) の形になり、
p^k + p^(k+1) = p^k (1 + p) = p^k · p² = p^(k+2)
なので、「手前 2 本を消して先に 1 本置く」ジャンプの前後で和は変わらない。(A, B) の組は 16 通りで、これが位置クラス（de Bruijn 1972、Conway の「3 の規則」と同じもの）。GF(4) の足し算は 2 ビットの XOR で書ける。
const POW = [1, 2, 3]; // p^0, p^1, p^2 を 2 ビットで
const pw = (k: number) => POW[((k % 3) + 3) % 3];
export function positionClass(board: Board, pos: number): number {
let a = 0, b = 0;
for (let i = 0; i < board.n; i++) {
if (!has(pos, i)) continue;
a ^= pw(board.row[i] + board.col[i]);
b ^= pw(board.row[i] - board.col[i]);
}
return a * 4 + b;
}
最後の 1 本は、その穴自身のクラスが今の局面のクラスと一致する穴にしか残れない。ページでは、それを満たす穴を金色の輪で常に表示している。
- 英国盤の中央問題: 輪は d1・a4・d4・g4・d7 の 5 か所だけ。中央と、4 本の腕の先端。Wikipedia の「成功で終わりうる盤上の位置は 5 つ」はこれ
- 欧州盤の中央問題: 輪が 1 つも出ない。37 穴から中央を抜いた局面は、どの 1 本とも違うクラスにいる。つまり解けない。ソルバーは 0 ノードでそう答える。同じ問題をクラス判定なしで探索させると、10,000,001 ノード（8.2 秒）かけても決着しなかった
- 欧州盤の単一空所問題: 37 穴のどれを空けて始めるかは、対称性で 8 通り。そのうちどこかに 1 本残せるクラスの出発点は c1・d2・d3 の 3 つだけで、Wikipedia が Brassine (1981) を引いて「解のある出発点は 3 つ」と載せているものと一致する。載っている 3 本の解を再生すると、どれも合法で c1 → e1、d2 → d3、d3 → d2 で終わった。欧州盤でどの単一空所が解けるかは、クラス判定だけで決まる（不可能の側はクラス判定が、可能の側は公開解が証明している）
英国盤の単一空所 → 単一残存問題（1 か所空けて始め、指定した 1 か所に 1 本残す）は 33 × 33 = 1,089 問あるが、クラス判定を通るのは 125 問だけ。欧州盤では 1,369 問中 64 問。
英国盤の中央問題の全局面を数える
素直に書くと、メモリで死ぬ
最初の版は、各手数の局面を対称性で畳まずに、2^26 スロットのオープンアドレス表（キー・カウント下位・カウント上位の Float64Array 3 本、計 1.6 GB）で持った。ピークの 17 手目は約 2,900 万局面なので、負荷率は 0.43 で問題ないはずだった。
ところが 8 手目で 7.8 万局面を作るのに 10 秒かかった。プロファイルでは時間のほぼ全部が挿入関数で、線形探査の衝突回数を数えると 107 万回の挿入でたった 1,422 回。ハッシュは無実だった。/usr/bin/time -l を付けると答えが出た。表を 2^22 にすると 2.0 秒で終わる同じ処理が、2^26 では 47.99 秒、うち sys 31.93 秒。マシンは 24 GB あるが、スワップを 9 GB 使っている状態で、1.6 GB をランダムにつつく表はページ圧縮とスワップの往復になっていた。
対称性で 1/8 に畳む
盤には正方形の 8 つの対称性がある。局面を「8 通りの像のうち数値が最小のもの」に正規化すれば、ピークの手数でも 363 万代表で済み、表は 2^23 スロット（200 MB）で足りる。
正規化は 33 ビットを 11 ビットずつ 3 つに切り、対称ごとに「11 ビットの塊 → 像のビット」の表（2,048 項目 × 3 × 7）を引いて足すだけ。
function canon(key: number): number {
const lo = key >>> 0;
const hi = (key - lo) / TWO32;
const v0 = lo & 0x7ff, v1 = (lo >>> 11) & 0x7ff, v2 = (lo >>> 22) | (hi << 10);
let best = key;
STAB = 1; // key を動かさない対称の数（恒等写像を含む）
for (let g = 0; g < 7; g++) {
const t = SYM[g];
const img = t[0][v0] + t[1][v1] + t[2][v2];
if (img < best) best = img;
if (img === key) STAB++;
}
return best;
}
代表 1 つが表す実際の局面数は 8 / STAB。全局面数も行き止まり数も、代表ごとにこれを足せば出る。
ジャンプ列の数は、畳んだまま運んで割り戻す
厄介なのは「そこへ至るジャンプ列の数」。出発局面は 8 対称すべてで不変なので、同じ類の局面はどれも同じ数の列で到達される。そこで代表 P には「P そのものに至る列の数」paths(P) を持たせる。
P から 1 手で q に行き、その代表が Q のとき、Q の積算値に paths(P) × |P の軌道| を足す。こうして集めた値は「P の軌道の全要素から Q の軌道の全要素への手の本数 × 列数」になり、ちょうど paths(Q) × |Q の軌道| に等しい。だから手数の処理が終わったら、各代表を自分の軌道の大きさで割り戻す。割り算が整数にならなければ例外を投げるようにしてあり、一度も投げていない。
列の数は 10^21 を超えるので、1 つの数を (下位 32 ビット, 上位) の 2 つの double で持ち、足し算のたびに繰り上げる。上位は 2^53 未満に収まる。
勝ち残りは探索しない: 補集合の双対性
「この局面からまだ中央に 1 本で終われるか」を全局面について知りたい。後ろ向きに探索し直す必要はない。
ジャンプ (a を b 越しに c へ) を考える。前の局面 s では a・b にペグ、c が空き。後の局面 t では a・b が空き、c にペグ。ここでペグと穴をすべて入れ替えると、補集合 t̄ では a・b にペグ、c が空きで、そこから a を b 越しに c へ跳ぶと s̄ になる。つまり
s → t が合法なジャンプなら、t̄ → s̄ も合法なジャンプ
で、列を逆順にして補集合を取れば合法な列に戻る。中央 1 本の補集合は出発局面そのものなので、
n 手目の局面 s から中央 1 本で終われる ⟺ s̄ が出発局面から 31 − n 手で到達できる
各手数の代表を整列した配列にしておけば、判定は二分探索 1 回。補集合は対称と可換なので、代表の補集合を正規化して引けばよい。表の「勝ち残り」列が前から読んでも後ろから読んでも同じなのは、この双対性そのもの。
結果
Node 1 プロセスで 126 秒。抜粋（全 32 行はページにある）:
| 手数 | 残りペグ | 局面 | 対称を除く | ジャンプ列の数 | 行き止まり | 勝ち残り |
|---|---|---|---|---|---|---|
| 0 | 32 | 1 | 1 | 1 | 0 | 1 |
| 4 | 28 | 296 | 39 | 400 | 0 | 292 |
| 8 | 24 | 77,559 | 9,751 | 2,076,744 | 0 | 49,236 |
| 12 | 20 | 4,138,302 | 517,854 | 18,687,793,880 | 0 | 902,056 |
| 15 | 17 | 20,773,236 | 2,598,215 | 13,794,351,556,920 | 40 | 1,841,556 |
| 16 | 16 | 26,482,824 | 3,312,423 | 112,576,101,214,496 | 176 | 1,841,556 |
| 17 | 15 | 28,994,876 | 3,626,632 | 857,945,953,884,624 | 302 | 1,639,652 |
| 20 | 12 | 15,425,572 | 1,930,324 | 222,984,258,240,522,544 | 6,890 | 546,308 |
| 24 | 8 | 800,152 | 100,565 | 56,487,846,008,148,393,896 | 33,051 | 16,628 |
| 28 | 4 | 2,529 | 348 | 287,520,477,058,517,555,304 | 1,295 | 60 |
| 30 | 2 | 32 | 7 | 16,301,649,363,425,363,800 | 28 | 4 |
| 31 | 1 | 5 | 2 | 81,723,294,080,159,936 | 5 | 1 |
- 到達できる局面は合計 187,636,299（対称を除いて 23,475,688）。最も多いのは 17 手目の 28,994,876
- そのうち中央 1 本で終われる局面は 13,428,122 で、7.16% しかない（対称を除いて 1,679,072）
- 行き止まりは合計 162,352 局面。最短は 6 手目の 4 局面で、Wikipedia の「最短の失敗は 6 手」と一致
- 中央 1 本で終わるジャンプ列は 40,861,647,040,079,968 通り。腕の先端 d1 で終わる列は 10,215,411,760,019,992 通りで、中央のちょうど 4 分の 1。d1 に 1 本残る直前は d2・d3 の 2 本しかありえず、そこから d2 が d3 を越えれば中央、d3 が d2 を越えれば d1 に行く。中央へ入る 4 方向は対称で等しいので、中央 = 4 × d1 になる
検証として、6 本の OEIS 数列を統計スクリプトに埋め込み、1 項でも食い違えば終了コード 1 で止まるようにしてある。
| OEIS | 内容 | 結果 |
|---|---|---|
| A335656 | n 手後の局面数 | ok (32 terms) |
| A112737 | 同、対称を除く | ok (32 terms) |
| A350561 | 長さ n のジャンプ列の数 | ok (23 terms) |
| A350998 | n 手後の行き止まり | ok (32 terms) |
| A351286 | 中央 1 本で終われる局面 | ok (32 terms) |
| A112738 | 同、対称を除く | ok (32 terms) |
A350561 は OEIS の data 欄に載っている 23 項（22 手目まで）と一致した。23 手目以降の 9 項もここで計算しているが、b-file とは照合していない。
Wikipedia の「2.2%」
Wikipedia 英語版の Peg solitaire には次の一文がある。
Note that the total number of reachable board positions (sum of the sequence) is 23,475,688, while the total number of possible board positions is 8,589,934,590 (33bit-1) (2^33), so only about 2.2% of all possible board positions can be reached starting with the center vacant.
23,475,688 は A112737（対称を除いた局面数）の総和で、上の台帳とも一致する。ところが 23,475,688 ÷ 2^33 は 0.27% で、2.2% ではない。2.2% になるのは、対称で畳まない局面数 187,636,299（A335656 の総和）を 2^33 で割ったとき（2.18%）。分母の 2^33 は対称で畳まない全配置なので、比べるなら分子も畳まない方を使うのが筋で、「2.2%」という結論自体は正しい。書かれている分子が違う。ついでに書くと 8,589,934,590 は 2^33（8,589,934,592）とも 2^33 − 1（8,589,934,591）とも合わない。
同じ数え方の二重性は、台帳を作るときにも効いてくる。対称で畳んだ代表と、実際の局面の両方を毎回数えていないと、どちらの数を見ているのかすぐ分からなくなる。
ソルバー
Solve ボタンの中身は深さ優先探索で、段は 3 つ。どれも健全で、切っても遅くなるだけ。
- クラス判定: 出発局面と目標の 1 本のクラスが違えば、探索せずに不可能と答える
- 死局面メモ: 解けないと分かった局面を覚えておく
- 終盤表: 目標の 1 本から逆ジャンプ（c のペグが空の b を越えて空の a に戻り、a・b を埋める）で、ペグが K 本以下で目標に終われる局面を全部作っておく。前向きの探索は K 本まで減った時点で表を引けば済む（双方向探索）。前の節の双対性から、中央を目標にした表の k 本の局面数は A335656 の (k − 1) 項目になり、テストで確かめている
中央問題での各段の効き目（予算 10,000,000 ノード）:
| 盤 | 段 | 結果 | 展開ノード | ms |
|---|---|---|---|---|
| english | class + memo + endgame | solved | 31 | 4,470 |
| english | class + memo | solved | 2,312 | 2 |
| english | memo only | solved | 2,312 | 2 |
| english | neither | solved | 20,275 | 31 |
| european | class + memo + endgame | class | 0 | 0 |
| european | class + memo | class | 0 | 0 |
| european | memo only | budget | 10,000,001 | 8,231 |
| european | neither | budget | 10,000,001 | 16,952 |
英国盤は 3 段とも入れると 31 ノードで解ける（ほとんどの時間は 12 本の終盤表の構築）。欧州盤ではクラス判定だけが決め手になる。
単一空所問題と、手の順序の偏り
英国盤の 125 問（クラス判定を通る単一空所 → 単一残存問題）を、1 問 2,000,000 ノード・12 本の終盤表で解かせた（対称で移り合う問題は 1 回だけ解き、類の大きさで数えている）。ジャンプを盤の番号順に試すだけだと、解けたのは 70 問。しかも中央から始める問題で、腕の先端 4 か所（d1・a4・g4・d7。回転と鏡映で互いに移り合う、実質同じ問題）のうち、d7 には残せたのに d1・a4・g4 には予算内で残せなかった。同じ問題を鏡に映しただけで結果が変わるのは、探索が最初の数手の選び方に予算をほとんど使い切っているということ。
そこで、盤の 8 つの対称のそれぞれが誘導する手の順序（g で映した盤を番号順に試すのと同じ順序）を用意し、予算の 1/8 ずつ順番に試す。死局面メモと終盤表はすべての順序で共有できる。解けない局面は、どの順序で調べても解けないからだ。
for (let g = 0; g < all.length && !found; g++) {
order = all[g];
out = false;
path.length = 0;
limit = nodes + share; // 予算の 1/8
found = dfs(lo, hi, pegs);
if (!found && !out) break; // 予算内で尽きた = どの順序でも解けない
}
これで125 / 125 問が解けた。英国盤では、クラス判定を通る単一空所 → 単一残存問題はすべて解ける。欧州盤では同じ条件で 64 問中 16 問が解け、48 問が未決着。欧州盤で「どこでもよいから 1 本残す」を予算 1,000 万ノードで解かせた結果は次のとおり。
| 出発点 | 同じ類の穴 | 結果 | 展開ノード | 最後の 1 本 |
|---|---|---|---|---|
| c1 | 8 | solved | 2,265,259 | b4 |
| d1 | 4 | class | 0 | — |
| b2 | 4 | class | 0 | — |
| c2 | 8 | class | 0 | — |
| d2 | 4 | budget | 10,000,008 | — |
| c3 | 4 | class | 0 | — |
| d3 | 4 | budget | 10,000,008 | — |
| d4 | 1 | class | 0 | — |
d2・d3 から始める問題は、上で再生した公開解が存在するのに、1,000 万ノードの探索では見つからなかった。欧州盤では探索はまだ弱く、何が解けるかを決めているのはクラス判定と公開解の方。
ページ
- 盤（英国 33 / 欧州 37）と目標（中央 / どこでも）を選ぶ。ペグをクリックしてから着地点をクリックで 1 手。Undo と New game
- Edit start で穴をクリックしてペグを足し引きし、好きな出発局面を作れる
- 右のパネルに、残りペグ・合法手の数・クラス (A, B)・最後の 1 本が残りうる穴を常時表示。金色の輪は盤上の同じ情報
- Solve は 8 順序ポートフォリオ（10 本の終盤表・400 万ノード）で解き、見つけた手順を 1 手ずつ再生する。不可能ならクラス判定か網羅探索の結果を、予算切れなら「未決着」と正直に出す
- 下の notes に、全 32 手分の台帳・OEIS 照合・ソルバーの段ごとの計測をすべて載せている
スクリーンショットは英国盤の中央問題を解いている途中の局面で、金色の輪は d1・a4・d4・g4・d7 の 5 か所。
まとめ
- 不変量は探索の前に置く。 GF(4) の 2 ビット XOR 16 通りで、欧州盤の中央問題の不可能性も、欧州盤で解ける出発点の 3 つも決まる。探索が 1,000 万ノードかけても出せない答えが 0 ノードで出る
- 状態空間を全部数えるなら、対称で畳む前にメモリを測る。 1.6 GB の表はスワップの往復で 20 倍以上遅くなった。8 対称で畳めば 200 MB で 126 秒
- 数を運ぶときは軌道の大きさで掛けて、最後に割り戻す。 割り切れなければ例外にしておけば、畳み方の誤りはすぐ見つかる
- 逆向きの探索は双対性で消せる。 列を逆にしてペグと穴を入れ替えても合法なので、勝ち残りの判定は二分探索 1 回。同じ理屈で、終盤表の大きさも前向きの台帳から予言できる
- DFS が鏡像の問題で結果を変えたら、手の順序を疑う。 8 つの対称が誘導する順序を予算を分けて回すと、70 問が 125 問になった
- 公表値は全部再現してから疑う。 OEIS 6 本・解の総数・5 つの終点・最短の失敗・欧州盤の 3 出発点がすべて合った上で、合わなかった 1 つ（2.2%）は、数え方の取り違えだった
数値はすべて npm run ledger と npm run stats が出力した JSON から、ページの notes とこの記事に流し込んでいる。テスト 15 件。ソルバー内蔵パズル第 75 弾。
参考文献:
- N. G. de Bruijn, "A solitaire game and its relation to a finite field", Journal of Recreational Mathematics 5 (1972)
- J. D. Beasley, The Ins and Outs of Peg Solitaire, Oxford University Press (1985)
- M. Brassine, "Découvrez... le solitaire", Jeux & Stratégie (1981年12月)
- OEIS A335656, A112737, A350561, A350998, A351286, A112738
- Wikipedia, "Peg solitaire"（2026年9月26日参照）
デモ: https://sen.ltd/portfolio/peg-solitaire/
リポジトリ: https://github.com/sen-ltd/peg-solitaire