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 本を 3 段階の強さで読む。そして 1 マス probe には見えない曖昧さ

0
Posted at

タイルペイント (Tilepaint) を、4 つのルールセット内蔵でブラウザに実装した。n×n の盤面がタイルに分割されている。塗るのはマスではなくタイル丸ごと。数字の付いた行・列は、塗られたマスをちょうどその数だけ含まなければならない。数字のない行・列は自由。ソルバー内蔵パズル第 41 弾。

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

Tilepaint

このパズルを選んだ理由は 2 つ。

変数はマスではなくタイル

このソルバーに「マス」という決定は存在しない。タイル 1 枚につきブール変数 1 個。マスはタイルの射影にすぎない。すると数字付きの各線(行・列)は、その線を横切るタイルのスライス(線内のマス数)にわたる部分和制約になる。複数の線を横切るタイルは制約同士を結合する——つまりタイルペイントは「線が変数を共有するノノグラム」だ。

この見方は退化極限で答え合わせができる。タイルを全部 1 マスに刻むと、タイルペイントは二値トモグラフィー(行和・列和から 0/1 行列を復元する古典問題)そのものになる。トモグラフィーの非一意性は有名で、実測でもそのまま出た。8×8 全開示・150 盤の粒度スイープ:

maxSize タイル数(平均) 一意 probe 完答 count 単独完答
1 64.0 0.0% 0.0% 0.0%
2 45.5 1.3% 1.3% 0.0%
3 35.9 48.7% 48.7% 1.3%
5 25.5 93.3% 93.3% 19.3%
8 18.6 98.7% 98.7% 48.0%
12 13.8 100.0% 100.0% 78.7%

1 行目がトモグラフィーだ。情報量の勘定も合う: 2n=16 個の数字は高々 16·log₂9 ≈ 51 bit しか持てない。自由ブール 64 個は入り切らず、14 個ならお釣りが来る。「タイルを大きくする」ことこそが、トモグラフィーに足された情報であり、このパズルを成立させている当のものだ。

ルールは 1 本の法則を 3 段階の強さで読む

4 段のラダーは、実は全部同じ部分和の法則だ。

レベル ルール
count 線を区間として読む、両方向: 数字に達したら残りは白、開きマス全部でちょうどなら全部塗る
edge タイルごとの貪欲限界: 負債より大きいスライスは白、他のスライスの合計では負債を賄えないスライスは黒
fit 部分和の到達可能性を正確に問う: 負債を構成する部分集合すべてに入るスライスは黒、どれにも入らなければ白
probe 1 タイルに色を仮置きし、下位ルールを fixpoint まで回して矛盾したら棄却

edgefit の差は「合計」と「構成可能性」の差だ。スライス {2, 2, 2} が負債 3 を負うと、貪欲限界は全部素通し(どれも 3 以下、他の合計は 4 以上)だが、部分和 {0, 2, 4, 6} に 3 は無い——fit だけが矛盾を見る。実装は prefix/suffix の部分和 bitmask で、タイルごとの「自分抜きの到達集合」を 1 回の合成で出す。

強制力として countedgefit入れ子になっているのがこのラダーの特徴で、ここから ablation の結果が定理として予言できる。300 盤/サイズ・全開示の生ストリームで、増分ラダーと ablation の両方:

増分(各段を足していく):

盤面 count +edge +fit +probe 生ストリームの一意率
6×6 61.7% 98.7% 98.7% 98.7% 98.7%
8×8 22.3% 87.7% 90.0% 91.7% 91.7%
10×10 1.3% 54.0% 60.3% 82.3% 82.7%

Ablation(全ラダーから 1 段抜く):

盤面 full −count −edge −fit
6×6 98.7% 98.7% 98.7% 98.7%
8×8 91.7% 91.7% 91.7% 91.7%
10×10 82.3% 82.3% 82.3% 82.3%

完全にフラット。−count と −edge は入れ子だから当然として、−fit まで無傷なのは probe が分岐で fit の取り分を回収するからだ。ablation だけ読めば「全ルール冗長」、増分だけ読めば「全ルール必須」——この連作で繰り返し出る教訓(両方測れ)が、今回は片側が定理で片側が測定という一番きれいな形で出た。

1 マス probe には見えない曖昧さ

この連作には「probe fixpoint が完答する ⇔ 一意解」という経験則があり、#320 クロットで初めて破れた。破れたのは偶然ではない——ルールが算術だけのパズルでは、曖昧さは多タイルの組み替えに棲むからだ。タイルペイントも純算術なので、ギャップは理論どおり再現した: 10×10 の一意 248 盤中 1 盤が probe 不能(82.3% vs 82.7%)。probe ⇒ 一意は全サイズで成立、逆だけが破れる。

このギャップには顔がある。第 2 解とは「反転が全数字線上で相殺するタイル集合」であり、最小のものは探索ゼロで答えから直読できる:

  • 単独 silent flip: どの数字線にも触れないタイル(間引きで数字が消えた時のみ可能。全開示では、全タイルは自分の行に触れるので定理として不可能
  • ペア silent flip: 塗り・白のペアで、全数字線上のスライスベクトルが一致——入れ替えてもどの数字も動かない

実測(300 盤/サイズ): 半分に間引いた 8×8 では非一意 290 盤中 249 盤がペア証明書 1 枚で説明できた。ところが全開示では 81 盤中 0 盤。全開示の曖昧さはペアではなく、トモグラフィー古典の 2×2 スイッチ(対角 4 タイルの同時反転=4 タイルの組み替え)に代表される長い交換連鎖だ。1 マス probe にも、ペア検査にも見えない。密度のダイヤル 1 本で、曖昧さの住処が「ペア」から「連鎖」へ引っ越す。

生成はコイン投げ

タイルペイントは連作で初めて、**配置空間が「全部」**のパズルだ。連結性も形状則も隣接則も無いので、R 枚のタイルの塗り方 2^R 通りすべてが合法な答え。生成器は分割を引き、タイルごとにコインを投げ、答えから行・列の数字を読み取るだけ——探索なし、リトライなし、リスタート上限なし。アクレを 8 時間ハングさせた重い裾は、今回も構造的に存在しない。

出荷 bank は全開示から「目標レベルがまだ完答できる限り数字を間引く」方式で 60 盤(6/8/10 × 4 グレード各 5)。数字の中央値は 12 本中 7、16 本中 10、20 本中 13。一意性は探索エンジンで再証明し、分岐数の中央値は全サイズで 0——fixpoint だけで証明が済む。

エンジンの信頼性は 2 系統の突き合わせで担保する: ルールラダーを伝播させる探索と、スライス表も部分和も持たない生タイル総当たり(行・列の集計と印刷ルールのバリデータのみ)。800/800 の (盤面, レベル) ペアで解数一致。検出したペア証明書が本当に第 2 解であることも、総当たりで両方向から確認している。

テストは 34 本。デモとコードはこちら:

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?