**ノンダンゴ（Nondango）**を、4 段のソルバー内蔵でブラウザに実装した。禁止されるのは「連続する 3 マスに並んだ 3 つの丸が全部黒」だが、各領域は丸をちょうど 1 つしか黒くしないので、3 つのうち 2 つが同じ領域にあるトリプルは絶対に発火しない。パズルが始まる前から満たされていて、出荷盤の幾何の 34.8% がこれに当たる。そして本体はもっと短い補題だ——答えの中で 1 つの領域の黒丸を同じ領域の別の丸へ動かすと、他の領域は無傷なので「各領域に黒 1 つ」は保たれたまま。これが不正になり得る理由は、動かした先を通る 3 連のうち他の 2 つが既に黒である場合しかない。だから一意な盤は白いままの丸すべてに 3 連を要求し、2 黒の 3 連は白い丸を 1 つしか含まないので 1 本は 1 つしか担保できない。よって
丸 − 領域 ≤ 生きたトリプル。これが盤の持てる選択の総量そのものになる。ソルバー内蔵パズル第 59 弾。
デモ: https://sen.ltd/portfolio/nondango/
リポジトリ: https://github.com/sen-ltd/nondango
ルール
盤が領域に分割されている。いくつかのマスには丸が描かれている。
- 各領域でちょうど 1 つの丸を黒く塗る
- 連続する 3 マスに並んだ 3 つの丸が全部黒になってはいけない。方向は横・縦・2 本の対角の 4 つ
以上。丸の無いマスは領域の一部だが、何も置かない。
短いルールだが、この 2 行から出てくるものが思ったより多かった。
まず 3 分の 1 は死んでいる
禁止されるのは 3 つの丸の組だ。しかし各領域は丸を 1 つしか黒くしない。だから 3 つのうち 2 つが同じ領域にあれば、その 2 つが同時に黒になることは絶対にない。そのトリプルは最初から満たされている。情報をまったく持っていない。
これを死んだトリプルと呼んでソルバーの最初に落とす。出荷盤での割合は小さくない。
| 盤 | 幾何的な 3 連 | 生きている | 死んでいる |
|---|---|---|---|
| 8×8 | 43.1 | 28.3 | 14.8 |
| 12×12 | 146.4 | 95.3 | 51.1 |
全体で 34.8%。領域の平均サイズが 3 マス程度なので、3 連の 3 マスが 2 領域以下に収まることがそれだけ多い。
スクリーンが正しいことは信じずに測ってある。8×8 の全 36 枚について「全トリプルで解く」と「生きたトリプルだけで解く」を走らせ、解の集合ごと一致することを確認した（36/36）。
一手ずらすと何が起きるか
ここからが本題。答えを 1 つ持っているとする。ある領域の黒丸を、同じ領域の別の丸へ動かす。
- 他の領域は一切触っていないので、「各領域に黒はちょうど 1 つ」は保たれたまま
- 黒を 1 つ減らして 1 つ増やしただけ。減らした側が新しい違反を作ることはあり得ない
つまり、この盤面が不正になるとしたら理由は 1 つしかない。動かした先の丸を通る 3 連で、他の 2 つがすでに黒だった——それだけだ。
この 3 連をその丸の証明書と呼ぶことにする。すると:
一意な盤は、答えが白のまま残したすべての丸に証明書を持たなければならない。
これは推測ではなく、そのまま殴って確かめられる。出荷 72 盤で可能な「ずらし」は 2,113 通り。全部が不正になり、全部に証明書があった。
予算の不等式
証明書を数えると、もっと強いことが言える。
2 つが黒である 3 連は、白い丸をちょうど 1 つしか含まない。（3 つ全部が黒なら答えが不正だから、少なくとも 1 つは白。2 つが黒なので、白はちょうど 1 つ。）よって 1 本の 3 連が担保できる丸は高々 1 つ。
したがって
丸の数 − 領域の数 ≤ 証明する 3 連 ≤ 生きたトリプル
左辺は何かというと、盤に置かれた「答え以外の選択肢」の総数そのものだ。領域が持つ丸のうち 1 つは答えなので、残りが選択肢の量になる。つまりこの不等式は、このパズルが持てる面白さの上限を幾何が決めていると言っている。3 連は連続する 3 マスにしか生えないので、そう贅沢には手に入らない。
| 盤 | 白い丸 | 証明する 3 連 | 生きたトリプル | 幾何的な 3 連 |
|---|---|---|---|---|
| 8×8 | 15.4 | 20.3 | 28.3 | 43.1 |
| 12×12 | 43.3 | 60.4 | 95.3 | 146.4 |
余裕は思ったより無い。出荷盤で最もきついものは証明する 3 連が丸の数より 1 本多いだけ、中央値でも 9 本しかない。テストでは 72 盤すべてについてこの不等式を assert している。
生きたトリプルが 1 本も無ければ、それはパズルではない
生きたトリプルが触れている 2 つの領域を繋いでいくと、領域の連結成分ができる。ルールは成分をまたがないので、成分ごとの答えは互いに独立で、盤全体の答えの数は成分ごとの積になる。
だから完全ソルバーは成分ごとの素朴な後戻り探索で足りる。そして重要なのは逆向きの読み方だ:
どの生きたトリプルにも触れていない領域は、それ単独で 1 成分になる。その領域の丸の数が、そのまま答えの数に掛かる。
つまり丸を 2 つ以上持っていて 3 連に一度も現れない領域があれば、その時点で答えは 2 通り以上ある。手も足も出ない。
これも測った。生きたトリプルが 1 本も無いランダム盤を 200 枚集めて解を数えたら、200 枚すべてで答えの数が領域サイズの積とちょうど一致した。出荷 72 盤は 189 個の成分に割れ、うち 114 個が「丸を 1 つだけ持つ領域が 1 つ」——つまり与えられたヒント——で、残りが最大 48 領域の 1 つの塊にまとまる。
二通りの誤読は、どちらもパズルを消す
ノンダンゴのルールは普通「横・縦・斜めに 3 つ並んだ丸」と書かれる。落としやすい語が 2 つあって、方向が逆の間違いになる。
対角線を忘れる
実装で最も起きやすい。方向を 4 本から 2 本に減らすと証明書の大半が消える。結果、出荷 72 盤すべてが一意でなくなった。8×8 は解の数の中央値が 1,268、12×12 は 36 枚全部が 20,000 解の打ち切りを突破する。
「並んだ」を「同じ直線上のどこか」と読む
こちらは制約が強くなりすぎる。1 行に L 個の丸があるとき、合法な黒の集合の数は:
| 直線上の丸 | 連続する 3 つ（A000073） | 直線上のどこでも（A000124） |
|---|---|---|
| 4 | 13 | 11 |
| 6 | 44 | 22 |
| 8 | 149 | 37 |
| 10 | 504 | 56 |
| 12 | 1,705 | 79 |
正しい読みでは「111 を含まない長さ L のビット列」なのでトリボナッチ数 A000073。誤読では「1 行に黒は高々 2 つ」なので 1 + L + L(L−1)/2、A000124（怠け仕出し屋の数列）。指数が 2 次に落ちる。
そして出荷盤は 72 枚中 72 枚が解無しになる。易しくなるのではなく消える。
ついでに、全マスに丸がある正方格子で「3 連続なし」の黒集合を数えると A181218 になる: 2, 16, 230, 10732, 1495392, … リポジトリでは行ペアを状態にした転送行列で計算し、4×4 までは総当たりと突き合わせている。8×8 で止めているのは、9×9 の項が 2^53 を超えて double が黙って丸めるから。
ラダー
同じ「領域ごとの候補集合」の上で、4 段の伝播を用意した。
-
region— 各領域に黒 1 つ。丸を 1 つしか持たない領域が確定するだけ -
triple— 生きたトリプルへの hyper-arc 整合性を不動点まで。証明書の規則を伝播として読んだもの: 3 連のうち 2 つが確定したら 3 つ目は消える -
probe— シングルトン整合性。1 つ仮定して伝播し、それだけで矛盾したら落とす -
search— 完全ソルバー。成分ごとに探索
段の切れ目は「盤にどれだけ選択肢があるか」でほぼ決まる。8×8 で生成した盤を白い丸の数で分けると:
| 白い丸 | 盤 | triple | probe |
|---|---|---|---|
| 1–4 | 93 | 92 | 1 |
| 5–8 | 82 | 76 | 6 |
| 9–12 | 100 | 78 | 22 |
| 13+ | 110 | 60 | 50 |
triple は証明書に対する単位伝播なので、出発点が要る。2 つの黒がすでに確定している証明書だ。これが尽きて、残った丸が互いを証明し合うループになると止まる。出荷 72 盤のうち 52 枚がそうなる。ただしそこでも triple は先に領域の 72% を確定させていて、probe に残るのは中央値 13 領域の結び目だけだった。バンクに search を要する盤は 1 枚も無い。
生成器は難易度を設計しない
答えを先に描く。領域を引き、各領域に黒を 1 つ、3 連続にならないように置く。ここまでで盤は一意だ（全領域が丸 1 つなので当たり前）。
そこから残りの全マスに丸を提案する。採否の基準は 1 つだけ:
board.circle[cell] = true;
if (countSolutions(board, 2).count === 1) keep();
else board.circle[cell] = false;
配置ルールも難易度も一切見ていない。それでも上の補題が「何が生き残れるか」を完全に予言する。証明書を持たない丸は 1 つも採用されなかった——これは生成器を回すたびに assert している。
ダイヤルは白い丸の数だ。スケルトンに証明書付きの丸を k 個ランダムに放り込み、一意性チェックを一切かけずに数える（証明書は必要条件であって十分条件ではない、その差の測定）:
| 白い丸 | 引いた枚数 | 一意 | 率 |
|---|---|---|---|
| 0 | 212 | 212 | 100.0% |
| 4 | 216 | 201 | 93.1% |
| 8 | 213 | 143 | 67.1% |
| 12 | 207 | 79 | 38.2% |
| 14 | 202 | 38 | 18.8% |
12×12 も同じ形の曲線で、0 個 100% から 32 個 13.7% まで。そして 3,276 枚のダイヤル盤で、解が 0 になった盤は 1 枚も無い。丸を足しても答えは無効にならず、仲間が増えるだけだからだ。
なお、ランダムに引いた盤はほぼ全滅する。ランダム領域＋ランダムな丸を 3,600 枚引いて、2,248 枚が解無し、一意はわずか 27 枚、そのうち丸が領域より多い（＝選択肢がある）ものは 23 枚しかない。
期待して外れたこと
証明書は「隣接する 2 つの黒」を要求する。だから答えは、3 つ並ばないぎりぎりまで黒が寄り添った、見て分かる密集構造になるはずだ——と思っていた。
ならなかった。8 近傍に黒を持つ黒の割合は:
- 出荷 8×8 の答え: 86%
- 同じ領域分割で黒をランダムに選んだ場合: 87.8%
12×12 でも 91% 対 91.4%。差が無い。領域の平均サイズが 3 マス程度だと、隣接する黒のペアは幾何が勝手に大量供給していて、生成器はそれを要求する必要がない。負けた仮説だが、測らずに書かなくてよかった。
2 つのエンジン
死んだトリプルのスクリーンと成分分解が、このリポジトリで一番荷重のかかっている主張だ。だからどちらも持たないエンジンと突き合わせている。領域ごとに丸を総当たりで選び、完成した盤を全幾何トリプルに対して 3 マスずつ検査するだけの後戻り探索だ。総当たりが終わるサイズの盤では、2 つのエンジンは解の集合が一致する（数だけではなく）。誤読 2 種の下でも同じ。成分分解はさらに 3 つ目の方法でも検査していて、成分ごとに手で数えて掛け算した値と全体の解数を比べている。
まとめ
- 3 つの丸のうち 2 つが同じ領域にあるトリプルは発火し得ない。出荷盤の幾何の 34.8% がこれ
- 黒を同じ領域内で 1 つずらすと、不正になる理由は「2 黒の 3 連」しか無い。だから白い丸には全部証明書が要る（2,113/2,113 で確認）
- 2 黒の 3 連は白い丸を 1 つしか含まないので、
丸 − 領域 ≤ 証明する 3 連 ≤ 生きたトリプル。盤が持てる選択の総量を幾何が上から押さえている - 生きたトリプルで繋がらない領域は独立成分になり、丸の数がそのまま解数に掛かる（200/200 で一致）
- 対角線を落とすと 72/72 が一意でなくなり、「直線上のどこでも」と読むと 72/72 が解無しになる。誤読は 2 方向あって、どちらもパズルを消す
ソルバー内蔵パズル第 59 弾。テスト 32 本、ランタイム依存ゼロ。