ステッチ — このパズルはマッチングで、ホールの定理を置く場所を間違えると何も起きない

ステッチ（Stitches） を 5 段のソルバー内蔵でブラウザに実装した。盤はブロックに分割され、隣り合うブロックの組すべてをちょうど 1 本のステッチ——境界をまたぐ隣接 2 マスを結ぶ糸——で縫う。糸の両端が穴で、1 マスに穴は 2 つ置けない。右と下の数字はその行・列の穴の数。この「1 マス 1 穴」がこのパズルをマッチングにする。候補辺は境界をまたぐ隣接対、市松に塗れば二部グラフ、つまり答えは二部マッチングで、ホールの定理がソルバーの道具になる。ここから規則書に無い事実が 3 つ出た。(1) 次数等式：隣接 d 個のブロックはちょうど k·d 個の穴を持つ（「高々」ではない）。k·d ≤ |R| として読むと答えが存在する前に走るスクリーンになり、8×8 を 8 ブロックに無作為に切ると通るのは 35.6%（20,000 枚中 7,111 枚）だけ。(2) マッチング段はブロック対ではなくブロックに置く：1 ステッチ盤ではブロック対に対するホール条件は証明可能に無力で、ブロック側に上げて初めて効き、出荷 36 盤中 9 盤はこの段が無いと探索なしで終わらない。(3) 2×2 の回転：4 辺すべてが境界をまたぐ 2×2 は同じ 4 マスを穴にしたまま四半回転でき、行・列の数字はどちらも区別できない。同ブロック対角が市松になる型は平面性で存在し得ず、5×5 までの全 2×2 位置で残りマスの分割を全列挙（5×5 は 1 位置 2,097,152 通り）して 0 通りを確認した。もう一方の型は実在し、8×8 地図 1,000 枚あたり 3.3 個と稀だが致命的で、点灯した 91 件は 91 件とも複数解だった。手掛かりの重みも測った：ブロック地図だけで一意になった盤は各サイズ 400 枚中 0 枚、数字だけなら 8×8 で 132 枚、両方でようやく 258 枚。逆に穴の総数はブロック地図が先に決めるので行と列の余白 1 つずつは常に冗長で、360 盤すべてで確認した。出荷 36 盤、テスト 55 件。ソルバー内蔵パズル第 70 弾。

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

ルール

盤はいくつかのブロックに切り分けられている。

• 隣り合う（辺を共有する）ブロックの組すべてを、ちょうど 1 本のステッチで縫う
• ステッチは、別々のブロックに属する隣接 2 マスを結ぶ短い糸
• 糸の両端が穴になる。1 マスに穴は 1 つまで
• 右端と下端の数字は、その行・列にある穴の個数

それだけだ。2÷ 版なら 1 本でなく 2 本、というバリエーションもある（記事の最後で触れる）。

塗るのでも輪を引くのでもなく、マッチングを組む

グリッドパズルの大半は「マスを塗る」か「輪を引く」かのどちらかだ。ステッチはどちらでもない。

候補になるステッチは、ブロック境界をまたぐ隣接マス対——つまりグラフの辺だ。そして「1 マスに穴は 1 つまで」は、その辺集合に対する次数 ≤ 1 の制約、すなわちマッチングそのものになる。さらにグリッドを市松に塗ると、隣接する 2 マスは必ず異色なので、このグラフは二部グラフである。

export interface Edge {
  a: number;      // 上／左のマス
  b: number;      // 下／右のマス
  pair: number;   // このステッチが縫うブロック対の id
  horiz: boolean;
}

答えは「二部グラフのマッチングであって、ブロック対ごと・行ごと・列ごとの本数指定を満たすもの」になる。こう読み替えた瞬間、規則書に書かれていない事実がいくつか落ちてくる。

(1) 隣接ブロックが d 個なら、穴はちょうど d 個

ブロック R が隣人に送るステッチは、どれも R 自身のマスを 1 つ消費する。そして同じマスを 2 回使うことはできない。したがって隣人が d 個あるブロックは、

ちょうど k·d 個の穴を持つ。

「高々」ではなく「ちょうど」だ。ここが効く。ブロック対ごとの本数指定は「この境界を何本またぐか」しか言わないし、行・列の数字は「この直線上に穴が何個あるか」しか言わない。ブロック単位でステッチを足し上げる規則は、どこにも書かれていない。

不等式として読むと、答えが 1 つも存在しない段階で、ブロック地図だけを見て走るスクリーンになる。

export function degreeScreenOk(p: Puzzle): boolean {
  for (let R = 0; R < p.regionCount; R++)
    if (p.k * p.regionDegree[R] > p.regionCells[R].length) return false;
  return 2 * p.k * p.pairCount <= p.w * p.h;
}

形式的な条件に見えて、実際には生成器の大半の仕事をここで終わらせている。

格子	ブロック数	切った地図	スクリーン通過	接触対の平均	そのうち答えを持つ
8 × 8	8	20,000	7,111 (35.6%)	13.2	432 / 551 (78.4%)
10 × 10	10	20,000	7,241 (36.2%)	17.8	396 / 551 (71.9%)
12 × 12	12	20,000	7,844 (39.2%)	22.5	396 / 585 (67.7%)

無作為に切った地図の 3 分の 2 は、答えが存在しないことが掛け算ひとつで分かる。残ったものからさらに 2〜3 割が落ちる。

(2) ホールの定理を置く場所

ここが今回いちばん面白かったところだ。

最初に書いた hall 段は、ブロック対ごとのマッチングだった。ある対が残り k 本のステッチを負っていて、候補辺の集合がある。その候補辺で大きさ k のマッチングが組めなければ矛盾。組めるがどの最大マッチングにも必ず入る辺があれば、その辺は確定。まっとうに見える。

そして k = 1 の盤では、この段は一度も何も確定しない。しかも偶然ではなく、証明できる。

• 対が 1 本を負っているとき、候補が 1 つでもあれば最大マッチングは 1。だから矛盾検出は起きない
• 辺 e が必須になるのは「e を除くと最大マッチングが 1 未満」つまり e が唯一の候補のときだけ。それは pair 段がすでにやっている
• 辺 e が排除されるのは「e を取ると残りで足りない」ときだが、1 + 0 ≥ 1 なので起きない

テストを書いて「line 段が open のまま残した辺を hall 段が確定する盤」を 4,000 枚探させたら、0 件だった。段として死んでいた。

直し方は、同じ発想をひとつ上の階層に持ち上げることだった。ブロック対ではなく、ブロックに置く。

ブロック R が負っているのは「隣人ごとに k 本」だ。それぞれの 1 本が R のマスを 1 つ消費し、しかもそのマスが実際に接している隣人にしか使えない。つまりこれは、

• 左側：R のまだ空いているマス
• 右側：R が負っている「隣人 × 残り本数」のスロット
• 辺：そのマスがその隣人に接している

という割り当て問題であり、ここで初めてホールの条件に歯が立つ。複数の隣人が同じマスを奪い合うからだ。

実装は、スロットを飽和させる最大マッチングを 1 回組み、そのあと未マッチのマスから交互路を BFS して「どの割り当てでも外せないマス」を拾う。

// すべてのスロットが埋まった。交互路で解放できないマスは、
// どの割り当てにも入っている ＝ 穴である。どの隣人に使われるかは未定でよい。
const free = new Uint8Array(cells.length);
const queue: number[] = [];
for (let ci = 0; ci < cells.length; ci++)
  if (matchOfCell[ci] === -1) { free[ci] = 1; queue.push(ci); }
while (queue.length) {
  const ci = queue.pop() as number;
  for (const s of cellSlots[ci]) {
    const other = matchOfSlot[s];
    if (other >= 0 && !free[other]) { free[other] = 1; queue.push(other); }
  }
}
for (let ci = 0; ci < cells.length; ci++)
  if (!free[ci] && b.cellState[cells[ci]] === C_UNKNOWN)
    setCell(b, cells[ci], C_HOLE);

同じテストが今度は通り、出荷している 36 盤のうち 9 盤は、この段が無いと探索抜きでは終わらない。

「ホールの定理を使う」だけでは足りず、どの二部グラフに使うかで生きるか死ぬかが決まる、という話だった。

(3) どの数字にも見えない 2×2

2×2 のマスを a b / c d と置く。4 つの隙間がすべてブロック境界をまたぐなら、この 2×2 の縫い方は 2 通りある——{ab, cd} と {ac, bd} だ。

そしてこの 2 通りは、同じ 4 マスに穴を開ける。行の数字も列の数字も、まったく区別できない。

区別できる可能性があるのは、対ごとの本数だけだ。そしてそれが効くのは、4 マスが4 つの別々のブロックに入っているときだけ。回転すると 4 つの異なる対の間でステッチが動くので、本数が崩れる。

逆に言えば、2×2 のどちらかの対角が同じブロックなら、すべての手掛かりが回転を生き延びる。a と d が同じブロック P なら、{ab, cd} は対 (P,B) と (C,P) を、{ac, bd} は対 (P,C) と (B,P) を使う。多重集合として同一だ。盤に双子ができる。

同ブロック対角の型は 2 つある。

市松型は存在できない

a, d が P、b, c が Q の場合。これは起こらない。P は a と d を結ぶ連結経路を、Q は b と c を結ぶ連結経路を、互いに交わらずに持たなければならない。平面ではこの 2 本は交差せざるを得ない。

これは主張なので、測った。5×5 までの各格子の全 2×2 位置について、残りのマスを 2 つのブロックに分けるすべての分け方を列挙し、両方が連結になるものがあるかを調べた。

格子	調べた 2×2 位置	1 位置あたりの分割	実現した市松
3 × 3	8	32	0
4 × 3	12	256	0
4 × 4	18	4,096	0
5 × 4	24	65,536	0
5 × 5	32	2,097,152	0

0 通り。平面性の議論は正しかった。

3 ブロック型は実在して、必ず殺す

a, d が同じブロック P、b と c は別々の 2 ブロック、という場合。今度は交差する相手がいないので、P は外側を回り込んで自分の対角に届ける。たとえばこうなる（P = 0）。

0 0 0 0
0 0 1 0
0 2 0 0
0 0 0 0

これは実在する。ただし稀だ。

格子	切った地図	回転可能な 2×2	1,000 枚あたり	1 個以上持つ地図	市松
8 × 8	20,000	66	3.3	65	0
10 × 10	20,000	102	5.1	102	0
12 × 12	20,000	146	7.3	145	0

稀だが、当たったときは容赦がない。回転可能な 2×2 の 4 マスすべてに穴が開いた答えを 91 件サンプルしたところ、91 件すべてが満点の手掛かりでも複数解だった。

だから生成器は、一意性テストに入る前にここで捨てる。安いスクリーンが 1 つ増えるだけの話だが、これを知らずに書くと「なぜかたまに一意にならない盤」を延々と踏むことになる。

3 つの手掛かり体系の重み

ステッチ盤には数え上げの体系が 3 つ同時に載っている。ブロック対ごとの本数、行ごとの穴数、列ごとの穴数。1 つ目は数字ではなくブロック地図に書かれているので、「右と下の数字は飾りでは？」という疑いが湧く。

無作為なブロック地図に無作為な答えを縫い、そこから数字を読み取ってから、各体系が単独で何解を許すかを数えた（上限 500 解で打ち切り）。

格子	盤	ブロック地図のみ	一意	数字のみ	一意	両方	一意
8 × 8	400	≥ 500 (中央値)	0 (0.0%)	2	132 (33.0%)	1	258 (64.5%)
10 × 10	400	≥ 500	0 (0.0%)	6	36 (9.0%)	2	182 (45.5%)
12 × 12	400	≥ 500	0 (0.0%)	40	7 (1.8%)	2	138 (34.5%)

ブロック地図だけで答えが決まったことは一度も無い（各サイズ 400 枚中 0 枚）。数字は飾りではない。そして両方揃えても 12×12 で 34.5% しか一意にならないので、生成は構成ではなく棄却ループになる。

（注：「数字のみ」も、どの隙間が候補になるかを決めるのにブロック地図は使っている。境界が無ければステッチという概念自体が無いからだ。外したのは対ごとの本数とブロックの等式。）

余白は 2 つタダで消せる

ステッチ 1 本につき穴は 2 つ。したがって完成盤の穴の総数は 2k × 接触している対の数 で、これは数字を 1 つも読む前にブロック地図が決めている。

ということは行の数字の総和は既知で、列も同じだ。各軸から 1 つ消しても情報は失われない。消した数字は「残りの引き算」でしかない。

上限は w + h − 2 になる。これも測った。満点手掛かりの盤から最後の行の数字と最後の列の数字を消して、解の個数が変わるかを見る。

• 8 × 8：120 / 120 盤で不変
• 10 × 10：120 / 120 盤で不変
• 12 × 12：120 / 120 盤で不変

その下はダイヤルで、しかも急だ。

残した余白	8 × 8 一意率	10 × 10	12 × 12
6	0.0%	0.0%	0.0%
8	16.7%	1.7%	0.0%
10	47.5%	3.3%	0.0%
12	86.7%	22.5%	0.8%
14	95.8%	43.3%	7.5%
16	100.0%	74.2%	23.3%
18	—	98.3%	40.8%
20	—	100.0%	73.3%
22	—	—	100.0%

無作為な部分集合ではなく貪欲に最小化すると、上限よりずっと下まで落ちる：8×8 で中央値 6（上限 14）、10×10 で 8（上限 18）、12×12 で 12（上限 22）。出荷盤はこのダイヤル上に意図的に散らしてある。

梯子

安い順に 5 段。

段	知っていること
pair	接している 2 ブロックの間はちょうど k 本
block	隣人が d 個のブロックはちょうど k·d 個の穴を持つ
line	行と列について、同じ数え上げ
hall	ブロックのマス対負っている隣人の割り当て（上述）
probe	1 本仮定して、安い段に矛盾を出させる

格子・段	盤	探索なしで完走	下の段より何か決めた盤	決まった隙間（中央値）	ノード（中央値）
8×8 pair	12	0	12	26.7%	5,487
8×8 block	12	0	1	26.7%	5,487
8×8 line	12	6	11	93.2%	2
8×8 hall	12	9	3	100.0%	1
8×8 probe	12	12	3	100.0%	1
12×12 pair	12	0	12	20.6%	≥ 400,000
12×12 block	12	0	1	21.0%	≥ 400,000
12×12 line	12	6	11	87.3%	2
12×12 hall	12	9	3	100.0%	1
12×12 probe	12	12	3	100.0%	1

≥ 400,000 は探索ノード上限に当たった盤で、総数ではなく下限だ。

正直に書くと、block 段が段として追加で何か決めるのは 12 盤中 1 盤しかない。この規則の本当の仕事は段ではなくスクリーンの側にあって、盤が存在する前に切り方の 3 分の 2 を捨てている。逆に line から hall への差は大きく、hall を外すと 9 盤が探索を必要とするようになる。

実装で効いた 2 つのこと

マスにも状態を持たせる。 最初は辺（隙間）だけ 3 値で持っていた。だが人間がステッチを解くとき、「このマスには穴が開く。ただし糸がどっちに伸びるかはまだ分からない」という状態を常に使っている。そこで cellState（未定／穴／穴なし）を辺とは別に持たせたところ、block と line の 2 段の威力が数倍になった。数え上げの段が「穴である」と言えるようになるからだ。

export const C_UNKNOWN = 0;
export const C_HOLE = 1;
export const C_EMPTY = 2;

ブロックの内側にあって境界に一切触れないマスは、初期化時に C_EMPTY にしておく。そうしないと数え上げの段が「まだ穴になれる候補」と誤って数える。

「1 マス 1 穴」は段ではない。 これを規則の 1 つとして段に混ぜると、あらゆる段がそれを気にしなければならなくなる。setEdge の中で、ステッチを 1 本入れた瞬間に両端の他の候補をすべて落とす、という不変条件にしてしまえば、上のどの段もそれを前提にできる。探索は 1 枚の盤を使い回してトレイルで巻き戻すので、この不変条件が壊れないことが唯一の注意点になる。

k を上げると何が起きるか

2÷ 版（対ごとに 2 本）は、次数等式がそのまま効く。k·d ≤ |R| は k に比例して厳しくなるのに、マスは増えないからだ。12×12 で測った。

ブロック数	k=1 通過	k=2 通過	k=3 通過	k=1 答えあり	k=2 答えあり	k=3 答えあり
4	98.7%	92.7%	84.2%	588/589	460/571	250/521
6	93.3%	70.4%	44.6%	535/551	158/427	13/259
8	81.9%	35.6%	9.7%	437/476	11/223	0/52
10	59.4%	9.6%	0.2%	302/373	0/50	—
12	40.4%	0.8%	0.0%	158/231	0/7	—

k を上げたければブロックを減らして太らせるしかない。12×12 を 8 ブロックに切って k=2 を要求すると、スクリーンを通った 223 枚のうち答えを持つのは 11 枚だけだ。今回出荷しているのは k=1 のみで、これが理由。

まとめ

ステッチは、塗るでも輪でもないマッチングのパズルだった。そう読み替えると、

• 規則書に無い等式（ブロックの穴数 = 隣人の数）が出て、それが最強のスクリーンになる
• ホールの定理は、置く階層を間違えると証明可能に無力になる。ブロック対では死に、ブロックでは生きる
• どの数字にも見えない 2×2 が存在し、その片方の型は平面性が禁じてくれる（全列挙で確認）

すべての数値は npm run stats が出力し、README とページの本文は npm run notes が src/stats.json から書き起こしている。手で転記した数字は 1 つも無い。

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