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?

クロットを解く — 大域ルールが1つもないパズルで、「probe解決率=一意解率」の法則が連作で初めて破れた

0
Posted at

クロットを、4 つのルールセット内蔵でブラウザに実装した。n×n の盤面のいくつかのマスに丸数字が置かれ、丸のマスは決して塗られない。残りのマスを自由に塗り、各丸数字がその丸に辺で接する黒ブロック(塗りマスの連結成分)のサイズ合計に一致するようにする。ルールはこれで全部だ。ソルバー内蔵パズル第 37 弾。

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

Kurotto

このパズルを選んだのは、大域ルールが 1 つもないからだ。

合法盤面は……全部

数字を全部剥がして、完成盤がどんな形をしていられるかを考える。答え: どんな形でもいい。連結性ルールなし、2×2 禁止なし、外周ルールなし。2×2 盤の 16 通りの塗り方はすべて合法、3×3 の 512 通りもすべて合法(全数検証済み)。合法盤面の空間は 2^(n²) の超立方体そのものだ。

この連作はずっと「合法盤面 ⟺ サンプル可能な対象」の全単射を探してきた。イン・ヤンでは境界の稜線パス、ケイブでは格子の単純閉路。クロットはその探索の縮退した終点で、全単射は恒等写像、一様サンプリングは n² 回のコイン投げだ。生成器に定理は 1 つも要らない。

代わりに、他のパズルが連結性定理から只で得ていたものすべてを、クロットは算術だけで買うことになる。そして盤面に残る唯一の大域的な力は「答えは一意であれ」という要求そのものだ。

ルールは 4 段 — ただし今回は「4 つの定理」ではない

各丸の手掛かりは 2 本のフラッド フィルで挟める。 = 丸に既に接続している確定黒の領域 D。天井 = 白でないマスを通って丸から届き得る全域(潜在領域 P)。床は上がるだけ、天井は下がるだけ。

レベル ルール
sum 床と天井の算術: 数字が天井に触れたら P 全体が黒に、床に触れたらフロンティア(丸や D に隣接する自由マス)が白に確定(0 の丸は「床が空の床タッチ」の特殊例)
door 唯一の入口: 数字が床より上の丸は成長が必要で、あらゆる成長はフロンティアのマスを 1 つ塗る。フロンティアが 1 マスなら、そこは黒
echo 1 マスに色を仮置きし、全丸の床/天井算術を再実行。どこかの数字が区間から落ちたら仮置きは棄却
probe 1 マスに色を仮置きし、下位ルール全体を fixpoint まで回して矛盾したら棄却

過去のラダーと違って、この 4 段は 4 つの異なる定理ではない。同じ 1 つの定理(区間算術)を、より強くつつくだけだ: 直接読む → フロンティアで読む → 仮定の下で読む → 伝播付きの仮定の下で読む。この構造は ablation に露骨に現れる(後述)。

実測 — 「probe = 一意率」が初めて破れた

300 盤/サイズの生の生成ストリーム(白マスの 80% に丸を開示、一意性でも難易度でも無選別)で、推測なしの fixpoint だけで完成する率:

盤面 sum +door +echo +probe ストリーム中の一意解率
6×6 21.7% 48.7% 56.3% 62.0% 63.3%
8×8 10.7% 33.0% 43.0% 52.0% 52.7%
10×10 2.0% 21.7% 33.0% 42.0% 42.3%

この連作では毎回、probe 列が一意解率と完全一致してきた。健全な fixpoint は複数解が食い違うマスを確定できないから一意解率は理論上の天井で、イン・ヤンもケイブも、ラダーはその天井にぴったり張り付いた。

クロットで初めて破れた。 6×6 で一意な 190 盤のうち 4 盤、8×8 で 158 中 2 盤、10×10 で 127 中 1 盤が、一意なのに probe で完成しない。捏造や測定ミスでないことは独立実装で裏取りした: ラダーとコードを共有しない総当たり(定義の床/天井だけで枝刈り、葉は独立バリデータ採点)にギャップ盤面を食わせると、確かに解数 1(探索 906〜3,078 ノード)。一意だが、単一マスの仮置きの連鎖では届かない盤面が実在する。

なぜクロットで破れるのか。ブロックの算術は2 つの再配置可能性を重ね合わせのまま保持できるからだ。どのマスを単独で仮置きしても両方の色が生き残る——死ぬのは2 つの仮定の組だけ。1 セル probe の見える世界の外に、一意性の証明が住んでいる。

ablation — 何を抜いても、ほぼ何も変わらない

全ラダーから 1 ルールだけ抜く:

盤面 full −sum −door −echo
6×6 62.0% 61.7% 62.0% 61.7%
8×8 52.0% 52.0% 52.0% 50.7%
10×10 42.0% 42.0% 42.0% 39.0%

ケイブでは −count で全サイズ 0.0% に崩壊した——数字を読む唯一のルールだったからだ。クロットには「数字を読む唯一のルール」が存在しない。4 段すべてが同じ床/天井算術を読んでいるので、probe より下のどの段を抜いても、残りが同じ演繹をほぼ再構成する。redundant-but-not-useless の連作記録はこれで 5 例目だが、今回は 1 ルールではなくラダーの下 3 段まるごとが互いの影だ。それでも各段は bank の難易度グレードを 1 段ずつ定義するし、人間が実際にやる推論の順序でもある。

曖昧さの住処 — オラクルが 3 つの証明書を必要とした

丸が語れるのは自分の潜在領域の中だけだ。どの丸の領域にも入らない自由マスは、1 手も推論する前から無料の第 2 解になる(塗っても塗らなくてもどの丸も気づかない)。だから一意性はまず全被覆を要求する。

被覆されていても、暗殺者は 2 種類残る。silent flip: 反転してもどの丸の合計も変わらない 1 マス。そして今回新顔の silent pair flip: 2 マスの同時反転がブロックを組み替えるのに、どの丸も気づかないペアだ。一意性の測定オラクルはこの 3 つの証明書(被覆・単独 flip・ペア flip)を描画解から直接読み、生き残った準一意盤面だけを数え上げ探索に回す。ペア flip 検査を入れる前は、素朴な解数探索が 1 盤で数十秒〜数分停まっていた——測定器自身がパズルの曖昧さの構造を学ぶ必要があった。探索の guess 上限超過は全セクション通じて 0 回。

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

開示率 一意 no-silent-flip 天井 echo 解決 sum 解決
0.30 0.0% 4.7% 0.0% 0.0%
0.42 0.0% 18.0% 0.0% 0.0%
0.54 2.0% 49.3% 0.0% 0.0%
0.66 11.3% 79.3% 5.3% 0.0%
0.78 36.0% 90.0% 28.0% 0.7%
0.90 67.3% 100.0% 60.7% 20.0%

正直な驚きが 2 つあった。まず被覆天井は一度も効かなかった——開示率 0.30 でも 150 盤全部が全被覆だった(空盤面のフラッドはほぼ全域に届く)。「どの丸にも見えないマス」という暗殺者は、乱数ストリームが作るよりずっと極端な配置でしか現れない。そして、ケイブの一意率が flip 天井に張り付いて登ったのと違い、クロットの一意率は天井のはるか下を這う: 開示率 0.54 で単独 flip 天井は 49.3% を許すのに、実測は 2.0%。クロットの曖昧さは多セルのブロック組み替えが支配する——probe=一意率の法則を破ったのと同じ構造であり、オラクルにペア flip 証明書が必要だった理由でもある。連作の座標系で言えば、クロットはイン・ヤン側の飢え方をさらに極端にした位置にいる。

一意性証明に要する探索

3 つの証明書をすべて通過した準一意盤面(各サイズ 100 盤)だけを対象に、解数確定までの分岐回数:

盤面 ルール 中央値 平均
6×6 sum 4 29.7
6×6 door 0 8.3
6×6 echo 0 3.1
6×6 probe 0 0.5
10×10 echo 0 2.3
10×10 probe 0 0.0

echo が伝播に入った時点で一意性証明はほぼ探索でなくなる(10×10 で中央値 0、平均 2.3)。弱いレベルの探索は自由マス数とともに 6×6 の時点で既に爆発を始めるため、大きいストリームには出さない。guess 上限超過は全セクション 0 回。

bank

出荷 bank は全白開示から敵対的に間引き、「そのレベルで初めて推測なしに解ける」盤面だけを収録する。全グレード×全サイズが 5 盤ずつ埋まった——ラダーの段差が難易度として機能している証拠だ。10×10 は中央値 27〜35 個の丸で一意に釘付けになる。乱数開示でコイントス程度の確率(開示率 0.84 で一意 49.3%)を得るには白マスの 84%、約 48 個の丸が要るから、敵対的間引きは予算をほぼ半分にする。

検証

  • 解数の一致: ルールとコードを共有しない総当たり vs 4 レベル各々の伝播探索。総当たりが届く全盤面で 520/520 一致。
  • 全数アンカー: 丸なし 2×2 の 16 通り、3×3 の 512 通りが全て合法——「隠れたルールは本当にない」。角の丸 1 つの 2×2 は 8 通りの完成形が合計値 0/1/2/3 に 2/2/3/1 で分かれることを手で数え、総当たりが再現。
  • ギャップの裏取り: probe が停まる一意盤面は tools/gapcheck.mts が総当たりで解数 1 を再確認。
  • 全 26 テスト。

遊び方

デモの Hint ボタンは選択中のレベルで最初に確定するマスを 1 個ずつ埋める。ルールセレクタがそのまま難易度。2 マス以上の黒ブロックには現在のサイズが隅に表示される——クロットのプレイヤーが頭の中で数え続けるあの数字だ。丸は充足して封止されると緑に、両立不能になると赤になる。

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


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

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?