フィル・ア・ピクス（Fill-a-Pix） を 3 段のソルバー内蔵でブラウザに実装した。この種の盤の作り方は「絵を描く → 手掛かりを全部見せる → 一意のまま抜けるだけ抜く」が定番だが、これは全部見せれば絵が 1 つに決まるという前提に乗っている。その前提は、盤の辺が 3 で割って 2 余るときに崩れる。手掛かりを全部並べる写像は三重対角行列のクロネッカー積で、その行列式は周期 6 で並び、n ≡ 2 (mod 3) のときだけ 0 になる。そのとき一部の絵には、手掛かりが 1 つも変わらない双子（別の絵）がいて、手掛かりをどう選んでも一意にできない。5×5 では 73.4%、8×8 では 39.9%。双子は「行か列を 1 本反転する」ものと、稀な「2 ブロック型」の 2 族で全部であることを示し、5×5 の全 33,554,432 枚で 4 通りの独立な数え方（手掛かりでの仕分け・核の直接列挙・分類器・閉じた式）が 1 枚の狂いもなく一致した。行・列反転だけの数え上げは OEIS A283624 に一致し、2 ブロック型まで含めた数列は OEIS に無かった。生成器は双子のいる絵を引き直す（176 盤で 71 回、厳密値からの予測は 58.8 回）。出荷 20 盤、テスト 20 件。ソルバー内蔵パズル第 73 弾。
デモ: https://sen.ltd/portfolio/fill-a-pix/
リポジトリ: https://github.com/sen-ltd/fill-a-pix
ルール
- マスを塗って絵を完成させる
- 数字は、そのマス自身を含む 3×3 のブロックの中にある塗りマスの数
- 盤の端ではブロックが切れる。角の数字は 4 マス、辺の数字は 6 マスしか見ない
- 数字の無いマスも塗られることがある（情報を持たないだけ）
ルールは Conceptis の Fill-a-Pix の説明で確認した（「手掛かりのマス自身も数える」は実装を左右するので、名前の印象で書かずに一次資料を読んだ）。
定番の作り方と、その前提
ソルバー内蔵パズルのシリーズでは、生成器の作り方にだいたい 2 通りある。答えを引いてから手掛かりを足していくか、全部見せた状態から抜いていくか。フィル・ア・ピクスは後者が自然だ。絵を 1 枚引いて、全マスの数字を出して、ランダムな順に 1 つずつ消し、答えが一意のままなら消したままにする。最後には「どの 1 つを消しても一意でなくなる」局所極小の盤が残る。
ただしこれは、全部見せた状態が一意であることを前提にしている。全部見せても答えが 2 つある絵なら、どう抜いても一意にはならない。手掛かりを「どれだけ見せるか」が作者のダイヤルだとすると、そのダイヤルが上限で振り切れてもまだ足りないケースがあるかどうか、を最初に確かめた。
行列式は周期 6
手掛かりは周囲 9 マスの和なので、全部見せるのは絵 x から数字の並びへの線形写像だ。これは「各列を縦 3 マスで足す」→「その結果を横 3 マスで足す」に分解できるので、クロネッカー積
$$
A = T_h \otimes T_w
$$
になる。T_n は対角とその隣が 1 の n×n 三重対角行列。A が（実数の上で）単射になるのは、両方の因子が正則なときに限る。
T_n の行列式を最後の行で展開すると d(n) = d(n−1) − d(n−2)、d(0) = d(1) = 1 なので、n = 1, 2, 3, … に対して
1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1, …
と周期 6 で並び、0 になるのは n ≡ 2 (mod 3) のときだけだ。
export function detT(n: number): number {
let a = 1; // d(0)
let b = 1; // d(1)
if (n === 0) return a;
for (let i = 2; i <= n; i++) [a, b] = [b, b - a];
return b;
}
n ≡ 2 のとき、核は u = (+1, −1, 0, +1, −1, 0, …, +1, −1) で張られる。どの 3 連続の窓でも和が 0 になるので、ある列にこれを足してもどの手掛かりも変わらない。絵がこの反転を受け付けるのは、その列の非ゼロ位置が 0 1 ? 0 1 ? … 0 1（またはその補数）と読めるとき。そうなればその絵には、手掛かりが完全に一致する双子がいる。
const tryLine = (kind, index, len, at) => {
const u = kernelT(len); // 1, -1, 0, 1, -1, 0, ..., 1, -1
if (!u) return;
for (const sign of [1, -1]) {
let ok = true;
const cells: number[] = [];
for (let i = 0; i < len && ok; i++) {
const d = u[i] * sign;
if (!d) continue;
const c = at(i);
if ((d > 0 && pic[c]) || (d < 0 && !pic[c])) ok = false; // +1 は白→黒、-1 は黒→白
cells.push(c);
}
if (ok) out.push({ kind, index, cells });
}
};
つまり盤は 2 種類に分かれる。どちらの辺も 2 (mod 3) でなければ、どの絵も全部の手掛かりで一意に決まり、生成器は「全部見せて抜く」を安心して回せる。実際、その種の正方盤 12 サイズで 24,000 枚のランダムな絵をソルバーに解かせて、2 つ目の答えは 1 度も出なかった。辺が 2 (mod 3) なら、一部の絵はどう手掛かりを選んでもパズルにならない。デモ下部の「twin lab」で、双子を持つ絵を引いて、枠で囲んだマスを反転すると、手掛かりが 1 つも変わらないのを確かめられる。
4 通りで数える：5×5 の全 3355 万枚
「双子とは、成分が {−1, 0, 1} の核ベクトルがちょうど 1 本当てはまること」を、共有部分がなるべく少ない 4 通りのやり方で総当たり検証した。
- 手掛かりで仕分ける。全部の絵の手掛かり列をキーにして、2 枚以上いるグループに属する絵を数える。理論を一切使わない（20 マスまで）
- 核を直接列挙する。3 値ベクトルを 1 行ずつ置き、行 r+1 を置いた時点で行 r を中心とするブロックの和が 0 かを確かめる。得られた核ベクトルの極小元だけ残し、各絵に当てはまるかを見る
- 分類器（下の節）で 1 枚ずつ判定する
- 閉じた式で数える
| 盤 | 絵の数 | 双子あり | 仕分け | 核 | 式 | 行・列の反転 | 2 ブロック型のみ | 核ベクトル（極小） |
|---|---|---|---|---|---|---|---|---|
| 2×5 | 1,024 | 996 (97.3%) | 996 | 996 | 996 | 996 | 0 | 344 (42) |
| 3×5 | 32,768 | 10,816 (33.0%) | 10,816 | 10,816 | 10,816 | 10,816 | 0 | 26 (6) |
| 4×4 | 65,536 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4×5 | 1,048,576 | 433,920 (41.4%) | 433,920 | 433,920 | 433,920 | 433,920 | 0 | 80 (8) |
| 5×5 | 33,554,432 | 24,644,272 (73.4%) | — | 24,644,272 | 24,644,272 | 24,587,824 | 56,448 | 3,194 (216) |
（1×1〜5×5 の全 15 サイズはデモページと README にある。）すべてのサイズで 4 通りが一致した。そして 5×5 で初めて、どの行も列も反転できないのに双子がいる絵が 56,448 枚（双子の 0.23%）出てくる。
双子の完全なリスト
片方の辺だけ 2 (mod 3) のとき（例えば高さ）、核は u ⊗ （何でも）なので、3 値の核ベクトルは「列ごとに ±u か 0」しかない。双子がいる ⇔ どれかの列が当てはまる。列は互いに素なので数え上げは積になる。u の非ゼロ成分が L 個なら、1 列あたり 2^L 通りの塗り方のうち 2^L − 2 通りがどちらのパターンにも当てはまらない。
両方の辺が 2 (mod 3) のとき、核は u ⊗ a + b ⊗ u で、もう 1 族出てくる。行を「u_i = 0 か否か」で分け、列も同じく分ける。u_i = 0 の行・列を通る直線は、他と重ならない自分だけのマスを持つ。残り（両方の u が非ゼロのマス）では
$$
d_{ij} = u_i u_j (a_j + b_i)
$$
と書けて、すべての a_j + b_i が −1, 0, 1 のどれかでなければならない。a の値の幅と b の値の幅を足して 2 以下なので、場合は 2 つしかない。
- a か b が定数：d は丸ごとの行・列の集まり（行・列の反転）
- 両方とも定数でない：ずらすと a は {0, 1}、b は {−1, 0} の値を取る。これが 2 ブロック型で、行の集合 I′ × 列の集合 J の長方形に +u_i u_j、補集合の行 × 補集合の列に −u_i u_j、それ以外は 0。丸ごとの 1 本の直線を含まない
これで全部だ。さらに両方の u が非ゼロのマスを
$$
Y_{ij} = x_{ij} \oplus [u_i u_j = -1]
$$
と塗り直すと、条件が小さな 0/1 行列の言葉になる。直線が当てはまる ⇔ Y のその行か列が定数。2 ブロック型が当てはまる ⇔ Y のどの行も「J の上で全部 0」か「J の外で全部 1」。分類器はこれをそのまま実装している:
const full = (1 << b) - 1;
for (let J = 1; J < full; J++) {
if (!Y.every((y) => (y & J) === 0 || (y | J) === full)) continue;
// 行 i は (Y[i] & J) === 0 なら I' に、そうでなければ補集合に入る
...
return { kind: 'block', cells };
}
数え上げも同じ形でできる。Y を 1 行ずつ積んでいき、「ここまでのどの行も許す J の集合」を状態にする。行ごとに状態は積集合で縮むだけなので、状態数は小さく収まる（6×6 の Y で 0.35 秒）。
let states = new Map<bigint, bigint>([[(1n << BigInt(Js.length)) - 1n, 1n]]);
for (let r = 0; r < a; r++) {
const next = new Map<bigint, bigint>();
for (const [st, cnt] of states)
for (const [s, mult] of groups) { // 同じ「許す J の集合」を持つ行をまとめたもの
const t = st & s;
next.set(t, (next.get(t) ?? 0n) + cnt * mult);
}
states = next;
}
return states.get(0n) ?? 0n; // 最後にどの J も残らなければ双子なし
m×m の Y のうち「定数の行も列も無い」ものの数は、包除原理の閉じた式で出る。2, 102, 22874, 17633670, 46959933962, … で、これは OEIS A283624（「どの行も列も全成分が同じでない n×n の 0/1 行列の数」）と 8 項目まで一致した。2 ブロック型も除いた双子なしの数は 2, 102, 22730, 17564070, 46913648762 で、OEIS には載っていなかった。どちらも統計ツールが毎回 m = 4 までの総当たりと突き合わせる。
サイズごとの割合
厳密な双子の割合は、Y が 6×6 まで（盤では 8×8 まで）なら安く計算できる。それより大きいと状態数が爆発するが、行・列の反転だけの割合は閉じた式でどのサイズでも厳密に出る。これを、手掛かりを全部見せたソルバーの標本（各 2,000 枚）と突き合わせた:
| 盤 | 双子あり（厳密） | 行・列の反転（厳密） | ソルバーの標本（95%） |
|---|---|---|---|
| 5×5 | 73.446% | 73.277% | 74.80% ± 1.90% |
| 8×8 | 39.873% | 39.814% | 38.55% ± 2.13% |
| 11×11 | — | 15.848% | 14.40% ± 1.54% |
| 14×14 | — | 5.327% | 5.35% ± 0.99% |
| 17×17 | — | 1.647% | 1.50% ± 0.53% |
| 20×20 | — | 0.487% | 0.35% ± 0.26% |
| 8×10 | 27.202% | 27.202% | 27.10% ± 1.95% |
| 10×11 | 7.543% | 7.543% | 6.90% ± 1.11% |
2 以外の余りのサイズ（6×6, 7×7, 9×9, …）はすべて 0%。分類器とソルバーの判定が食い違った絵は 50,000 枚中 0 枚で、分類器が挙げた双子はすべて「反転しても手掛かりが 1 つも変わらない」ことを確かめている。
2 ブロック型は実在するが、薄く、急速に消える。8×8 では厳密に全体の 0.0593% で、100 万回引いて 617 回（期待値 593）。11×11 では 100 万回で 10 回。8×8 より大きいと、表示している桁では行・列の反転の割合がそのまま双子の割合になる。
生成器：双子なら引き直す
生成器は、各マスを公平なコインで塗って絵を引き、辺が 2 (mod 3) なら分類器に双子の有無を尋ね、いれば引き直す。探索は要らない。その後、手掛かりを全部見せてランダムな順に 1 つずつ抜き、一意のままなら抜いたままにする。一意性の判定は既知の答えと逆の値から先に枝分かれするので、2 つ目の答えがあるときは数ノードで見つかる。ノード上限に当たった判定は「手掛かりを残す」側に倒す（推測はしない）。
5〜15 の各サイズで 16 盤、計 176 盤を作った:
| 盤 | 残った手掛かり | 引き直し（期待値） | count / pair / probe / 探索 で完成 | 1 盤の時間（中央値 / 最悪） |
|---|---|---|---|---|
| 5×5 | 41.5% ± 1.4% | 54 (44.3) | 0 / 14 / 2 / 0 | 9 / 16 ms |
| 8×8 | 45.4% ± 1.3% | 15 (10.6) | 0 / 6 / 10 / 0 | 151 / 414 ms |
| 10×10 | 43.4% ± 0.7% | 0 (0.0) | 0 / 1 / 14 / 1 | 561 / 2,459 ms |
| 11×11 | 43.1% ± 0.8% | 1 (3.0) | 0 / 1 / 14 / 1 | 1,275 / 7,030 ms |
| 13×13 | 42.0% ± 0.5% | 0 (0.0) | 0 / 1 / 10 / 5 | 5,218 / 14,580 ms |
| 15×15 | 44.2% ± 0.7% | 0 (0.0) | 0 / 0 / 8 / 8 | 19,040 / 216,501 ms |
引き直しは 176 盤で計 71 回、厳密な双子の割合からの予測は 58.8 回。それ以外に、2 種類の盤の違いは下流に現れない。残る手掛かりは 2 (mod 3) でないサイズで平均 44.2%、2 (mod 3) のサイズで 43.2%。
補集合を取ると各手掛かり v はブロックサイズ − v に写るので、ある絵に双子がいる ⇔ その補集合にも双子がいる。だから引き直しは塗りマスの割合を半分から動かさない（生成した盤の塗りマスは 49.9%）。これはテストでも確かめている。
盤はラダーにとって難しい。176 盤のうち count で完成するのは 0、pair で 37、probe で 118、探索が要るのが 21。貪欲に抜くので、最後に抜ける手掛かりは深い推論でしか取り戻せないものになる。大きい盤ほど探索が要る（15×15 は 16 盤中 8 盤）。
どの手掛かりが残るか
作った全盤をまとめて、最初に見せた手掛かりのうちどれが残ったかを数えた。最初は「0 や満杯のように 1 つでブロック全体を決める極端な値ほど残るだろう」と思っていたが、逆だった。
- 位置が効く：内側の手掛かりは 45.3%、辺は 40.0%、角は 37.6% が残る（標準誤差 0.4%, 0.7%, 1.8%）。角の手掛かりは 4 マスしか見ず、その 4 マスは隣の手掛かりもすべて見ている
- 値はほとんど効かない：内側の 1〜8 はすべて 44.8%〜46.7%
- ブロックを 1 つで決める手掛かり（どこでも 0、角の 4、辺の 6、内側の 9）はむしろ残りにくい：357 個中 35.3%（± 2.5%）、それ以外は 43.6%
一色のブロックは周囲の手掛かりを上限か下限に押しやり、上限・下限に張り付いた手掛かりはまさに count と pair が働く相手なので、たいてい隣が復元してしまう——というのが私の読みだが、これは推測で、測ったのは率の方だけだ。
段（rung）の値段
| 段 | やること |
|---|---|
count |
塗りマスがすでに数字に達した手掛かりはブロックの残りを白に、開いたマスを全部塗らないと届かない手掛かりは全部塗る |
pair |
ブロックが重なる 2 つの手掛かりで、共有する開いたマスに入る塗りマスの数を両側から上下に挟む |
probe |
1 マスを仮に塗る（または白にする）と count と pair が矛盾を見つけるなら、逆に確定 |
pair は共有部分・片側だけの部分を前計算しておき、評価のたびに数えるだけにしている:
const needA = p.clues[q.a] - inkBoth - tally(q.onlyA, a);
const needB = p.clues[q.b] - inkBoth - tally(q.onlyB, bb);
// 共有する開いたマスの塗りマス数は lo .. hi
const lo = Math.max(0, needA - a.length, needB - bb.length);
const hi = Math.min(both.length, needA, needB);
if (lo > hi) return -1;
if (lo === both.length) fill(both, INK);
else if (hi === 0) fill(both, BLANK);
if (a.length) {
if (needA - hi === a.length) fill(a, INK);
else if (needA - lo === 0) fill(a, BLANK);
}
出荷 20 盤（8×8, 10×10, 11×11, 15×15 を各 5 盤、2,550 マス、見せている手掛かり 1,092 個）で、段を登りながらと 1 段抜いてで値段を付けた:
| 段 | 登りながら決まるマス | 登りながら完成 | 抜いたとき決まるマス | 抜いたとき完成 | 抜いたときの探索ノード |
|---|---|---|---|---|---|
| count | 93 (3.6%) | 0 / 20 | 2,210 (86.7%) | 7 / 20 | ≥ 1,986,479（1 盤が 100 万ノード上限） |
| pair | 694 (27.2%) | 1 / 20 | 353 (13.8%) | 0 / 20 | ≥ 5,625,115（5 盤が上限） |
| probe | 2,434 (95.5%) | 19 / 20 | 694 (27.2%) | 1 / 20 | — |
探索の列は probe 抜きで count と pair を毎ノード回したときの値で、両方ありなら出荷 20 盤の合計 390,758 ノード。
この表は 1 度作り直している。最初の版では count を抜いても pair を抜いても 19 / 20 が完成し、「probe さえあれば安い段は要らない」ように見えた。原因は probe の実装で、内部で仮定を試すときに only('count', 'pair') を決め打ちしていた。段を「抜いた」つもりでも、probe の中では両方とも動き続けていたわけだ。probe が「いまオンになっている安い段」だけを使うように直すと、count 抜きは 7 / 20、pair 抜きは 0 / 20 に落ちた。どの段も効いている。
function probeRule(P: Prepared, s: Uint8Array, set: Setter, rules: Rules): number {
// the probe runs whichever cheaper rungs are switched on, never itself
const inner = rules.map((on, i) => on && RULE_NAMES[i] !== 'probe');
...
対照実験（ablation）のスイッチは、上位の段の内側にも届いていなければ意味がない。いまは「probe だけをオンにすると 1 マスも決まらない」ことをテストで固定している。
持ち帰れるもの
- 「全部見せれば一意」は定理として確かめる。 フィル・ア・ピクスでは辺が 3 で割って 2 余ると崩れる。三重対角行列の行列式が周期 6 で 0 になるからで、1 行の漸化式で分かる
- 2 つ目の答えは、核の中の小さな整数ベクトル。 線形の手掛かりなら、双子は成分が {−1, 0, 1} の核ベクトルと 1 対 1。分類すれば探索なしで判定できる
- 分類が「全部」であることは、独立な数え方の一致で担保する。 手掛かりでの仕分け・核の直接列挙・分類器・閉じた式。5×5 の 3,355 万枚で 1 枚の狂いもなかった
- 稀な族を見落とさない。 行・列の反転だけでは 5×5 の双子の 0.23% が説明できなかった。標本 2,000 枚では見えず、全数え上げで初めて見えた
- 仮説は測って捨てる。 「極端な手掛かりほど残る」は逆だった。効くのは値ではなく位置
- 段を抜くなら、それを呼んでいる上位の段の中からも抜く。 probe が安い段を決め打ちで呼んでいたせいで、count と pair がタダに見えていた
数値はすべて npm run stats が出力し、README とページ本文は npm run notes が src/stats.json から書き起こしている。手で転記した数字は 1 つも無い。出荷 20 盤、テスト 20 件。ソルバー内蔵パズル第 73 弾。
デモ: https://sen.ltd/portfolio/fill-a-pix/
リポジトリ: https://github.com/sen-ltd/fill-a-pix