天体ショーを解く — 鏡映写像ひとつがパズル全体で、推論は2回ずつ起きるか一度も起きないか

天体ショー（Spiral Galaxies）を、4 つのルールセット内蔵でブラウザに実装した。盤面を領域に分割する。各領域は 1 つのドットを含み、連結で、そのドットを中心に 180° 回転させると自分自身に重なる。ドットはマスの中心・辺の中点・格子点のどこにでも置ける。ソルバー内蔵パズル第 33 弾。

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

このパズルを選んだのは、パズル全体が写像 1 個に畳み込めるからだ。ルールは 3 つある——ドットを含む、連結、180° 対称。ところが実装してみると、3 つのうち 2 つ半は同じ 1 行の関数についての文になる。

倍座標とドットの 3 種類

ドットは「マスの中心」「辺の中点」「格子点」の 3 箇所に置ける。場合分けしたくなるが、座標を 2 倍にすると消える。マス (r, c) の中心を (2r+1, 2c+1) に置くと、ドットの位置 (cy, cx) は 1 ≤ cy, cx ≤ 2n−1 の整数で、両方奇数ならマス中心、片方偶数なら辺、両方偶数なら格子点だ。

そして、ドット g によるマス k の鏡像は:

export function mirrorOf(k: number, g: Galaxy, n: number): number {
  const r = g.cy - rowOf(k, n) - 1;
  const c = g.cx - colOf(k, n) - 1;
  return r >= 0 && r < n && c >= 0 && c < n ? r * n + c : -1;
}

2·cy − (2r+1) は cy の偶奇によらず必ず奇数なので、マスの鏡像は必ずちょうど 1 マスになる。ドットがどの種類でも、この 1 行が全部やる。場合分けはドットが物理的に触るマス（1・2・4 マス）を列挙するときにしか出てこない。

ルールは 4 段

ソルバーは「マス k を銀河 g がまだ所有しうるか」の候補配列 cand[g][k] を削っていく。

レベル	ルール
mirror	マスと双子は一蓮托生。双子側で g が死んでいたらこちらでも死ぬ。逆向きも: マスが g に確定したら双子も g に確定する
reach	領域は連結でドットを含む。生存候補の中を歩いてドットまで帰れないマスでは g は死ぬ
bridge	g に確定したマスはドットと繋がり続けねばならない。最後の回廊の上に乗ったマスは g に取られる
probe	1 ペアリングを仮定し、下位ルールを fixpoint まで回して、それだけで矛盾したら棄却

ペア定理 — 推論は 2 回ずつ起きる

この構成から不変量が 1 つ出る。各銀河の候補集合は、ラダーの全ルールを通じて、そのドットを中心とする 180° 回転対称に保たれる。

理由は各ルールが回転と可換だから。mirror の閉包は定義から対称。reach の BFS は、対称な集合の上を対称な種（ドットが触るマス）から歩くので、届く集合も対称。bridge で強制される回廊のマス u が橋なら、鏡像側の u′ も橋。probe の矛盾も鏡像側でそのまま再生される。つまり片側で候補を 1 つ削れば、同じラウンドで反対側の双子が落ちる。推論は 2 回ずつ起きるか、一度も起きないか。

これは実測できる。3 サイズ × 300 盤 × 4 レベル = 3600 回の fixpoint で、対称性が破れた候補集合はゼロだった。

系がひとつ付いてくる。辺・格子点ドットの領域は偶数マス、中心ドットの領域は奇数マス——というパリティルールは、書きたくなるが書く必要がない。対称閉包の下では未確定マスが双子で来るので、1 つの銀河への寄与は常に 0 か 2。パリティは検査する前から合っている。発火できないルールは、下位ルールの定理である。

踏んだ落とし穴 — 鏡映ルールを半分だけ書いた

最初に書いた mirror はこうだった: 「g が双子側で死んでいたら、こちら側でも殺す」。候補の死は転送している。だが対称性の定義はもっと強い——マスが g の領域に入るなら双子も入る。候補が 1 つに絞られた（= 所有が確定した）という情報は、死の転送だけでは双子に届かない。

// 所有の確定も双子に伝わる: k が g にピン留めされたら、g による k の鏡像から g 以外を消す
for (let k = 0; k < nc; k++) {
  const g = assignedAt(model, cand, k);
  if (g === -1) continue;
  const m = model.mirror[g * nc + k];
  for (let h = 0; h < model.galaxies.length; h++) {
    if (h !== g && cand[h * nc + m]) cand[h * nc + m] = 0;
  }
}

この半分を欠いたまま盤を難易度グレード（fixpoint だけで解ける最弱レベル）で分類すると、分布が {mirror, probe} に縮退した。7×7 の 16 盤が全部 probe。確定情報が伝播しないので、中間の reach と bridge が「最弱の決め手」になる機会を probe に全部吸われる。両方向を入れた途端、同じ生成器・同じシードで 7×7 は mirror 9 / reach 6 / bridge 1 に開いた。ルールセットの強さを測る前に、ルールが自分の定義を全部使っているかを疑うべきだった。

連結性の崖

300 盤 × 3 サイズの無フィルタの生成流（一意性でも難易度でも選別しない——測りたい性質で母集団を濾すと列が無意味になる）で、fixpoint 単独の解決率:

盤	mirror	+reach	+bridge	+probe	生成流の一意解率
5×5	94.3%	97.7%	98.0%	98.0%	98.0%
7×7	63.3%	93.3%	95.3%	95.3%	95.3%
10×10	2.7%	87.3%	92.3%	93.0%	93.0%

mirror は 5×5 の 94.3% から 10×10 の 2.7% まで崖から落ちる。鏡映は距離を保つ写像なので、盤が大きくなるほど「鏡像が盤外」という削り方が効かなくなり、しかも mirror はマスがドットまで歩いて帰れるかを一度も聞かない。それを聞く reach を足すと 10×10 が 87.3% まで戻る。連結性が金を払うルールだ。

ablation は今回も「控え選手への相対値」を測った

同じ盤で、4 ルール全部から 1 つだけ抜く:

盤	full	−mirror	−reach	−bridge	−probe
5×5	98.0%	5.3%	95.0%	98.0%	98.0%
7×7	95.3%	0.0%	74.0%	95.3%	95.3%
10×10	93.0%	0.0%	31.0%	92.7%	92.3%

bridge は増分（ladder の +bridge 列）では 10×10 で +5.0pt に見える。だが ablation では −0.3pt——外しても probe がこぼれ球をほぼ全部拾う。前作シャカシャカで見た「伝播器に固有の寄与などなく、あるのは特定の控え選手の顔ぶれに対する相対値だけ」が、別のパズル・別のルール構成でそのまま再演された。増分と ablation は両方出さないと、どちらか片方は必ず嘘をつく。

解決率の上限は一意率で、ラダーはそこに届いている

上の表でもう 1 つ。probe での解決率と生成流の一意解率が、3 サイズすべてで桁まで一致している（98.0 / 95.3 / 93.0%）。これは偶然ではない。健全な伝播は真の解を殺せないので、解が 2 つある盤を fixpoint が確定させることは原理的にない。「ルールで解ける率」は一意率を上限に持ち、このラダーはその上限にちょうど届いている。差分（解けなかった盤）はすべて複数解の盤で、そこではどんな健全なルールを足しても無駄だ。

そして無フィルタの生成流の 93〜98% がそもそも一意というのも、このパズルの個性だ。鏡映制約それ自体が強烈で、候補配列を持たない総当たり——行優先でマスを歩き、双子ペアを一手で割り当て、連結性は葉に着くまで一切見ない——ですら、5×5 の全解列挙が中央値 5 ノードで終わる。10×10 の一意性チェックは mirror だと中央値 142.5 回の推測が要るが、reach を入れると 0 回。ここでも連結性が effectively 探索を消す。

検証

• 解数の一致: 伝播つき探索（4 レベル全部）と、上記の総当たりが、ランダム小盤で全解数一致。健全なルールセットは解数を変えられないので、1 レベルでもズレたらそのルールは不健全
• 独立バリデータ: 総当たりの葉と全ソルバーの出口で、候補配列もルールも共有しないバリデータが flood fill で採点
• 健全性: 生成器の作った真の分割が、probe までの fixpoint を通しても 1 候補も削られないことをランダム盤で確認
• ペア定理: 全レベルの fixpoint 後に候補集合の対称性を検査（上記 3600 回ゼロ違反の縮小版）

全 27 テスト。

まとめ

• 倍座標にすると、ドット 3 種類の場合分けが鏡映写像 1 行に消える
• 候補集合はラダー全体で 180° 対称に保たれる（3600 fixpoint、違反ゼロ）。推論は 2 回ずつ起きるか、一度も起きない
• パリティルールは対称閉包の定理なので発火できない。書く必要のないルールがあると分かるのも定理の効用
• 鏡映ルールは「死の転送」と「確定の転送」の両方向。半分だけ書くと難易度グレードが縮退する
• mirror は 10×10 で 2.7% まで崖から落ち、連結性（reach）が 87.3% まで戻す
• bridge は増分 +5.0pt / ablation −0.3pt。増分と ablation は両方出す（前作の教訓の再演）
• 健全な fixpoint の解決率は一意率が上限。このラダーは 3 サイズ全部でその上限に届いた

---

SEN 合同会社では、こういう「小さく作って学びを言語化する」開発を積み重ねています。他の作品は sen.ltd/portfolio へ。