のりのり（Norinori） を、3 つのルールセット内蔵でブラウザに実装した。盤は領域に切り分けられている。マスを塗る。どの領域にもちょうど 2 マスの塗りがある。そして塗りマスは必ずちょうど 1 つの塗りマスと隣接する——つまり塗りマス全体がドミノに分解され、ドミノは領域の境界をまたいでよい。ここまでがルールの全部だ。気づいてほしいのは、盤には数字が 1 つも書かれていないこと。このシリーズの他のパズルは全部「数字を削る生成器」を持っていたが、のりのりには削るものが無い。領域の切り方そのものがパズルであり、そのせいで「変数の取り方」も「生成の仕方」も別物になる。ソルバー内蔵パズル第 26 弾。
🌐 ライブデモ: https://sen.ltd/portfolio/norinori/
📦 GitHub: https://github.com/sen-ltd/norinori
ルール
- 盤は領域（任意形のポリオミノ）に分割されている
- どの領域にもちょうど 2 マスの塗りがある
- 塗りマスは、上下左右にちょうど 1 つだけ塗りマスを持つ
3 番目は言い換えると「塗りマス全体がドミノ（1×2 のペア）にちょうど分解される」だ。そしてドミノは領域の境界をまたいでよい。
以上。数字は無い。
数字が無いと何が変わるか
このシリーズでずっと同じ形をしていた部分が、2 か所とも壊れる。
| 数字のあるパズル | のりのり | |
|---|---|---|
| 生成器が動かすもの | どの数字を残すか | 領域の切り方そのもの |
| 難易度のつまみ | 残す数字の枚数 | どの切り方を採用するか |
| 自然な変数 | マス | 領域 |
最後の行が本題だ。
変数を「マス」から「領域」へ持ち上げる
領域を変数だと思ってみる。k マスの領域が下す決定は 1 つしかない——どの 2 マスを塗るか。だからドメインは C(k,2) 個のペアで、しかも小さい。出荷している盤の平均領域サイズは 4 マス、つまり 6 ペアだ。
この持ち上げをすると、「ドミノが盤の上を勝手に歩き回る」という広い条件が、隣り合う領域どうしの普通の二項制約になる。両方の領域を候補ペアから読み、それ以外は盤面から読み、塗りになったマスが「塗り隣接 2 つ以上」や「相手候補ゼロ」になっていないかを見るだけだ。あとは教科書どおりの AC-3 で回る。
const kept = live[i].filter((p) =>
live[j].some((q) => binaryOk(state, puzzle, i, meta[i].pairs[p], j, meta[j].pairs[q])),
);
if (kept.length === 0) return null;
if (kept.length < live[i].length) {
live[i] = kept;
for (const k of meta[i].neighbours) if (k !== j) push(k, i);
}
マスへ書き戻すのは自明だ。生き残った全ペアが含むマスは塗り確定、1 つも含まないマスは白確定。
この二項チェックは意図的に健全だが完全ではない。1 マスは 3 つの領域に接しうるのに、見ているのは 2 つだからだ。3 つ目のルールセットが要る理由がここにある。
3 つのルールセット
local — 領域を数えて、4 近傍を見て、繰り返す。マスから一歩も出ない解き手の目に映るのりのり。反証として出荷する。
pairs — local + 領域変数の弧無矛盾。合同の不動点まで回す。
probe — singleton consistency。あるマスを塗りと仮定して pairs を回し、盤が死んだら白確定。逆も同様。
到達距離を、解けるかどうかのフィルタを一切かけずに生成した一意盤で測る（かけると最後の列が循環論法になる）：
| サイズ | local | pairs | probe | 領域数 | 平均領域サイズ |
|---|---|---|---|---|---|
| 5×5 | 0% | 55% | 100% | 6.0 | 4.17 |
| 6×6 | 3% | 53% | 100% | 9.0 | 4.00 |
| 7×7 | 0% | 33% | 100% | 11.9 | 4.10 |
| 8×8 | 0% | 62% | 100% | 15.8 | 4.05 |
局所ルールはほぼ 1 枚も終わらない（6×6 の 3% は 60 枚中 2 枚）。
900 局面のプロパティテストが逆側から同じことを言う：
local が持ち上げより多く決めた局面 ...... 0 / 900 （包含）
持ち上げが local より多く決めた局面 ...... 509 / 900 （57%）
全局面平均の差 ........................... +11.4 マス
0 の側は運ではなく構造だ。pairs は local の全ルールを含んでいるので包含は定義から従う。テストはそれを釘付けにしているだけ。
生成が本番
さて、削る数字が無い。生成器が動かせるのは領域の切り方だけだ。
では適当に切ればいいのか——まったくダメだった。ランダムに切った領域は、一意になるどころかそもそも解が 1 つも無いことがほとんどだ：
| サイズ | 解が 0 個 | ちょうど 1 個 | 2 個以上 |
|---|---|---|---|
| 5×5 | 62% | 5% | 33% |
| 6×6 | 77% | 2% | 22% |
| 7×7 | 93% | 0% | 7% |
7×7 で 93% が塗り方ゼロ。使えるのは 0%。ランダム生成は完全に死んでいる。
逆から作る
なので塗り方を先に引く。引くのは induced matching（誘導マッチング）——どの 2 本も互いに接していないドミノの集合だ。これは「のりのりの塗りマス集合が満たすべき形」そのものなので、引いた時点で既に合法な塗り方になっている。あとはその周りに、塗りマス 2 個ずつを含む連結領域を育てて、余ったマスを一番小さい隣の領域へ流し込む。
そして、密度が全てだった
ここで 1 つの数字が全部を決める。どの領域も塗りマスをちょうど 2 個持つのだから、
平均領域サイズ = 2 ÷ 塗りマスの割合
が強制される。つまり——
| サイズ | 素朴な貪欲マッチング | + 抜き差しパス | 強制される平均領域サイズ |
|---|---|---|---|
| 6×6 | 37% 塗り | 50% 塗り | 5.37 → 4.00 |
| 7×7 | 38% 塗り | 49% 塗り | 5.21 → 4.12 |
| 8×8 | 35% 塗り | 48% 塗り | 5.66 → 4.21 |
| 10×10 | 36% 塗り | 48% 塗り | 5.59 → 4.15 |
素朴な貪欲マッチングは 36% あたりで止まる。すると平均領域サイズが 5.4 に強制され、ドメインは C(5,2) 以上、盤は解が数百個あるグズグズになる。実測でも解数の上限 200 に張り付いた。
抜き差しパス——ランダムに 1 本抜いて、シャッフルした辺順で貪欲に詰め直し、本数が減らなければ採用——を回すと 48〜50% まで届く。これは格子の詰め込み限界に近い。たったこれだけで盤の締まり方が一桁変わる。
let best = refill([]);
for (let t = 0; t < rounds; t++) {
const trimmed = best.slice();
trimmed.splice(Math.floor(rng() * trimmed.length), 1);
const grown = refill(trimmed);
if (grown.length >= best.length) best = grown;
}
残りは反例を歩いて潰す
密度を上げても、まだ解が 2〜数個残る盤が出る。ここで解数を目的関数にした山登りは効かなかった——領域への編集はほとんどが解数を変えないので、平坦な地形をさまようだけになる（実測でも 60 → 10 まで落ちたあと振動して収束しなかった）。
効いたのは反例を歩くやり方だ。
- 意図した解
S以外の解S'を 1 つ見つける -
S'が塗っていてSが塗っていないマスkを選ぶ -
kを隣の領域へ移す
この 1 手は必ず S' を殺す。k の元の領域は S' の下で塗りが 1 個に、移った先は 3 個になるからだ。一方 S は無傷で生き残る——k は S では白なので、どちらの領域の塗り個数も変わらない。狙った反例に対して毎回確実に前進する（新しい反例が生まれることはあるが、それは次の周で潰す）。
おまけの定理：解の領域グラフは必ずサイクルの集まり
これは書いていて気づいた。
- どの領域も塗りマスをちょうど 2 個持つ
- どの塗りマスもちょうど 1 つのドミノに属する
だから解を領域へ射影すると——各ドミノを「2 マスが属する領域どうしを結ぶ辺」（同一領域内なら自己ループ）にすると——どの領域も次数がちょうど 2 になる。
つまり射影は 2-正則マルチグラフ、すなわち全領域を覆うサイクルの直和だ。出荷盤 919 領域での実測：
ドミノ ................................... 919 本
領域境界をまたぐもの ..................... 233 本 (25%)
長さ 1 のサイクル（領域が自前でドミノを持つ） 686 (87%)
長さ 2 のサイクル（2 領域が半分ずつ交換） .. 88 (11%)
長さ 3 ................................... 15 (2%)
長さ 4 ................................... 3 (0%)
regionCycles がこの分解を返し、プロパティテストが生成した全盤で次数 2 を要求している。
2 つのルール、どちらも効いている
出荷している 5×5 盤で、検証器の側からルールを片方ずつ外して数え直す：
領域の個数ルールを外す ... 7358 通り — 40 枚すべてで同じ数
ドミノルールを外す ....... 中央値 54000 通り（最悪 77760）
どちらを外しても一意 ..... 0 / 80
1 行目が面白い。ドミノルールしか残っていないと、盤の領域は一度も読まれない。だから答えは「5×5 格子の誘導マッチングの個数」という格子の性質であって、パズルの性質ではなくなる。逆に個数ルールしか残っていないと各領域が独立にペアを選ぶので、答えは C(|R|,2) の総積になる。どちらも単独では何も決めていない。
健全性：ブルートフォースを 2 本置く
シリーズの標準装備に 1 本足した。伝播とコードを一切共有しない全数探索を、わざと違う経路で 2 本用意する。
-
countBrute— マスを行優先で歩く。枝刈りは漸進的なものだけ（領域の塗り個数、4 近傍が全部確定したマスのドミノ条件） -
countByRegions— 領域を歩き、各領域の 2-部分集合を選ぶ
この 2 本が食い違うのは「マス ↔ 領域の翻訳そのものが間違っているとき」だけだ。今回の主題が「マスから領域への持ち上げ」である以上、そこを別々に検算しておく価値がある。
そして解数を 4 通りで数える——brute 2 本 + ルールセット探索。不一致は「どれかが解を落としたか捏造した」という意味になる。全 124 テスト。
まとめ
- のりのりは盤に何も書かれていない。領域の切り方がパズルの全部
- だから自然な変数はマスではなく領域。ドメインは
C(k,2)ペアで平均 6 個しかなく、ドミノの広い条件が隣接領域どうしの二項制約になる。あとは AC-3 - マスから出ない
localルールセットの完走率はほぼ 0%。900 局面では 509/900 で持ち上げが勝ち、平均 +11.4 マス - 削る数字が無いので生成が本番。ランダムな領域分割は 7×7 で 93% が解ゼロ・一意 0%
- なので塗り方（誘導マッチング）を先に引き、その周りに領域を育てる。ここで密度が全て——「平均領域サイズ = 2 ÷ 塗り割合」が強制されるので、貪欲の 36% では領域 5.4 マスでグズグズ、抜き差しパスで 48〜50% に上げると領域 4.0 マスで締まる
- 残りは反例を歩いて潰す。
S'が塗ってSが塗らないマスを隣の領域へ移す 1 手は、Sを無傷のままS'を必ず殺す - おまけの定理：解を領域へ射影すると常に 2-正則マルチグラフ＝サイクルの直和。実測で 87% が長さ 1、最長 4、ドミノの 25% が境界をまたぐ
- 健全性は経路の違う 2 本のブルートフォース込みの 4 カウンタ解数全一致で固定。全 124 テスト
次は何のパズルを潰そうか。
SEN 合同会社 — ソフトウェア開発・技術コンサルティング