ヘテロミノ（Heteromino）を、4 段のソルバー内蔵でブラウザに実装した。このパズルには数字が 1 個も無い。矢印も、領域の境界線も、丸も無い。作者が読者に渡せるのは「どのマスを黒く塗るか」だけで、手掛かりの言語がマスの部分集合そのものになっている。ここから 2 つのことが出た。1 つ目、黒マスは同時に 2 つの仕事をしている——マスを敷き詰めから外す仕事と、同じ形のピース同士の間に立って合法にする仕事。出荷 72 盤のうち **65 盤（90.3%）**が後者に依存していた。2 つ目のほうが効いた。盤に何も書かれていないということは、伝播の起点が無いということで、下 3 段は手つかずの 8×8 のうち 2.1% しか確定できずに止まる。1 段の先読み（probe）を入れた瞬間に 100% になる。ソルバー内蔵パズル第 56 弾。
デモ: https://sen.ltd/portfolio/heteromino/
リポジトリ: https://github.com/sen-ltd/heteromino
ルール
- 盤の白マス全部をトロミノ（3 マスのピース）に分割する。3 マスの連結な形は棒と L の 2 種類
- 同じ形のピース同士は辺を共有してはいけない
- ここでの「形」は描かれたとおりの形。L を 90° 回すと別のピースとして数える。つまり形は全部で 6 種類（棒 2 向き ＋ L 4 向き）
以上。数字は 1 個も無い。
ルール 3 の「回転を区別する」がこのパズルの肝で、あとで LITS 流に「回転を同一視」する方言と比べる。結論を先に言うと、同一視した瞬間に出荷 72 盤の全部が解無しになる。
この連作で初めて、手掛かりが「書かれた物」ではない
ナンバーリンクなら数字、さしがねなら丸と矢印、ヘヤワケなら領域と数字。どのパズルも作者は盤に何かを書く。ヘテロミノは書かない。マスを消すだけだ。
ここが面白いのは、黒マスが 1 個で 2 つの仕事を兼ねていて、しかも片方だけ買うことができないという点にある。
- 穴としての仕事: そのマスは敷き詰めの対象から外れる
- 壁としての仕事: そのマスを挟んだ両側のピースは辺を共有しないので、同じ形でも合法になる
2 の実測がこれ。出荷 72 盤の答えを走査して、「1 個の黒マスを挟んで向かい合っている同形ピースのペア」を数えた。
| そういうペアを 1 組以上持つ盤 | 65 / 72（90.3%） |
| ペアの総数 | 263 組 |
| 全ピース数 | 1,968 個 |
| 1 盤あたりの中央値 / 最大 | 3 組 / 11 組 |
その黒マスを 1 個どけたら、その 2 つのピースはただの「接している双子」になって違反する。壁としての仕事は飾りではない。
1. 白紙の盤 — 1 行の帯はほぼ全滅する
手掛かりを 1 個も置かず、「空の h×w 格子をヘテロミノに分割する方法は何通りか」を全数え上げした。マス数が 3 の倍数でない長方形は最初から失格なので · にしてある。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1×n | · | · | 1 | · | · | 0 | · | · | 0 | · | · | 0 |
| 2×n | · | · | 2 | · | · | 4 | · | · | 8 | · | · | 16 |
| 3×n | 1 | 2 | 8 | 14 | 28 | 70 | 144 | 304 | 688 | 1476 | 3168 | 6956 |
| 4×n | · | · | 14 | · | · | 130 | · | · | 1414 | · | · | 14894 |
| 5×n | · | · | 28 | · | · | 686 | · | · | 20077 | · | · | 584442 |
| 6×n | 0 | 4 | 70 | 130 | 686 | 4552 | 15218 | 70654 | 372124 | 1525273 | 6893222 | 10887414* |
| 7×n | · | · | 144 | · | · | 15218 | · | · | 2001412 | · | · | 5375356* |
* は探索ノード上限に当たった下界。それ以外は厳密値で、小さいものは毎回のテスト実行でゼロから再計算して照合している。
1 行目が、このパズルのルールをそのまま縮小したような形をしている。1×n の帯は n = 3 以外どの n でも 0 通りだ。1 行しかないと入るピースは横棒しかなく、横棒 2 本を 1 行に並べたら必ず辺を共有する。だから帯にはピースが 1 個しか入らず、2 個は絶対に入らない。
ついでにこれは、手掛かりが 1 個も無くても成立する唯一の盤が 1×3 だということでもある。真っ白な 1×3 は解がちょうど 1 通り。何も印刷されていないパズル。
3×n / 4×n / 5×n / 6×n はどれも OEIS に無い。
2. 2 行の帯は、きっちり 2 のべき乗になる
2 行目もぐちゃぐちゃではなかった。
| 帯 | 2×3 | 2×6 | 2×9 | 2×12 | 2×15 | 2×18 |
|---|---|---|---|---|---|---|
| 分割数 | 2 | 4 | 8 | 16 | 32 | 64 |
| 2^m | 2 | 4 | 8 | 16 | 32 | 64 |
| 使われた棒の本数 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 列ブロックをまたいだピース | 0 | 0 | 0 | 0 | 0 | 0 |
空の 2×3m の帯の分割数 = 2^m
m = 9（2×27 = 512）まで一致した。ただし数が合ったことは、この主張のいちばんつまらない部分だ。数値一致は偶然でも起きうるので、テストでは背後の構造のほうを直接確かめている。上の表の下 2 行がそれで、全分割にわたって棒が 1 本も使われず、3 列の境界をまたぐピースが 1 個も無い。
つまり 2 行の帯は帯ではない。独立した 2×3 ブロックの列で、各ブロックは L 2 枚で 2 通りに切れる。2^m はその積というだけ。
手で追える議論になっている。左端 3 列の上段に横棒を置いてみる。その真下のマスにはまだピースが要る。そのマスを取れる L はどれも上段のマスを欲しがるが、それはもう横棒が持っている。残るのは真下の横棒だけで、それは同じ形で接しているから違反。よって左端から横棒は始められない。同じ罠が右へ伝播していく。
これがルールの効果であってピースの品揃えのせいではないことも確認してある。同形禁止ルールを切ると、空の 2×6 は再び 4 通りを超え、棒も戻ってくる。これもテストに入れた。
3. 手掛かり空間は薄い — そして全数え上げできる
手掛かりが「マスの部分集合」でしかないということは、「この手掛かり言語はどれくらい優秀か」を総当たりで答えられるということでもある。小さい盤について、あらゆるサイズのあらゆる黒マス配置を全部歩いて、それぞれの解数を数えた。
| 盤 | 黒マス数 | 手掛かり集合の数 | 解無し | 複数解 | ちょうど 1 解 |
|---|---|---|---|---|---|
| 3×4 | 3 | 220 | 37.3% | 20.0% | 42.7% |
| 3×4 | 6 | 924 | 79.7% | 1.6% | 18.7% |
| 3×5 | 3 | 455 | 34.3% | 42.9% | 22.9% |
| 3×6 | 3 | 816 | 28.2% | 54.2% | 17.6% |
| 3×6 | 9 | 48,620 | 91.8% | 1.1% | 7.1% |
| 4×5 | 2 | 190 | 2.1% | 90.5% | 7.4% |
| 4×5 | 5 | 15,504 | 57.9% | 20.0% | 22.1% |
| 4×6 | 6 | 134,596 | 65.6% | 18.8% | 15.6% |
| 4×6 | 9 | 1,307,504 | 89.5% | 3.3% | 7.2% |
| 5×6 | 3 | 4,060 | 4.6% | 93.5% | 1.9% |
| 5×6 | 6 | 593,775 | 48.2% | 40.1% | 11.7% |
| 6×6 | 3 | 7,140 | 2.6% | 97.0% | 0.3% |
| 6×6 | 6 | 1,947,792 | 33.7% | 58.7% | 7.6% |
（全部は載せきれないので抜粋。完全な表はデモページにある）
2 つのことが読める。
一意な盤はどこでも珍しい。全数え上げの中でいちばん当たりやすいのが 3×4 に 3 個で、それでも 42.7% しか通らない。
そして外し方が途中で裏返る。黒マスが少ないうちは「解が多すぎて」失敗し、多くなると「解が無くて」失敗する。後者の理由は単純で、黒マスが盤を分断して、3 の倍数でないサイズの領域を作ってしまうからだ。一意性は「まだ言い足りない」と「言ってはいけないことを言った」の間の細い帯に住んでいて、盤が大きくなるほど帯は細くなる。
全数え上げなので、最小手掛かり数は探索結果ではなく厳密な下限として出る。
| 盤 | マス数 | 一意化できる最小の黒マス数 | 密度 |
|---|---|---|---|
| 3×4 | 12 | 3 | 25.0% |
| 3×5 | 15 | 3 | 20.0% |
| 4×4 | 16 | 4 | 25.0% |
| 3×6 | 18 | 3 | 16.7% |
| 4×5 | 20 | 2 | 10.0% |
| 4×6 | 24 | 3 | 12.5% |
| 5×5 | 25 | 4 | 16.0% |
| 5×6 | 30 | 3 | 10.0% |
| 6×6 | 36 | 3 | 8.3% |
個数の最小は 4×5 の 2 個——20 マスの盤が、黒マス 2 個で一意に決まる。密度の最小は 6×6 の 3 個で 8.3%。なお 4×4 と 5×5 が 4 個なのは、マス数の 3 での余りが 1 なので合法な手掛かり数が 1, 4, 7, ... しか無く、1 個では足りないから。
4. 作者は手掛かりを「撒く」ことができない
サイズを上げてサンプリングすると、この帯は急速に閉じる。各手掛かり数についてランダムな黒マス配置を引いて、一意になった割合のピークを取ったのがこれ。
| 盤 | 各手掛かり数あたりの試行 | 最良の手掛かり数 | そこでの一意率 |
|---|---|---|---|
| 6×6 | 4,000 | 9 | 8.1% |
| 8×8 | 1,500 | 13 | 1.5% |
| 10×10 | 600 | 22 | 0.7% |
| 12×12 | 300 | — | 0% |
12×12 は、合法な手掛かり数 17 通り × 300 回 = 5,100 盤を引いて、一意なものが 1 枚も出なかった。
だから生成器はサンプリングをしない。ここで、このパズルの生成が他と決定的に違うところが出てくる。
この連作の他の生成器はだいたい同じ形をしている: 答えを先に描く → そこから手掛かりを読み取る → 一意を保つ限り手掛かりを 1 個ずつ消す。ヘテロミノはこれが全部できない。
- 手掛かりは答えの関数ではない。マスを黒くする／白くすると、そもそも「どのマスを覆うべきか」が変わってしまう
- 白マスの数は常に 3 の倍数でなければならない。つまり黒マスは1 個ずつ足すことも消すこともできない
手掛かりを 1 個減らす合法な一手が存在しないので、最小化フェーズが原理的に書けない。 残るのは「黒マス k 個を撒いて、解数を数えて、黒マスを盤上で 1 個ずつ歩かせる」しかない。
ここで実装上の罠が 1 つあった。素直に「解数」を目的関数にすると動けない。上の表のとおり、面白い密度帯ではランダム配置の多くが解が多すぎるのではなく解が無いので、探索空間の大半が「解 0」という平らな台地になる。そこで、解が無い盤には副次的な勾配——3 の倍数でないサイズの開領域がいくつあるか——を足した。これは解けるための必要条件でしかない（十分条件ではない）が、不可能領域から這い出すための坂としては機能する。
探索が予算内で到達できた最小の手掛かり数:
| 盤 | 到達できた最小の黒マス数 | 密度 |
|---|---|---|
| 6×6 | 3 | 8.3% |
| 8×8 | 7 | 10.9% |
| 10×10 | 13 | 13.0% |
| 12×12 | 24 | 16.7% |
これは探索の限界であってパズルの限界ではない。何が存在するかを言っているのは上の全数え上げの表のほうだ。
5. 測定の主役 — 段が平らで、最後に崖になる
出荷盤を一意と証明するのに要した分岐回数を、段ごとに合計した。
fit |
region |
hetero |
probe |
|
|---|---|---|---|---|
| 8×8, 40 盤 | 7,046 | 6,547 | 6,537 | 0 |
| 12×12, 32 盤 | 103,060 | 78,098 | 77,459 | 39 |
変な形の梯子になっている。region——「開いている領域のマス数は 3 の倍数」という、いかにも効きそうなルール——が fit から削るのは 8×8 で 7.1%、12×12 で 24.2%。hetero、つまりこのパズル自身のルールを符号化した段が、そこからさらに削るのが 0.2% と 0.8%。そして probe が 8×8 を 0 に、12×12 を 39 に落とす。ほぼ平らで、最後に崖。
理由は「手つかずの盤から各段が何マス確定できるか」を訊くともっとはっきりする（デモページのチェックボックスが表示しているのがこれ）。
| 1 手も指す前に確定できるマス | fit |
region |
hetero |
probe |
|---|---|---|---|---|
| 8×8 | 2.1% | 2.1% | 2.1% | 100% |
| 12×12 | 3.9% | 3.9% | 4.2% | 88.1% |
伝播の起点が無いのだ。 この連作の他のパズルは必ず何かを印刷している——数字、矢印、領域の境界——ので、局所的に 1〜2 マスが刺さり、不動点計算がどこかから始められる。ヘテロミノが印刷するのは穴だけ。開いているマスは平均 9.5 個の候補ピースを持って始まり、どの局所ルールもそのどれ 1 つ消せない。下 3 段は合わせて盤の 2.1% / 4.2% を確定させて止まる。
そこに1 段だけ先読みを入れる——ピースを 1 個仮定して、伝播させて、矛盾したら殺す——と 100% / 88.1% になる。ヘテロミノは、いい近似で、ちょうど singleton-consistency 困難だと言っていい。probe の下は何も効かず、probe の上には探索がほとんど要らない。
hetero 段自体は推論としては面白い。まだ正体の分かっていないピースについて推論するからだ。あるマスの生き残り候補が全部同じ形なら、そのマスの持ち主が誰になるにせよ形は確定している。よってそのマスに接している同形のピースは全部すでに死んでいる。ただ、数字の無い盤では、この推論が発火する相手が仮定を置くまでほとんど現れない。
6. ルールの両側を落としてみる
| ルールセット | 一意性を失う盤 | うち解が無くなる盤 |
|---|---|---|
| 何も落とさない | 0 / 72 | 0 |
| 同形禁止ルールを切る（ただのトロミノ敷き詰め） | 72 / 72 | 0 |
| 回転を同一視する（LITS 流） | 72 / 72 | 72 |
同形禁止ルールは敷き詰めパズルに乗った飾りではなく、全盤で骨組みだった。
面白いのは逆側だ。ルールをきつくする——L の回転を同じ形とみなす、LITS が採っている規約——と、盤は「より制約されてより一意になる」のではない。解が無くなる。72 盤すべてで、意図された答えそのものが違法になるからだ。
7. 期待して外した測定を 2 つ
棒はほとんど冷遇されていなかった。 棒は長い平らな辺を 1 本持っていて、長い平らな辺は双子とぶつかる機会が多い。だからルールは棒を罰するはずだと思っていた。
| I— | I| | L┌ | L┐ | L└ | L┘ | 棒の割合 | |
|---|---|---|---|---|---|---|---|
| 出荷盤の答え | 16.1% | 15.5% | 16.5% | 16.5% | 17.7% | 17.7% | 31.6% |
| 空の 6×6 の全分割 | 14.9% | 14.9% | 17.5% | 17.5% | 17.5% | 17.5% | 29.9% |
| 空の 2×12 の全分割 | 0% | 0% | 25% | 25% | 25% | 25% | 0% |
重みなしなら 33.3%。実測は 31.6% / 29.9%。2〜3 ポイントしかない。null result としてそのまま書いておく。
例外は「効果が統計的ですらない」1 箇所で、空の 2×12 では棒は 0%——上で見たとおり 2 行の帯は棒を使えない。幾何が十分きついところではルールは棒を完全に排除し、そうでないところではほとんど何もしていない。
手掛かりはどれも効いている。効きすぎている。 出荷盤の黒マスを 1 個、ランダムな空きマスへ動かす（手掛かりの個数は変えない）。
| 盤 | 試した手数 | まだちょうど 1 解 | 解が無くなった |
|---|---|---|---|
| 8×8 | 1,440 | 6.2% | 30.8% |
| 12×12 | 3,888 | 3.4% | 41.0% |
ほとんどの手がパズルを壊し、しかも壊し方の主流は「曖昧になる」ではなく「解が無くなる」。全数え上げで見た非対称性を、うまくいっている盤の内側から見ているのと同じことだ。
8. 2 本目のエンジンが捕まえたバグ
エンジンは 2 本あって 1 行も共有しない。1 本目はマスを変数にしてドメイン（そのマスを覆いうるトロミノ）を持ち、4 段を不動点まで伝播させる。2 本目はドメインを作らない——格子を走査して、最初の未被覆マスに対して、それを覆いうるピースを全部試し、既に置いたピースと直接照合する。
探索は「このマスを誰が持つか」で分岐する。これは解空間を分割するので、部分木は互いに素になり、枝の間で候補を除外する必要は無い。ところが最初の版は、試し終わった候補を親の状態から除外して再伝播していた。いかにも気の利いた最適化に見える。
これが壊れる。除外して伝播した結果、後続の候補が同じマスに確定してしまうことがある。すると、その候補の番が来たときに commit は「そのマスはもう持ち主がいる」と判断して false を返し、その枝が黙って飛ばされる。エラーは出ない。ただ答えが減る。
伝播器は空の 3×4 の分割を 5 通りと報告した。スキャナは 14 通りと報告した。
伝播器を単体で眺めても、おかしいところは何も無い。1 行も共有しない 2 本目のエンジンがそう言ったから分かった。
テストには「伝播器が持ち主を確定させたマスは、スキャナが見つけるすべての解で同じ持ち主でなければならない」という健全性プロパティが入っている。
実装
TypeScript + Vite、ランタイム依存ゼロ。ソルバーは素の配列。
src/heteromino.ts ルール、候補生成、4 段、エンジン 1
src/brute.ts エンジン 2（1 行も共有しない）
src/generate.ts 黒マスを歩かせる生成器
src/ledger.json 白紙盤の分割数（npm run ledger）
src/stats.json この記事の全数値（npm run stats）
tools/notes.mts stats.json からデモページの解説を生成
ページに出ている数値は全部 tools/notes.mts が src/stats.json から生成している。手で書き写した数字は 1 つも無い。測定を回し直せば文章のほうが追従する。全 39 テスト。
ソルバー内蔵パズル第 56 弾。