イン・ヤン（白丸黒丸）を、4 つのルールセット内蔵でブラウザに実装した。n×n の各マスを黒か白で塗る。ルールは 2 つだけ——各色は全体で 1 つの連結成分、そして単色の 2×2 は禁止。ソルバー内蔵パズル第 35 弾。
デモ: https://sen.ltd/portfolio/yin-yang/
リポジトリ: https://github.com/sen-ltd/yin-yang
このパズルを選んだのは、名前が定理だからだ。
名前が定理
黒マスと白マスを隔てる格子辺の集合——境界線——を、格子点の上の曲線として読む。すると 2 つのルールがそのまま曲線の性質に翻訳される:
- 単色の 2×2 は、曲線が通り損ねた内部格子点。ある内部格子点の周り 4 マスが同色 ⟺ その点に境界辺が 1 本もない。
- 市松の 2×2（対角に黒黒・白白）は、曲線が自分と交差する点。そしてこれは書かれていないのに禁止されている——対角の黒ペアと白ペアはそれぞれ連結路が要るが、正方形の対角どうしを結ぶ 2 本の互いに素な経路は平面格子では必ず交わる。連結性ルールの局所的な影だ。
- 境界線が 2 本以上あると、盤面は 3 つ以上の単色領域に切り分けられ、そのうち 2 つは同じ色なのに互いに届かない。
つまり合法な盤面の境界線は、全ての内部格子点をちょうど 1 回ずつ通る、自己交差しない 1 本の曲線。内部格子は (n−1)×(n−1) だから、これは内部格子グラフのハミルトン路（両端を盤の外周まで 1 辺ずつ伸ばしたもの）だ。稀に閉じてハミルトン閉路にもなる——そのとき片方の色は外周に触れない「内陸国」になる。
2×2 盤で確かめると: 内部格子点は 1 個、曲線はその点を通過するだけなので、4 本の接続辺から 2 本を選ぶ C(4,2) = 6 通り。塗り方が各 2 通りで 12 盤。全数列挙も 12。3×3 は 34 盤（うち内陸 2 盤——中央 1 マスだけの純粋な陰陽図）、4×4 は 96 盤。数え上げ器 6 本（素朴列挙・総当たり・伝播つき探索 4 レベル）が全部一致する。
生成した 1,500 盤でも: 境界線の連結成分は常に 1、自己交差 0、外周の色変化は常に 0 か 2 回。例外ゼロ。デモを解き切ると「Solved! The frontier between the colors is one unbroken curve, as it must be.」と出るのはこのためだ。
生成器は定理を逆走する
最初の生成器は素朴に書いた: 空盤からランダムなマスにランダムな色を置き、ルールを伝播して、死んだらバックトラック。6×6 は 3ms/盤。10×10 は 5.6 秒/盤。散らばった置き方が遠く離れた場所に矛盾を仕込み、それが深部でしか発覚しない——連結性の失敗は局所では見えない。
そこで定理を逆に使う。合法盤面 ⟺ 内部格子のハミルトン路 なのだから、盤面を塗る代わりに曲線を引けばいい:
- 蛇行（serpentine）ハミルトン路から始める
- backbite ムーブ（端点をランダムな隣へ繋ぎ替えて経路を反転する、格子上のランダムハミルトン路の標準手法）で 8m² 回混ぜる
- 両端点が内部格子の縁に来るまでさらに混ぜ、外周へ 1 辺ずつ伸ばす
- 曲線の両側に 2 色を flood fill する
バックトラックはゼロになり、10×10 が 0.6ms/盤。約 9,000 倍速い。伝播や探索の話をする前に、生成器がまず定理の恩恵を受けている。
ルールは 4 段
ソルバーは各マスの候補 cand[k] ∈ {黒, 白, 両方} を削っていく。
| レベル | ルール |
|---|---|
window |
2×2 の 16 通りのうち合法な 12 通りを列挙し、全生存者が一致するマスだけ確定。禁止 4 通りの内訳: 単色 2（明文ルール）+ 市松 2（連結性の影） |
border |
外周のマスはサイクルをなす。完成盤で各色は外周の高々 1 つの弧——黒白黒白と循環的に並んだら 4 本の連結路が交差するしかない。確定済み外周マスの色変化が 2 を超える置き方は死ぬ |
bridge |
連結性の局所化。各色の確定マスは（同色 ∪ 未確定）のグラフで互いに届き続けなければならない。ある色から封鎖された未確定マスはその色になれず（pocket）、確定マス同士を繋ぐ唯一の関節点は必ずその色になる（bridge）。Tarjan の関節点探索で 1 パス O(V+E) |
probe |
マスに色を仮置きし、下位ルールを fixpoint まで回して、それだけで矛盾したら棄却 |
4 つのうちパズルの明文ルール由来なのは window の半分だけ。市松禁止も外周弧ルールも、高価な大域ルール（連結性）の安価な局所的影だ。独立バリデータはこのことを知らない——チェックするのは連結性と単色 2×2 という定義そのものだけで、影のルールは帰結として浮かび上がる。
実測 — incremental と ablation は今回も違う話をする
3 サイズ × 300 盤。生成流は一意性でも難易度でもフィルタしない（測ろうとしている性質でサンプルを歪めないため）。手掛かり密度 0.8、fixpoint だけで解き切れた率:
| 盤面 | window | +border | +bridge | +probe | 生成流の一意解率 |
|---|---|---|---|---|---|
| 6×6 | 2.3% | 16.7% | 57.3% | 57.3% | 57.3% |
| 8×8 | 0.0% | 2.7% | 39.3% | 39.3% | 39.3% |
| 10×10 | 0.0% | 0.0% | 16.7% | 17.0% | 17.0% |
同じルールを ablation（全ラダーから 1 個だけ抜く）で測ると:
| 盤面 | full | −window | −border | −bridge |
|---|---|---|---|---|
| 6×6 | 57.3% | 15.3% | 57.3% | 16.7% |
| 8×8 | 39.3% | 2.3% | 39.3% | 2.7% |
| 10×10 | 17.0% | 0.0% | 17.0% | 0.0% |
incremental で見ると border は 6×6 で +14.4pt の準主役に見える。ablation で見ると抜いても 1 盤も落ちない——全サイズで 0.0pt。window+bridge+probe が全部拾う。逆に window か bridge を抜くと 10×10 は 0.0% まで崩壊する。このシリーズで毎回出る「incremental と ablation の乖離」の、今回はもっとも極端な形だ。
それでも border は無用ではない。難易度グレードを 1 段定義する——バンクの border グレード盤（6×6 で中央値 11 手掛かり）は window グレード（20）と bridge グレード（8）のちょうど中間の手掛かり予算に座る。そして人間が実際に使うのはこのルールだ。冗長と無用は違う、を 3 回連続で確認したことになる。
一意性の証明に要する探索回数も測った（10×10、100 盤、解数 2 の確認まで）: 分岐回数の中央値は window 527 回、border 21 回、bridge 2 回、probe 2 回。連結性を伝播に入れた瞬間、一意性判定はほぼ探索ではなくなる。
probe の解決率 = 一意解率、今回も
上の表で probe 列と一意解率の列は全サイズで完全一致している。健全な fixpoint は解が 2 つある盤面を確定できないので一意率が上限——ラダーは今回も上限に張り付いた。
イン・ヤンは手掛かりに死ぬほど飢えている
10×10、各点 150 盤の密度スイープ:
| 密度 | 一意 | flip 上限 E[d^flips] | bridge で解ける | window で解ける |
|---|---|---|---|---|
| 0.50 | 0.0% | 80.0% | 0.0% | 0.0% |
| 0.70 | 2.7% | 88.5% | 2.7% | 0.0% |
| 0.80 | 16.7% | 91.1% | 16.7% | 0.0% |
| 0.90 | 60.7% | 95.1% | 60.7% | 1.3% |
| 0.95 | 88.7% | 97.5% | 88.7% | 8.7% |
| 1.00 | 100.0% | 100.0% | 100.0% | 100.0% |
**盤面の 9 割をランダムに見せられても、4 割の盤面はまだ答えが 2 つ以上ある。**Slant の閾値（0.75 で 50%）よりはるかに酷い。
なぜかを測るために flippable セルを数えた: そのマス 1 個の色を反転しても盤面全体が合法のままであるマス。flippable なマスが 1 個でも手掛かりから漏れれば、その瞬間に第 2 の解が無料で手に入る。だから P(一意) ≤ E[密度^flips]。ところがランダム盤面の flippable は平均 0.4 個（10×10）しかなく、この上限は高い——そして実測はどの密度でも上限よりはるかに下にいる。つまりイン・ヤンの曖昧さは 1 マスの反転ではなく、曲線の複数マスにわたる引き直しから来ている。境界線が手掛かりのない領域を通るとき、そこでの経路の取り方は何通りもあり、1 マスの手掛かりはそのうちの 1 本しか殺せない。
対照的に、出荷バンクの盤面は敵対的に間引いて作る（全マス開示から始めて、目標レベルが推測なしに解ける限り 1 個ずつ消す）。10×10 の probe グレードは中央値 24 手掛かりで一意——ランダム開示なら 90 個見せてもまだ 4 割失敗する確実性を、24 個で買っている。手掛かりは曲線を釘付けにする場所にあるときだけ価値を持つ。
内陸国のパリティ
境界線が閉路になる盤面——片方の色が外周に一切触れない「純粋な陰陽図」——は存在するが、稀少で、そしてパリティを持つ。全数調査で: 3×3 にちょうど 2 盤（中央 1 マス）、4×4 と 6×6 には存在しない（内部部分集合の全列挙 2^16 まで含めて 0）。5×5 と 7×7 には明示的な構成がある（テストに入っている）。偶数盤では四隅の 2×2 窓が内部の黒を四隅の内側に強制し、それが黒の 2×2 を作ってしまう。ランダム生成 1,500 盤では閉曲線は 0 回——測度としてもほぼゼロだ。
検証
すべての主張を 2 つの独立な経路で数える。ひとつは 4 レベル各々で伝播しながら探索する数え上げ。もうひとつはルールのコードを一切共有しない総当たり——行優先でマスを埋め、枝刈りは定義そのものの 2 つ（完成した 2×2 の単色チェックと、確定マスの相互到達可能性）だけ、葉では独立バリデータが最終判定する。総当たりが届く全盤面で全レベルの解数が一致しなければテストは落ちる: 360/360 一致。
厳密なアンカー: 手掛かりなしの 2×2 / 3×3 / 4×4 は 12 / 34 / 96 盤。2×2 の 12 は C(4,2) × 2 色という曲線の言葉の答え合わせでもある。境界線定理は生成器の出力だけでなく（それは循環論法になる）、4×4 までの全合法盤面で全数検証した。全 33 テスト。
遊び方
デモの Hint ボタンは選択中のレベルで最初に確定するマスを 1 個ずつ埋める。ルールセレクタがそのまま難易度で、バンクは「そのレベルで初めて推測なしに解ける」盤面だけを出す。盤面には黒白の境界線が紫でライブ描画される——解に近づくにつれ、それが 1 本の曲線に繋がっていくのが見える。
次回もソルバー内蔵パズルの予定。
SEN 合同会社 — ソフトウェア開発の実験と実装を公開しています。
他のポートフォリオ: https://sen.ltd/portfolio/