ゴキゲンななめを解く — ループ禁止ルールは数え上げの定理で、盤面は必ず 2n+1 本の木の森になる

ゴキゲンななめ（Slant）を、4 つのルールセット内蔵でブラウザに実装した。n×n の各マスに斜線を 1 本ずつ引く——/ か \。格子点の丸数字は、その点に先端が触れる斜線の本数。そして斜線がループを閉じてはならない。ソルバー内蔵パズル第 34 弾。

デモ: https://sen.ltd/portfolio/gokigen-naname/
リポジトリ: https://github.com/sen-ltd/gokigen-naname

このパズルを選んだのは、「ループ禁止」というトポロジカルに見えるルールが、実は算数だからだ。

ループ禁止は V − E である

各マスは (n+1)×(n+1) の格子点グラフにちょうど 1 本の辺を追加する。\ はマスの左上と右下の格子点を結び、/ は残りの 2 点を結ぶ。どちらを選んでも辺は 1 本。つまり完成盤面は、(n+1)² 頂点の上の n² 本の辺だ。

サイクルのないグラフの連結成分数は V − E で決まる。(n+1)² − n² = 2n+1。**合法な Slant の盤面は、手掛かりが何であろうと、必ずちょうど 2n+1 本の木からなる全域森になる。**成分数は自由度ではない。生成した 1,500 盤で数えて、例外ゼロ。

デモの盤面を解き切ると「Solved! A forest with exactly 2n+1 trees, as it must be.」と出るのはこのためだ。

export function edgeOf(k: number, orient: number, n: number): [number, number] {
  const [tl, tr, bl, br] = cornersOf(k, n);
  return orient === BACK ? [tl, br] : [tr, bl];
}

パズル全体はこの 1 行の言い換えで、ソルバーの全ルールはこの辺選択についての文になる。

ルールは 4 段

ソルバーは各マスの候補 cand[k] ∈ {/, \, 両方} を削っていく。

レベル	ルール
count	手掛かり 1 個ずつ。置かれた斜線が数字に達したら残りは全部そっぽを向く。未確定マスがちょうど不足分なら全部が触りに行く
cycle	格子点上の union-find。すでに連結な 2 点を結ぶ向きは死ぬ
duet	直交隣接する手掛かり 2 個をひとつの制約として読む。共有する ≤6 マスの結合割当 ≤64 通りを列挙し、全生存者が一致するマスだけ確定する
probe	斜線 1 本を仮定し、下位ルールを fixpoint まで回して、それだけで矛盾したら棄却

duet は Slant の定石を全部飲み込む。「隣接する 3 と 3 の外側 4 マスは両方に向く」「隣接する 1 と 1 の両脇は同じ向き」といった教科書テクニックは、列挙の特殊ケースとして勝手に出てくる。

ただし後者には罠がある。隣り合う 1 と 1 の両脇 2 マスについて教科書が言うのは「A と B は同じ向き」——出力がマスの値ではなく、2 マスの相等だ。unary な propagator はこれを書き込めない。列挙しても「全生存者が一致するマス」は存在しない（A=B=/ と A=B=\ の両方が生き残る）。定石をそのまま propagator に翻訳しようとすると、値ではなく関係を出力する規則が混ざっていることに気づく。duet は unary 部分だけを絞り出し、残った相等制約は片側が決まった瞬間に count が拾う。それでも届かない盤面が probe の仕事になる。

実際、隣接 3-3 をテストすると外側 4 マスは確定し、間の 2 マスは XOR 制約のまま開いている:

// 外側 4 マスは duet が確定する
expect(c2[cellId(1, 1, 5)]).toBe(BACK);
// 間の 2 マスは「どちらか片方が u に触る」という関係だけが残る
expect(c2[cellId(1, 2, 5)]).toBe(BOTH);

実測 — incremental と ablation は違う話をする

3 サイズ × 300 盤。生成流は一意性でも難易度でもフィルタしない（測ろうとしている性質でサンプルを歪めないため）。手掛かり密度 0.75、fixpoint だけで解き切れた率:

盤面	count	+cycle	+duet	+probe	生成流の一意解率
5×5	78.7%	82.0%	82.7%	83.3%	83.3%
7×7	56.3%	62.7%	66.7%	68.3%	68.3%
10×10	31.7%	42.7%	52.7%	55.0%	55.0%

同じルールを ablation（全ラダーから 1 個だけ抜く）で測ると:

盤面	full	−count	−cycle	−duet
5×5	83.3%	71.7%	79.3%	83.3%
7×7	68.3%	55.7%	60.3%	68.3%
10×10	55.0%	39.0%	40.7%	55.0%

incremental で見ると duet は 10×10 で +10.0pt の立役者に見える。ablation で見ると抜いても 1 盤も落ちない——後ろに控えた probe がこぼれ球を全部拾うからだ。逆に cycle は抜くと 14.3pt 落ちる。probe は cycle の代わりにはなれない。前回・前々回と同じ「控え選手への相対値」問題がここでも出た。冗長と無用は違う: duet の価値は、cycle だけでは推測なしに解けない盤面を推測なしに終わらせることで、それはまさに難易度グレードが測りたいものだ。だから出荷バンクの 4 グレードのうちのひとつは duet で、全 (サイズ, グレード) バケットが埋まっている。

もうひとつ、−count の 39.0% が面白い。基本ルールを丸ごと消しても 4 割解ける。duet が手掛かりペアの数え上げを再発明しているからで、密度 0.75 では大半の手掛かりに直交隣接の相棒がいる。孤立した手掛かりだけが完全に見えなくなる。

probe の解決率 = 一意解率、今回も

上の表で probe 列と一意解率の列は全サイズで完全一致している。健全な fixpoint は解が 2 つある盤面を確定できないので「ルールで解ける率」は一意率が上限——そしてラダーはその上限に届いている。密度スイープの全 11 点でも一致は崩れなかった。

Slant は手掛かりに飢えている

その密度スイープ。10×10、各点 150 盤:

密度	一意	probe	count
0.55	1.3%	1.3%	0.0%
0.65	11.3%	11.3%	2.0%
0.75	50.7%	50.7%	28.0%
0.85	90.7%	90.7%	85.3%
0.95	100%	100%	100%

閾値が鋭い。0.55 では実質何も決まらず、0.95 では全部決まる。1 個の手掛かりは「最大 4 マスに対する 0〜4 の数字」という弱い制約で、しかも盤面の自由度は n² ビットもある。ナンプレ系のパズルに慣れた目には異様に見える「格子点の過半数に数字が付いている」出題は、情報理論的に必要なのだ。ちなみに生成流の格子点次数の分布は 0/1/2/3/4 = 8.6/38.5/34.8/15.1/2.9%（10×10）——「4」の手掛かりが珍しいのは作為ではなく統計である。

一意性の証明に要する探索回数も測った。10×10 の 100 盤、解数 2 を確認するまでの分岐回数の中央値: count 1 回、cycle 1 回、duet 0 回、probe 0 回。上位 2 レベルにとって、この密度の一意性判定は探索ですらない。

検証

すべての盤面を 2 つの独立な数え上げ器が採点する。ひとつは 4 レベル各々で伝播しながら探索する数え上げ。もうひとつはルールのコードを一切共有しない総当たり——行優先でマスを埋め、使うのは次数の算術と rollback 付き union-find だけ、葉では独立バリデータが最終判定する。全レベルの解数が全盤面で一致しなければテストは落ちる（健全なルールセットは解の個数を変えられない）。

厳密なアンカーもひとつ: 手掛かりなしの 2×2 盤面の充填は 15 通り。2⁴ = 16 通りから、中央格子点を囲むダイヤ 1 個だけがループで死ぬ。5 つの数え上げ器全部がこの 15 に一致する。全 27 テスト。

遊び方

デモの Hint ボタンは選択中のレベルで最初に確定するマスを 1 個ずつ埋める。ルールセレクタがそのまま難易度で、バンクは「そのレベルで初めて推測なしに解ける」盤面だけを出す。probe グレードの 10×10 は、count/cycle/duet を全部使っても最後は仮定が要る盤面だ。

次回もソルバー内蔵パズルの予定。

---

SEN 合同会社 — ソフトウェア開発の実験と実装を公開しています。
他のポートフォリオ: https://sen.ltd/portfolio/