カントリーロード (Country Road) を、5 つのルールセット内蔵でブラウザに実装した。盤面は「国」に分割されていて、1 本の閉じたループがすべての国をちょうど 1 回ずつ通る。数字はその国で使うマスの個数。そして国境をはさんで向かい合う 2 マスを両方とも空にはできない。ソルバー内蔵パズル第 49 弾。
デモ: https://sen.ltd/portfolio/country-road/
リポジトリ: https://github.com/sen-ltd/country-road
ルール
盤面は国に分割されている。マスの中心を通る閉じたループを 1 本引く。交差はしない。そのうえで:
- ループはすべての国をちょうど 1 回ずつ訪れる
- 国の中に書かれた数字は、その国でループが通るマスの個数（数字の無い国は自由）
- 国境をはさんで隣り合う 2 マスは、両方ともループ外にはできない（同じ国の中なら 2 マス空いていてよい）
国を 1 点に潰すと、このパズルはハミルトン閉路問題になる
各国を 1 個のノードに縮約し、国境を共有する 2 国を辺で結ぶ。ルール 1 は「ループが通る国の順序は、全ノードをちょうど 1 回ずつ回る巡回列だ」と言っている。つまり:
ループは領域隣接グラフ上のハミルトン閉路を誘導する。
ここから 2 つ、そのままソルバーの骨格になる帰結が出る。
関節点があれば、その分割には解が無い
ハミルトングラフは必ず 2-連結である。したがって領域隣接グラフに関節点（または橋）がある分割は、どんな数字を印刷しても解を持たない。
いちばん分かりやすい反例が「横帯分割」だ。各行を 1 国にすると領域グラフはパスになり、両端以外はすべて関節点になる。
n×n を行ごとに分割: 関節点 true, ハミルトン false, 解の個数 0 (n = 4, 5, 6)
hasCutVertex は Hopcroft–Tarjan で O(V+E)。数字を 1 個も見ずに盤面を却下できる。グラフのことを何も知らない総当たりカウンタも、独立に 0 を返す。
「国ごとに国境を 2 回横切る」は 2-因子であって、ハミルトン閉路ではない
ループは国に 1 回入って 1 回出るので、その国の国境辺のうちちょうど 2 本が使われる。これは領域グラフ上の次数 2 制約、すなわち 2-因子の緩和だ。そして 2-因子とハミルトン閉路の差は、TSP の人たちが一生かけて潰しているサブツアーそのものである。
このパズルのラダーは、その構造をそのまま段にした:
| 段 | 知っていること |
|---|---|
region |
マス単位の帳簿: 空マスに道は通らない、使った辺の両端は道の上、国境をはさんだ 2 マスが両方空はダメ、数字は使うマス数の上下限 |
once |
各国ちょうど 1 回: 国境辺の使用数はちょうど 2、最低 1 マスは通る、同じ国境は 2 回横切らない、その国で通るマスは国の内側で連結 |
loop |
ループ自身の構造: 次数 2、行き止まり、早すぎる閉路や国を飛ばした閉路、到達不能になった道マス |
macro |
領域グラフのハミルトン性。パズルにつき 1 回だけ全ハミルトン閉路を列挙してビットマスクのカタログにし、以降は集合演算だけ — 「既に横切った国境を全部含み、閉じた国境を 1 つも含まない」閉路を残し、その和集合（＝どの閉路にも無い国境は殺せる）と共通部分（＝全部にある国境は強制）を読む |
probe |
単集合整合性。マスだけでなく辺にも仮定を置く（全マスが決まってもなお道の通し方が 2 通り、ということが起きる） |
macro がサブツアー除去にあたる。全部健全なので、探索なしで完答した段は「解が一意である」証明にもなる。
各段が到達する範囲
すべての国に数字を書いた盤面から始めて、fixpoint で決まったビット（全マス＋全格子辺）の割合:
| サイズ | 盤数 | region | once | loop | macro | probe |
|---|---|---|---|---|---|---|
| 6×6 | 80 | 14.9% | 15.1% | 18.3% | 30.5% | 63.4% |
| 8×8 | 80 | 18.1% | 18.2% | 20.5% | 33.4% | 77.8% |
| 10×10 | 40 | 18.3% | 18.4% | 19.8% | 30.1% | 72.8% |
probe 未満で完答できる盤はほとんど無い（macro の完答率は 6×6 で 1.3%、それ以上のサイズでは 0.0%）。出荷したバンクもそれを裏書きしていて、見つかった最弱グレードは 6×6 で loop、8×8 で macro、10×10 で probe。region や once だけで落ちる盤は、どのサイズにも 1 枚も無かった。
ablation — フルのラダーから 1 段抜く
| サイズ | 抜いた段 | fixpoint で失ったビット | 動いた盤 | probe の仮定回数 |
|---|---|---|---|---|
| 6×6 | −region | 889 | 40/40 | +31.6% |
| 6×6 | −once | 71 | 9/40 | +9.4% |
| 6×6 | −loop | 482 | 36/40 | +28.5% |
| 6×6 | −macro | 607 | 32/40 | +39.2% |
| 8×8 | −region | 1240 | 30/30 | +110.9% |
| 8×8 | −once | 59 | 10/30 | +46.5% |
| 8×8 | −loop | 458 | 30/30 | +116.8% |
| 8×8 | −macro | 591 | 25/30 | +57.8% |
面白いのは once の行だ。fixpoint ではほぼ無料（8×8 で 30 盤合計 59 ビット、動く盤は 1/3）なのに、抜くと探索が同じ事実を仮定 +46.5% で買い直す。増分の表と ablation の表が逆を向くので、両方載せる。
そして、ハミルトン閉路の方が「簡単な半分」だった
ここまでの筋書きだと macro が主役に見える。実際は違った。調べ方は「第 2 解が何を変えているか」を見るだけだ。
| サイズ | 曖昧な盤 | 第 2 解が同じ国の巡回順を歩く | 別の順を歩く |
|---|---|---|---|
| 6×6 | 51 | 92.2% | 7.8% |
| 8×8 | 34 | 85.3% | 14.7% |
曖昧さのほぼ全部が micro 側にある。同じ国、同じ順序、違うのは「国の中でどのマスを使うか」。そしてそれこそ数字が担当すべき仕事なのに、数字はほとんど仕事をしていない — 全部の国に数字を書いても、一意なのは 6×6 で 18.0%、8×8 で 10.0% だけである（クリークが全開示で一意率 100% だったのと対照的だ）。
相関はむしろ逆を向く:
| 領域グラフのハミルトン閉路数 | 6×6 盤数 | 一意率 |
|---|---|---|
| ちょうど 1 | 28 | 7.1% |
| 2–4 | 45 | 17.8% |
| 5–16 | 26 | 30.8% |
macro の自由度がゼロの盤がいちばん一意になりにくい。 交絡は国の大きさだ。小さい国が多い分割は領域グラフを密にする（＝ハミルトン閉路が増える）と同時に、国の中に道を引き回す余地を消す。ダイヤルを回すと、効いていたのは全部サイズの方だったことが見える:
| サイズ | 平均の国サイズ | 一意率 | ハミルトン閉路数の中央値 | ラダー到達率 |
|---|---|---|---|---|
| 6×6 | 2.5 | 40.0% | 7 | 41.6% |
| 6×6 | 3.5 | 20.0% | 4 | 33.3% |
| 6×6 | 4.5 | 6.7% | 2 | 27.7% |
| 6×6 | 6.0 | 3.3% | 1 | 21.3% |
| 8×8 | 2.5 | 18.3% | 54 | 34.6% |
| 8×8 | 6.0 | 1.7% | 4 | 22.7% |
分割は「壁」になりうるので、分割から作らない
分割を先に引く生成器は罠だ。罠の大きさは測れる:
| サイズ | 国数 | 関節点あり | 領域グラフがハミルトン | 解が存在 |
|---|---|---|---|---|
| 6×6 | 4 | 13.3% | 86.7% | 83.3% |
| 6×6 | 6 | 11.7% | 88.3% | 74.2% |
| 6×6 | 8 | 4.2% | 95.8% | 84.2% |
| 6×6 | 12 | 0.0% | 100.0% | 90.0% |
領域グラフのハミルトン性は必要だが十分ではない（右 2 列の差が、国の内側で道が引けずに落ちた分）。
そこで生成は逆から行く。行き詰まりが構造的に起きない手順だ:
- 膨張でループを 1 本育てる。2×2 の最小ループから始め、辺を 1 本選んで隣の 2×2 に押し出し、3 辺の迂回に置き換える。結果は常に単一の閉路になる — 棄却も連結性チェックも要らない。
- ループを連続する弧に切り分ける。弧 1 本が国 1 個の種になるので、ループは既に各国を 1 回ずつ訪れていて、弧の並び順がそのまま領域グラフ上のハミルトン閉路になる。盤面ができる前に macro 問題は解けている。
- ループ外マスの連結塊を、丸ごと 1 つの国に渡す。これがそのままルール 3 になる。
合法性は構造で保証される。買わなければならないのは一意性だけで、それは「ラダーが完答し続ける限り数字を消す」で買う:
| サイズ | 国数 | 残る数字（敵対的な消し方） | 残る数字（ランダムな消し方） |
|---|---|---|---|
| 6×6 | 6.7 | 2.9 | 5.4 |
| 8×8 | 11.3 | 4.7 | 10.1 |
3 つのエンジンと、リポジトリの外にある数
すべての盤を、幾何ヘルパ以外を共有しない 3 通りの方法で数える: 伝播つき探索、マス先行の総当たり（マスを決めてから道の通し方を数える）、ループ先行の総当たり（格子の単純閉路を全列挙して、空マスは補集合として読む）。60/60 盤で一致。
そして全体を、このリポジトリの外にある数に固定する。各マスをそれぞれ 1 国にするとルール 1 は「全マスをちょうど 1 回ずつ訪れる」になり、数字なし盤の解の個数は格子グラフのハミルトン閉路数そのものになる。OEIS A003763:
2×2 全単独マス: 1 4×4: 6 6×6: 1072
2×m 帯: m = 3..8 すべてで 1
さらに「探索なしで完答 ⇔ 一意」を総当たりと両方向で照合し、120 盤で例外 0（完答したのに曖昧: 0 盤、一意なのに止まった: 0 盤）。テストは 37 本。
実装の小さな教訓
デバッグで一番時間を食ったのは、loop 段の「早すぎる閉路」判定だった。閉じた成分のマス数と「ON と分かっているマスの数」を比べていたのだが、1 パスの途中では、辺の方が先に確定してマスがまだ未確定のことがある。道が通っているのにセル配列では空欄、というマスが 1 個あるだけで、閉じたループが「1 マス長すぎる」ように見えて健全なはずの伝播器が正しい解を殺す。
見つけ方はいつものやつで、「ラダーの各段の fixpoint は、総当たりが返すすべての解と 1 ビットも矛盾してはいけない」というテストを回すだけだ。伝播器が 1 個でも不健全なら、「探索なしで完答した」は一意性の証明ではなくなる。
src/country-road.ts ルール・幾何・5 段・レフェリー・領域グラフの定理
src/brute.ts 幾何以外を共有しない 2 つの総当たりカウンタ
src/generate.ts ループ先行の生成、分割、数字の削り
tools/stats.mts この記事の全ての表
デモ: https://sen.ltd/portfolio/country-road/
リポジトリ: https://github.com/sen-ltd/country-road