ドッペルブロック (Doppelblock) を、5 つのルールセット内蔵でブラウザに実装した。n×n 盤の各行・各列には 1 … n−2 が 1 個ずつと、ブロックマスがちょうど 2 個入る。行・列の外に書かれた数は、その行（列）の 2 個のブロックに挟まれたマスの数字の合計だけを意味する。ソルバー内蔵パズル第 44 弾。
デモ: https://sen.ltd/portfolio/doppelblock/
リポジトリ: https://github.com/sen-ltd/doppelblock
手がかりが「どのマスの話なのか」を言わない
カックロなら、合計の適用範囲は紙に描いてある。17 がどのマスたちの話なのかは、1 文字も書く前に見て分かる。ビルディングもカックラスも不等号ナンプレも同じで、手がかりのスコープ（関与する変数の集合）は盤面が固定している。
ドッペルブロックは違う。手がかりは「2 個のブロックに挟まれたマス」の合計だが、その 2 個がどこにあるかこそ、これから求めるものだ。つまり 制約のスコープ自体が変数になっている。
厄介に聞こえるが、これが設計の全てだ。この構造から、印字された数に対して最初にやるべきことは算術ではなく幾何になる。長さ L の窓には 1 … n−2 から相異なる L 個が入るので、その合計は
[ L(L+1)/2 , (n−2) + (n−3) + … ]
の範囲に必ず収まる。しかもこの区間の値は全部到達可能だ（区間の端が正しいことも、区間内が全部埋まることも、部分集合の全探索と突き合わせてテストしてある）。含意を逆向きに読むと、手がかりは 距離についての言明になる:
| 8×8 の手がかり | 許される窓の長さ |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 6 | 1, 2, 3 |
| 15 | 3, 4, 5 |
| 20 | 5 |
| 21 | 6 |
手がかり 0 は 2 個のブロックが隣接していることを確定させる。8×8 の 21 は両端に確定させる。間の値は 2〜3 通りの隙間を残す。だからソルバーの第 2 段 scope は、数字を 1 個も見ずに、全ての手がかりを純粋な配置制約として読む。それだけで 4×4 の 37.5%、6×6 の 20.3% のマスが確定する。
盤面は「2 つの記号を同じ色で塗ったラテン方陣」
値 1 … n−2 はそれぞれ各行・各列にちょうど 1 個ずつ入るので、置換行列を 1 枚占める。残り（＝ブロックマス）は両側の次数がちょうど 2 の二部グラフで、König の辺彩色定理よりこれは常に 2 枚の置換行列に分解できる。
つまりドッペルブロックの答えは、位数 n のラテン方陣の n 個の記号のうち 2 個を同じ色で塗ったものにちょうど一致する。この帰結が 2 つとも実務で効く。
生成器が一切探索しない。 記号ごとに「まだ未割り当ての二部グラフ」から完全マッチングを 1 枚ランダムに剥がしていく。残りグラフは常に正則なので König が存在を保証し、失敗しない。最後に 2 記号を塗るだけ。引くたびに必ず合法な答えが出る。棄却も、リスタートも、重い裾を持つ打ち切り探索も要らない。
export function randomLatinSquare(n: number, rng: () => number): Uint8Array {
const square = new Uint8Array(n * n).fill(255);
const free = Array.from({ length: n }, () => new Uint8Array(n).fill(1));
for (let sym = 0; sym < n; sym++) {
// 列順をランダム化した Kuhn 法。残りグラフが正則なので Hall 条件は
// 常に成り立ち、ここは絶対に失敗しない。
...
}
}
同時に機械検査になる。 ラテン方陣→盤面の写像は全射で、盤面 1 枚の逆像の大きさは 2^k（k はブロックパターンの二部グラフのサイクル数）。各サイクルは 2 つの塗る記号への振り分け方が 2 通りあるからだ。したがって、手がかりを 1 個も置かない盤に独立エンジンをかけると、Σ 2^cycles = L(n) がぴったり成立していなければならない:
| n | 列挙された盤面数 | Σ 2^cycles | L(n) |
|---|---|---|---|
| 4 | 216 | 576 | 576 |
| 5 | 66,240 | 161,280 | 161,280 |
「2 つのエンジンが一致した」よりずっと強いテストだ。このリポジトリの誰も計算していない外部の数（ラテン方陣の個数）にエンジンを縛り付けている。
5 つのルール、そのうち 4 つは答えを一切変えない
ここが連作の他の 43 本と決定的に違う。普通ラダーは 5 つの異なる演繹で、面白い問いは「どれが盤を支えているか」だ。今回は 1 つの制約を 5 段の整合性強度で見る構成になっている:
| レベル | ルール |
|---|---|
line |
順列部分だけ。各行列にブロック 2 個・各値 1 個。手がかりは一切読まない |
scope |
＋手がかりを幾何としてのみ読む。2 個のブロックの配置を列挙し、窓長が印字された合計に到達しうるものだけ残す。数字は見ない |
bounds |
＋合計に対する境界整合性。窓内マスの候補の最小値和・最大値和が手がかりを挟む配置だけ残す |
gac |
＋領域整合性。候補ごとに「完全な (ブロック対, 数字順列)」の証人を 1 個探し、無いものを消す |
probe |
＋シングルトン整合性。候補を 1 個仮定して gac を回し、矛盾したら落とす |
2n 個の合計を全部印字し、盤内には何も印字しない無フィルタ盤で、1 段ずつ足したときの確定マス率:
| 盤 | line | scope | bounds | gac | probe |
|---|---|---|---|---|---|
| 4×4 | 0.0% | 37.5% | 65.5% | 65.5% | 65.5% |
| 5×5 | 0.0% | 32.8% | 67.6% | 73.6% | 75.9% |
| 6×6 | 0.0% | 20.3% | 38.4% | 52.8% | 73.8% |
| 7×7 | 0.0% | 11.7% | 16.3% | 26.6% | 63.0% |
| 8×8 | 0.0% | 4.7% | 5.4% | 8.5% | 41.5% |
最初の列が最初の結果だ。line は全サイズで 0.0%。 盤内に何も印字されていない状態では「各行列にブロック 2 個・各値 1 個」は 1 マスも決められない。まだ始まっていない盤についての制約でしかない。このパズルの情報は 100% 合計の側にある。
次に、フル probe ラダーから 1 ルールずつ抜く。連作の他のエントリでは、この表こそ驚きが出る場所だった。今回はほぼ空で、それが結論になる:
| 盤 | 変種 | 完走 | 確定マス | fixpoint が動いた盤 | 構築した行割当 | probe 回数 |
|---|---|---|---|---|---|---|
| 6×6 | full | 28.3% | 73.9% | — | 755 | 74 |
| 6×6 | −line | 28.3% | 73.9% | 60 中 0 | 907 | 74 |
| 6×6 | −scope | 28.3% | 73.9% | 60 中 0 | 755 | 74 |
| 6×6 | −bounds | 28.3% | 73.9% | 60 中 0 | 777 | 74 |
| 6×6 | −gac | 28.3% | 73.9% | 60 中 0 | 0 | 117 |
| 6×6 | −probe | 18.3% | 54.1% | 60 中 28 | 167 | 0 |
| 8×8 | full | 0.0% | 39.7% | — | 59,534 | 591 |
| 8×8 | −line | 0.0% | 39.7% | 25 中 0 | 65,043 | 591 |
| 8×8 | −scope | 0.0% | 39.7% | 25 中 0 | 59,534 | 591 |
| 8×8 | −bounds | 0.0% | 39.7% | 25 中 0 | 60,458 | 591 |
| 8×8 | −gac | 0.0% | 29.5% | 25 中 21 | 0 | 938 |
| 8×8 | −probe | 0.0% | 13.3% | 25 中 22 | 795 | 0 |
肝は「fixpoint が動いた盤」の列だ。完走したかどうかではなく、候補集合がビット単位で違う状態に落ちた盤を数えている。ここから 3 つの別々の結論が出る。
scope は完全な死荷重。 fixpoint もコストも同一 —— 8×8 で構築した行割当が 59,534 で 1 の位まで一致する。偶然ではない。bounds は scope と同じ配置集合を歩き、より厳しいテストを掛けるので、scope が配置を殺せる場面は原理的に存在しない。2 つを別ルールとして書いたのは読み味が違うから（片方は幾何、片方は算術）で、同じ伝播器の片方に足枷を付けただけだったことを見つけたのは ablation 表だ。ablation を回さずにルールラダーを出荷すると、この種類のバグを一緒に出荷することになる。
line と bounds は純粋な加速器。 どの盤でも fixpoint は同じ。ただし line を抜くと重いルールが構築する行割当が 6×6 で 20%、8×8 で 9% 増える。買っているのは時間であって答えではない。
gac は「途中まで無料」。 6×6 では無くても probe ラダーは同じ場所に着く。8×8 では抜くと 25 盤中 21 盤の fixpoint が動き、確定率が 10 ポイント落ちる —— それでも「完走」列は変わらない。8×8 ではもともと 0% だからだ。
完走列を動かすのは probe だけで、しかも大きく動かす（6×6 で 28.3% → 18.3%、7×7 で 5.0% → 0.0%）。
明るい要約は「シングルトン整合性がソルバーの本体で、他は全部プリコンディショナ」。正直な要約は「入れ子のラダーは構造上、面白い ablation 表を出しようがない。それでも回す理由は scope のようなバグを見つけるためだ」。回したら、実際に見つかった。
「安い整合性は前処理になるか」を測る
4 つのルールが 5 つ目を安くするためだけに存在するなら、当然「本当に安くなっているのか」を測るべきだ。gac の実装は標準の support schema を使っている —— 行を全列挙するのではなく、未サポートの (マス, 値) ごとに証人を 1 個だけ探す。だから緩い行では既に強く短絡する。そのベースラインに対して、安い段が買えるものは期待より小さい:
| 盤 |
gac 単独の行割当数 |
line+scope+bounds を前置 |
削減 |
|---|---|---|---|
| 6×6 | 177 | 155 | 12.5% |
| 7×7 | 400 | 365 | 8.7% |
| 8×8 | 606 | 563 | 7.1% |
7〜12%。安いルールが本当に効いているのは 1 段上だった。gac を抜くと probe は同じ場所に着くのに 6×6 で 58%（117 対 74）、8×8 で 59%（938 対 591）多く仮定を置く必要がある。効く前処理は「強いルールを速くする」ではなく「強いルールに投げる質問を減らす」ほうだった。
幾何を最も強く縛る合計ほど、パズルとしては悪い
scope が手がかりを距離の言明として読む以上、盤ごとに自然な「鋭さ」が定義できる —— 2n 個の合計が平均で何通りの窓長を残すか。これで盤を並べると、幾何とパズルの質は逆を向く:
| 盤 | 手がかり 1 個あたりの残り窓長 |
scope の確定率 |
probe の確定率 | 解が一意 |
|---|---|---|---|---|
| 6×6 最も鋭い 1/3 | 1.18 | 26.6% | 58.4% | 10.6% |
| 6×6 真ん中 1/3 | 1.33 | 23.8% | 72.6% | 27.3% |
| 6×6 最も曖昧な 1/3 | 1.49 | 17.2% | 84.7% | 41.2% |
| 7×7 最も鋭い 1/3 | 1.38 | 16.9% | 51.2% | 5.0% |
| 7×7 最も曖昧な 1/3 | 1.71 | 12.4% | 81.9% | 37.5% |
0 と最大値だらけの盤は、scope が最も雄弁で、パズルとしては最も貧しい。理由はルールにそのまま書いてある。手がかり 0 は 2 個のブロックの位置を完全に教えるが、数字については一言も言わない。 幾何的な鋭さと算術的な中身は綱引きの関係にあり、パズルが必要としているのは後者だ。手でドッペルブロックを作るなら、これは実用的な指針になる —— 合計が極端値ばかりの答えは、どれだけ整って見えても悪い答えだ。
「盤内に何も印字しない」代償
出版されるドッペルブロックは 2n 個の合計だけを印字し、盤内は空にする。ランダムに答えを引くと、それでは大抵足りない:
| 盤 | 答え数 |
bounds 完走 |
gac |
probe |
解が一意 |
|---|---|---|---|---|---|
| 4×4 | 300 | 56.0% | 56.0% | 56.0% | 56.0% |
| 5×5 | 300 | 45.3% | 50.7% | 54.7% | 54.7% |
| 6×6 | 200 | 10.5% | 20.0% | 29.5% | 29.5% |
| 7×7 | 120 | 0.8% | 5.0% | 11.7% | 11.7% |
| 8×8 | 80 | 0.0% | 1.3% | 2.5% | 2.5% |
8×8 では 40 枚に 1 枚しか、自分の合計だけで一意にならない。綺麗な 8×8 が欲しい作者は、長く探すか、盤内に数マス印字するかだ（中央値は 64 マス中 5 マス）。そして最後の 2 列に注目 —— probe 完走と一意性は 1,000 盤すべてで、両方向とも例外なく一致した。
出した null result
ブロックマスは次数 2 の二部グラフなので、互いに素な偶サイクルに分解される（12-サイクル 1 本、6-サイクル 2 本、4-サイクル＋8-サイクル、…）。難易度のつまみとして魅力的に見える。実際は違った: 6×6 で k = 1 / 2 / 3 の probe 確定率は 73.4% / 71.9% / 69.4%、一意率は 24.1% / 27.9% / 22.2%。ノイズだ。
健全性
機構を一切共有しない 2 エンジン。伝播探索はマスの候補で分岐する。生エンジンは盤を行 1 本まるごと単位で列挙する —— その行のブロック 2 列を選び、1 … n−2 を配り、その行の合計を検査して再帰 —— し、葉ごとにルール本文で採点する。518/518 の盤×エンジン組で一致した。加えて上の census 恒等式、そして「どのレベルのどのルールも、どの手がかり体制でも、真の値をマスから削らない」テスト。全 41 テスト。
ソルバー内蔵パズル第 44 弾。全体が TypeScript でランタイム依存ゼロ。npm run stats でこの記事の表は全部再生成できる。
デモ: https://sen.ltd/portfolio/doppelblock/
リポジトリ: https://github.com/sen-ltd/doppelblock