0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

クロプキを解く — 全制約が線の内側に住むパズル。ラダーの天井は「線を厳密に解く」で、情報の主役はドットの沈黙

0
Posted at

クロプキ (Kropki) を、4 つのルールセット内蔵でブラウザに実装した。n×n の盤面に 1〜n をラテン方陣(各行・各列に各数字ちょうど 1 回)として埋める。隣接マスの間には白ドット=連続する 2 数黒ドット=一方が他方の 2 倍無印=どちらでもない、が全辺で開示されている。ソルバー内蔵パズル第 42 弾。

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

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 段を完全に包含する。制約が全部線内なのだから、ラダーは dotsingleline の入れ子であり、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 合同会社では、こうした「小さく作って測って出す」を積み上げています。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?