クロプキ (Kropki) を、4 つのルールセット内蔵でブラウザに実装した。n×n の盤面に 1〜n をラテン方陣(各行・各列に各数字ちょうど 1 回)として埋める。隣接マスの間には白ドット=連続する 2 数、黒ドット=一方が他方の 2 倍、無印=どちらでもない、が全辺で開示されている。ソルバー内蔵パズル第 42 弾。
デモ: https://sen.ltd/portfolio/kropki/
リポジトリ: https://github.com/sen-ltd/kropki
このパズルを選んだ理由は 2 つ。
全制約が線の内側に住む
ラテン則は行または列を縛る。ドットは直交隣接ペアを縛る——そして直交隣接ペアも必ず同じ行か同じ列に属する。つまりクロプキには線をまたぐ制約が 1 本も存在しない。この構造がソルバーの形を決める。伝播ルールの天井は「線 1 本を厳密に解く」こと、すなわち各行・各列について「この線の、候補とドットに整合する完全な順列に延長できる数字はどれか」を正確に答えることだ。実装は前向き・後向きの bitmask DP(状態 = 使用済み数字集合 × 末尾の数字)で、prefix と suffix を縫い合わせて各マスの生存候補を出す。
ラダーは 4 段:
| レベル | ルール |
|---|---|
dot |
naked single(ラテン消去)+ 各辺のアーク整合(無印も負制約として伝播) |
single |
+ hidden single: 線内で行き場が 1 つの数字はそこに入る |
line |
+ 線の厳密解: 双方向 bitmask DP で線内の全制約を一括で問う |
probe |
+ 1 マスに数字を仮置きし、line を fixpoint まで回して矛盾したら棄却 |
line は自分の線の中では下位 2 段を完全に包含する。制約が全部線内なのだから、ラダーは dot ⊂ single ⊂ line の入れ子であり、ablation の帰結は定理として予言できる。実測(200 盤/サイズ、probe ラダーから 1 段抜き):
| 盤面 | full | −dot | −single | −line |
|---|---|---|---|---|
| 5×5 | 99.0% | 99.0% | 99.0% | 99.0% |
| 6×6 | 99.5% | 99.5% | 99.5% | 99.5% |
| 7×7 | 96.0% | 96.0% | 96.0% | 96.0% |
完全フラット。−line さえ無傷なのは、probe が分岐の中で dot+single を回して取り分を回収するからだ。一方、増分ラダー(各段を足していく、全開示・生ストリーム)は各段が明確に稼ぐ:
| 盤面 | dot | +single | +line | +probe | 一意率 |
|---|---|---|---|---|---|
| 5×5 | 95.0% | 99.3% | 99.5% | 99.5% | 99.5% |
| 7×7 | 64.3% | 88.0% | 99.0% | 99.0% | 99.0% |
| 8×8 | 30.5% | 56.5% | 97.5% | 97.5% | 97.5% |
| 9×9 | 6.7% | 16.7% | 82.0% | 86.0% | 86.0% |
「ablation だけ読めば全ルール冗長、増分だけ読めば全ルール必須」——連作の教訓(両方測れ)が、タイルペイント (#324) に続いて片側定理・片側測定の形で再現した。そして 9×9 で line (82.0%) と probe (86.0%) の間に残る 4 ポイントが、線内推論では原理的に届かない、純粋な行×列結合の実測値だ。
probe ⇔ 一意が破れなかった
この連作には「probe fixpoint が完答する ⇔ 解が一意」という経験則があり、クロット (#320)・タイルペイント (#324) と、純算術パズルでは多セル組み替えに曖昧さが棲んで反例が出る、が直近の法則だった。クロプキも純算術だ。ところが今回、全 1,750 盤で probe 完答と一意が完全一致した(probe ⇒ 一意は定理、逆は測定——gap 0)。
理由は曖昧さの形にある。ラテン方陣 2 つの最小差分は intercalate——a/b と b/a が対角に並ぶ 2×2 部分長方形——で、その入れ替えは 4 マスの組み替えだ。1 マス probe はこれを直接見られないはずなのに、なぜ破れないのか。全開示のクロプキでは、intercalate が「沈黙」する(入れ替えても見えている全ドットが不変)こと自体が稀で、曖昧さが発生した盤では probe もちゃんと詰まる方向にしか外れない。反例の住処だった「probe には見えないが一意」な盤が、このパズルの全開示レジームには実測上存在しなかった。法則は破れることも破れないことも、測るまで分からない。
曖昧さには今回も顔がある。第 2 解の最小証明書は沈黙する intercalateで、探索ゼロで答えから直読できる: 4 マスの入れ替えが行・列を保ち(ラテン則は自動で無事)、外側の隣接マスに対して labelOf(a,x) = labelOf(b,x) が全部成立すれば、どのドットも動かない。実測では 9×9 の非一意 21 盤中 16 盤(76%)がこの 4 マス証明書 1 枚で説明でき、辺を半分隠した 6×6 では 61 盤中 39 盤(64%)。一意な盤で証明書が誤検出されたことは 0 回——「沈黙 intercalate ⇒ 第 2 解」は定理で、その対偶が空振りしないことの機械検査になっている。
情報の主役はドットの沈黙
古典クロプキは「ドットは全部描いてある」ルールなので、無印の辺は負制約(連続でも 2 倍でもない)だ。この沈黙がどれだけ働いているかを、無印辺だけを「不明」に置き換えた盤(ドットは全部残す)と比較して測った:
| 盤面 | 辺の構成 白/黒/無印 | 一意(全情報) | 一意(ドットのみ) |
|---|---|---|---|
| 4×4 | 33.7% / 33.0% / 33.3% | 100.0% | 82.5% |
| 6×6 | 26.2% / 20.3% / 53.5% | 99.5% | 74.5% |
| 7×7 | 23.8% / 14.8% / 61.4% | 96.0% | 52.7% |
| 8×8 | 22.1% / 14.4% / 63.5% | 96.0% | 47.0% |
n が大きいほど無印辺が支配的になり(8×8 で 63.5%)、その沈黙を捨てると一意率は 96% → 47% まで落ちる。盤面の情報の過半は、描いてあるドットではなく描いてないドットが運んでいる。ついでに色にも非対称がある: 1·2 のペアは「連続」と「2 倍」の両方を満たすので、このリポジトリでは黒を優先して確定的にラベルづけした。したがって白ドットは「連続」に加えて「{1,2} ではない」もささやく——白は見た目より強い。
負制約をルールごと消すのではなく、辺そのものをランダムに伏せるダイヤルも回した(6×6・200 盤):
| 伏せた辺の割合 | probe 完答 | 一意 | 非一意のうち証明書で説明 |
|---|---|---|---|
| 0 | 100.0% | 100.0% | — |
| 25% | 97.0% | 97.0% | 6/6 (100%) |
| 50% | 69.5% | 69.5% | 39/61 (64%) |
| 75% | 3.0% | 3.0% | 132/194 (68%) |
ここでも probe と一意の列は 1 盤も割れない。
生成はラテン方陣を引いてドットを読むだけ
クロプキの答えは任意のラテン方陣だ。生成器は行ごとのランダム化バックトラッキング(リスタート上限つき)で方陣を 1 つ引き、全辺のラベルを答えから読み取るだけ——パズルレベルの探索もリトライも要らない。弱いレベル向けの盤は given(初期開示数字)で完答可能性を買い、あとで最小化する方式にした。レベル別の「弱さの値段」(最小化後 given 数の中央値):
| 盤面 | dot | single | line | probe |
|---|---|---|---|---|
| 5×5 | 0 | 0 | 0 | 0 |
| 7×7 | 0 | 0 | 0 | 0 |
| 9×9 | 2 | 1 | 0 | 0 |
7×7 までは最弱ルールですら中央値 0——全情報クロプキは素で解けるパズルで、given が要るのは 9×9 の弱レベルだけ。出荷 bank は 52 盤(5/7/9 × 4 グレード、9×9 は probe 級 5 枚を含む)、全盤とも探索エンジンで一意性を再証明済み。
エンジンの信頼性は 2 系統の突き合わせで担保する: 候補集合を伝播させる探索と、候補もドット表も持たずに定義へ直接当てる行単位の生総当たり。600/600 の (盤面, エンジン) ペアで解数一致。テストは 24 本。
SEN 合同会社では、こうした「小さく作って測って出す」を積み上げています。
