シャカシャカを、5 つのルールセット内蔵でブラウザに実装した。白マスに黒い直角三角形（マスの半分、直角は 4 隅のどれか）を置いて、残った白い部分がすべて長方形になるようにする。長方形は正立でも 45° 傾いていてもよい。黒マスの数字は、その上下左右 4 マスのうち三角形が入っているマスの数。ソルバー内蔵パズル第 32 弾。
デモ: https://sen.ltd/portfolio/shakashaka/
リポジトリ: https://github.com/sen-ltd/shakashaka
このパズルを選んだのは、中心のルールがソルバーにとって最悪の形で書かれているからだ。「白い領域はすべて長方形」は連結成分についての文で、最後の 1 マスが埋まるまで何も聞けないし、やっと聞けるようになったときの答え合わせは flood fill だ。このシリーズの他のパズルは、たいてい伝播できる局所ルールをくれる。これは領域をくれる。
——と思っていた。このルールは、格子点 1 個における白の角度についての条件と「ぴったり」同値だった。8 ビットとテーブル引き。領域という概念はどこにも出てこない。それはソルバーの形を変える。
わかったことは 3 つ。
- 大域ルールは局所ルールで、しかもそれは証明できる。 格子点まわりの白い 45° セクタの連続する塊は、必ず 90°・180°・360° のどれかになる。これを flood fill 側のオラクルと 1250 万通りで突き合わせた（3×3 の全盤・全配置 6^9 を含む）。不一致ゼロ。
- 素朴な局所ルールは、両方向に間違っている。 「格子点の白の角度の合計が 90° の倍数」は、空の 4×4 盤で合法な絵が 23 通りしかないところに 13958 通りを通し、しかもその 23 通りのうち 21 通りを弾く。
- 冗長な伝播器を 1 つ足したら、別の伝播器の ablation スコアが 27 ポイント動いた。 同じルール、同じ盤、同じ指標で。伝播器に「その」寄与などなく、あるのはあるセットに相対的な寄与だけだ。
伝播できないルール
ルールはこれだけ。マスは黒（与えられる。数字入りのこともある）か白。白マスには、マスの半分を占める黒い直角三角形を 1 つ、直角を 4 隅のいずれかに置くか、何も置かないか。つまり白マスの状態は 5 通り。
export const E = 0; // 三角形なし: 端まで白
export const TNW = 1; // 直角が左上
export const TNE = 2;
export const TSE = 3;
export const TSW = 4;
そして、残った白い部分は互いに素な長方形の集まりでなければならない。正立か 45° 傾き。
探索は「ダメ」をできるだけ早く聞きたい。このルールは全マスが決まるまで一言も喋らず、決まった瞬間に flood fill が「この 5 時間は無駄でした」と告げる。これは葉での検査であり、白マス 84 個を葉だけで検査する探索は 5^84 ≈ 10^59 状態を歩くことになる。
格子点まわりの 8 ビット
格子点——マスの角であって、マスではない——に立つ。そこには 4 つのマスが集まる。それぞれが 0°・45°・90° の白い角度を差し出す。そして、その場から見える情報はそれだけだ。
1 周を 45° ずつ 8 セクタに切り、北から時計回りに番号を振る。
セクタ 0,1 → 格子点の北東のマス 2,3 → 南東
4,5 → 南西 6,7 → 北西
各マスの状態は、自分の象限の 2 ビットを埋める。黒マスや盤外は何も埋めない。空の白マスは両方埋める。三角形は、直角が遠い隅なら両方、近い隅なら両方とも埋めず、それ以外は片方だけ。
export const PAT: number[][] = [
// q0: 格子点の北東のマス。格子点はそのマスの南西の隅にあたる。
// E TNW TNE TSE TSW
[0b11, 0b10, 0b11, 0b01, 0b00],
[0b11, 0b00, 0b10, 0b11, 0b01], // q1: 南東
[0b11, 0b01, 0b00, 0b10, 0b11], // q2: 南西
[0b11, 0b11, 0b01, 0b00, 0b10], // q3: 北西
];
主張はこうだ。格子点まわりの白セクタの極大な巡回連結塊をとる。すると:
白い部分が互いに素な長方形の集まり ⟺ すべての塊の長さが 2 か 4 か 8。
90°・180°・360°。角か、まっすぐな辺の上か、内部か。
なぜこれで十分か。白い部分の境界の頂点は必ず格子点に載る（三角形の斜辺は隅から隅へ引かれるので）。だから白い領域の境界は、頂点が格子点にある多角形だ。塊 4 はまっすぐな点、塊 8 は内部の点、塊 2 は 90° 曲がる角。それ以外を禁じると、領域の境界は「すべての角が同じ向きに 90° 曲がる単純多角形」になる。曲がりの総和が 360° でなければならないので、角はちょうど 4 つ。角 4 つ、すべて直角——長方形だ。辺はマスの辺かマスの対角線のどちらかで、隣り合う辺は直交するので、辺の向きは「全部軸平行」か「全部 45°」のどちらかに揃う。正立か 45°、その中間はない。
長さ 6 の塊は、L 字を L 字たらしめている凹角そのもの。奇数長の塊は 45° のくさび——孤立した三角形の尖った先だ。どちらもルールが禁じているものそのもので、第 3 の失敗モードは存在しない。
というわけで、ルール全体が 256 エントリのテーブルになる。
export const VALID_FULL = table((arcs) => arcs.every((L) => L === 2 || L === 4 || L === 8));
「合計」ではなく「塊」——ここで危うくバグを出荷するところだった
最初に書きたくなるのは「格子点の白の角度の合計が 0°・90°・180°・360°」のほうだ。popcount 1 回。塊の分解なんて要らない。どう見ても同じことに見える。
同じことではないし、安全側の近似ですらない。両方向に間違っている。
| 盤 | 合法 | 素朴ルールが通す | 合法なのに弾く | 非合法なのに通す |
|---|---|---|---|---|
| 空の 2×2 | 2 | 13 | 0 (0%) | 11 |
| 空の 3×3 | 3 | 1 | 2 (67%) | 0 |
| 空の 4×4 | 23 | 13958 | 21 (91%) | 13956 |
空の 4×4 に合法な絵は 23 通り。素朴ルールは 13958 通りを通し、現実と一致するのはそのうち 2 通りだけだ。
両方向の失敗が、たった 1 つの事実から出ている。2 つの長方形は 1 点で接してよい。 1×1 の白マス 2 つが斜めに並び、残る対角に黒マスがある——このパズルで最もありふれた絵だ。共有する角では白の角度は 180°、ただし独立した直角 2 つに割れている。合計してしまうとまっすぐな辺と区別がつかないので:
- 対角の象限に 45° + 45°、合計 90° → 通してしまう。実際は非合法なくさびが 2 つ。
- 180° + 90° が 2 つの塊、合計 270° → 弾いてしまう。実際は合法な辺と合法な角が隣り合っているだけ。
これを「エッジケース」に分類したくなる。ならない。デモに収録した解の格子点を数えると:
| 盤 | 格子点 | 空 | 角 1 つ | 辺 1 つ | 内部 | 塊 2 つ |
|---|---|---|---|---|---|---|
| 6×6 | 784 | 10% | 38% | 16% | 11% | 25% (16/16 盤) |
| 8×8 | 1296 | 8% | 35% | 16% | 13% | 28% (16/16 盤) |
| 10×10 | 1936 | 5% | 33% | 13% | 13% | 35% (16/16 盤) |
10×10 の解では、格子点の 3 分の 1 が「別々の白 2 つが 1 点で接する場所」だ。素朴ルールは、存在するすべての盤で間違っている。
こういう主張は、どうテストするのか
大域的な性質と局所的な性質の同値は、ユニットテストで直接アサートできるものではない。できるのは、もう一方の読みをきちんと独立に実装して、全部に両方かけることだ。
素朴なほう（＝ルールブックどおりのほう）は、局所ルールが使う概念を一切使わないようにする必要があった。角度なし、角なし、セクタなし。行き着いた先はこれ。
各マスを両対角線で 4 つの四分三角形に切る。合法な半マス三角形はすべてそのうち 2 つの和なので、四分三角形が絵の原子になる。
黒い直角が NW → 黒い四分は N, W NE → N, E
SE → S, E SW → S, W
白い四分三角形を flood fill する。辺での隣接だけを使うので、1 点で接する 2 領域は 2 領域のまま残る。そして各領域について、長方形判定は面積でやる。
// 座標を 2 倍しておくと、四分三角形の面積はちょうど 1。
const upright = (Xmax - Xmin) * (Ymax - Ymin);
const tilted = (Umax - Umin) * (Vmax - Vmin); // = 傾いた外接箱の面積 × 2
if (count !== upright && 2 * count !== tilted) { /* 長方形ではない */ }
U = X + Y、V = X − Y。領域は必ず自分の外接箱に収まるので、面積が等しければ領域は箱そのものだ——形の比較は要らない。座標を 2 倍してあるのでマスの角は偶数、マスの中心は奇数に載り、全部整数演算で済む。正立長方形は (x, y) での箱、45° のものは (x+y, x−y) での箱。第 3 の向きは存在しない。
そのうえで、両方の読みを、払える限りのものにかけた。
| 配置数 | 対象 | うち合法 | 不一致 |
|---|---|---|---|
| 625 | 空の 2×2 上の全配置 | 2 | 0 |
| 1,953,125 | 空の 3×3 上の全配置 | 3 | 0 |
| 46,656 | 2×3 の全盤（黒マス配置込み）上の全配置 | 46 | 0 |
| 10,077,696 | 3×3 の全盤（黒マス配置込み）上の全配置 | 328 | 0 |
| 400,000 | 黒の多いランダム 5×5 盤上のランダム配置 | 1 | 0 |
| 75,264 | 収録解すべての 1 マス・2 マス改変 | 232 | 0 |
4 行目は 6^9 だ。9 マスそれぞれが「黒」か「5 状態のどれか」。そのサイズのシャカシャカ盤すべてと、その上の絵すべて。
ただし本当に効いているのは最後の行だ。ランダム 5×5 の「うち合法」欄を見てほしい——40 万通りで1 通り。ランダム盤は主張の易しい側しか動かさない。両方の読みが、無関係な理由で大声で「ダメ」と言うだけだ。境界に座っているのは、本物の解から 1〜2 マスずれた盤のほうで、75264 通り中 232 通りが合法だった。1 つだけ信じろと言われたらこのスイープを取る。
テーブル自体を幾何に固定するテストも別にある。4 マスが格子点で出会う 1296 通りすべてについて、格子点から各セクタの真ん中方向へ髪の毛 1 本ぶん進み、その点が白かどうかを実際の絵——x + y > 1、y > x——に聞く。PAT のビットが 1 つでも間違っていたら、上の全部が「間違ったものの自己無矛盾な検証」になってしまう。
それで何が手に入るのか
局所ルールは「5 値の変数 4 つ」に対する制約なので、そのまま arc consistency の伝播器になる。各マスの定義域は高々 4 通りの 2 ビットパターンに潰れるから、制約全体は 16 ビット入力・16 ビット出力。メモ化して終わり。
const packed = supported(rules.valid, key);
for (let q = 0; q < 4; q++) {
const next = dom[cells[q]] & STATESET[q][(packed >> (4 * q)) & 15];
if (next === 0) return false;
...
}
同じ探索、同じ盤、同じ答え。違うのは「ルールが葉より前を覗いてよいか」だけ。
| 盤 | 白マス | 解 | 伝播あり: ノード | 葉だけ検査: ノード | 比 |
|---|---|---|---|---|---|
| 3×3 | 6 | 0 | 0 | 19,531 | 19,531× |
| 3×3 | 8 | 2 | 3 | 488,281 | 162,760× |
| 4×4 | 11 | 1 | 1 | 61,035,156 | 61,035,156× |
そしてデモが実際に配っている盤では、右側の列はもう印字できる数ではなくなる。
| 盤 | 白マス | 決着までのノード | 枝刈りなしで歩く状態数 |
|---|---|---|---|
| 6×6 | 30 | 1（中央値） | 5^30 ≈ 10^21 |
| 8×8 | 54 | 1.5（中央値） | 5^54 ≈ 10^38 |
| 10×10 | 84 | 1（中央値） | 5^84 ≈ 10^59 |
中央値 1 ノード。収録盤では、格子点上の arc consistency だけで、一度も推測せずに答えが決まる。
1 回あたりの検査コストは勝負の退屈なほうで、それも差はある——同じ完成盤に対して flood fill が 10.5 µs、テーブル引きが 3.2 µs。だが 3 倍速いことが要点ではない。1 割しか埋まっていない盤に対して、そもそも質問できることが要点だ。
伝播器の採点法は 2 つあって、答えが食い違う
ルール全体は、独立した局所ルール 2 つに割れる。tips（奇数長の塊なし＝ 45° のくさびなし）と reflex（長さ 6 の塊なし＝逆向きに曲がる角なし）。この 2 つの共通部分が全体になる。テストにしておくと気持ちがいい。
expect(Array.from(intersect(VALID_TIPS, VALID_REFLEX))).toEqual(Array.from(VALID_FULL));
そこに 4 つ目を意図的に足した。parity — 「白の角度は直角の整数倍」、セクタがどこにあるかは見ない。塊の分解ではなく popcount 1 回。tips に含意されるので冗長で、そして「安く済ませたい人が手を伸ばす近似」そのものだ。
ラダーを登る側——そのルールは、より弱いルールにできないことができるか:
| 盤 | ルールセット | 削減 | 完解 |
|---|---|---|---|
| 10×10 | （なし） | 0.0% | 0% |
| 10×10 | clues | 5.3% | 0% |
| 10×10 | clues + parity | 24.0% | 0% |
| 10×10 | clues + parity + tips | 74.7% | 0% |
| 10×10 | clues + parity + tips + reflex | 93.8% | 27% |
1 つ抜く側——そのルールは、より強いセットにできないことができるか:
| 盤 | 抜いたもの | 削減 | 完解 | フルセット比 |
|---|---|---|---|---|
| 10×10 | （なし） | 93.8% | 27% | — |
| 10×10 | clues | 68.8% | 0% | −25.0% 削減, −27 盤 |
| 10×10 | parity | 93.8% | 27% | −0.0% 削減, −0 盤 |
| 10×10 | tips | 32.9% | 0% | −60.9% 削減, −27 盤 |
| 10×10 | reflex | 74.7% | 0% | −19.1% 削減, −27 盤 |
増分で見ると parity はラダー 2 番目の跳ね幅で、clues 単独の削減を 4 倍以上にする。ablation で見ると、全盤サイズで最後の桁までゼロ。ここまでは想定内だった。構成上冗長だし、前作でも同じ形の結果が出ている。
想定外だったのは逆方向だ。tips を、2 つの異なるセットに対して ablation で採点してみる。
| 盤 | セット |
tips を抜くと |
削減の落ち幅 |
|---|---|---|---|
| 10×10 | clues + tips + reflex | 6.1% | −87.7% |
| 10×10 | clues + parity + tips + reflex | 32.9% | −60.9% |
同じルール。同じ盤。同じ指標。それでも数字が 27 ポイント動く。別のルール——それ自身の申告ではゼロ点のルール——が後ろに控えていて、こぼれ球を拾うからだ。ablation は伝播器を測っていない。特定の控え選手の顔ぶれに対する相対値を測っている。冗長なルールをセットに足すと、それが重複している相手の ablation スコアが静かに目減りする。
これは自分がすでに信じていたことの、より正確な言い方でもある。伝播器に「その」寄与はない。両方向を報告しないなら、それは測定ではなく好みの表明だ。
答えを一意にしているのは誰か
解が 1 つしかない盤を取り、ルールを 1 つ切って数え直す。
| 盤 | 盤数 | 数字を全部落とす: 一意のまま | 形のルールを tips まで弱める: 一意のまま |
|---|---|---|---|
| 6×6 | 60 | 5 (8%), 中央値 6.5 通り | 20 (33%) |
| 8×8 | 60 | 0 (0%), 中央値 52.5 通り | 4 (7%) |
| 10×10 | 36 | 0 (0%), 中央値 335 通り | 0 (0%) |
どちらも効いていて、形のルールのほうが大きい。だからこの盤たちは数字をほとんど載せていない。ジェネレータは全黒マスに解から数字を振り、そのあと答えが一意なままである限り数字を剥がし続ける。
| 盤 | 黒マス | 残った数字 | 割合 | 内訳 |
|---|---|---|---|---|
| 6×6 | 6.0 | 1.7 | 28% | 0:6% 1:37% 2:40% 3:16% 4:0% |
| 8×8 | 10.0 | 3.3 | 33% | 0:9% 1:25% 2:45% 3:16% 4:5% |
| 10×10 | 16.0 | 5.5 | 35% | 0:6% 1:29% 2:41% 3:21% 4:2% |
数字の 3 分の 2 は、幾何がすでに知っていたことだった。ここの 10×10 盤は、数字 5 個ほどで解が 1 つに定まる。
相互照合
すべてのカウントは 3 通りの方法で出していて、食い違えばテストが落ちる。
- 伝播つき探索 — 格子点制約と数字制約に対する arc consistency で駆動する、定義域最小優先のバックトラック。
- 伝播器を外した同じ探索 — 行優先でマスを埋め、ルールは葉でしか検査しない。答えは同じ、ノードは最大 6100 万倍。
-
validateを通すブルートフォース — 全割り当てを列挙して、ルールブックを一から読み直す（数字の算術 → flood fill → 外接箱）。許した枝刈りは「4 まで数える」ことだけなので、検証対象そのものには手を触れていない。
ラダーのラベルも、信じるのではなく検査している。生成した盤の難易度ラベルを取り、そのランクを走らせ、到達した定義域が意図した解とマスごとに一致することをアサートする。さらに健全性テストとして、すべてのランクが、すべての盤で、すべての本物の解を定義域の中に残すことを確認する。これは伝播器が推測ではなく伝播器であるための性質そのものだ。
テストは 26 本。TypeScript、ランタイム依存ゼロ。
リポジトリ: https://github.com/sen-ltd/shakashaka
デモ: https://sen.ltd/portfolio/shakashaka/