Stitches: the puzzle is a matching, and Hall's theorem is dead if you apply it one level too low

I built Stitches in the browser with a five-rung solver, and the interesting part was not the solver. It was discovering that the most sophisticated-looking rule in it — Hall's condition on a bipartite matching — does provably nothing when you attach it to the object the rulebook points at, and becomes the rule that decides a quarter of the shipped boards when you attach it one level up.

Play it · Source

The rules

The grid is cut into blocks.

• Every pair of blocks that touch must be sewn together with exactly one stitch
• A stitch is a short thread joining two orthogonally adjacent cells in different blocks
• Each end of a thread punches a hole, and no cell takes more than one hole
• The numbers down the right and along the bottom count the holes in that row and column

That is the whole game. (There are 2÷ variants demanding two stitches per pair; more on those at the end.)

Not shading, not a loop — a matching

Almost every grid puzzle is either "shade some cells" or "draw a loop". Stitches is neither, and the right way to see it is as a graph problem.

The candidate stitches are exactly the adjacencies that cross a block border — the edges of a graph whose vertices are cells. "No cell takes two holes" is then a degree ≤ 1 constraint on that edge set, which is the definition of a matching. And because the grid is bipartite under the checkerboard colouring — every orthogonal adjacency joins a black cell to a white one — it is a bipartite matching.

export interface Edge {
  a: number;      // the upper/left cell
  b: number;      // the lower/right cell
  pair: number;   // id of the block pair this stitch would sew
  horiz: boolean;
}

So an answer is: a bipartite matching satisfying three systems of cardinality constraints — one per block pair, one per row, one per column. Reading it that way hands you several facts the rulebook never states.

(1) A block with d neighbours holds exactly d holes

Every stitch a block R sends to a neighbour spends one of R's own cells, and no cell can be spent twice. So a block with d neighbours holds

exactly k·d holes.

Exactly, not at most. That word is the whole point. The per-pair rule only says how many stitches cross each border; the margins only say how many holes sit on each line. Nothing in the rules ever adds the stitches up per block.

Read as an inequality, it becomes a screen that runs on the block map before any answer exists at all:

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;
}

It looks like a formality. It is doing most of the generator's work.

grid	blocks	maps cut	pass the screen	mean touching pairs	of those, have an answer
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%)

Two thirds of random cuts are provably answerless, and one multiplication finds them. A further 20–30% of the survivors have no answer for reasons the screen cannot see.

(2) Hall's theorem, applied one level too low, does nothing

This is the part I got wrong first, and the failure is clean enough to be worth walking through.

My first hall rung applied Hall's condition per block pair. A pair still owes k stitches; it has a set of candidate edges; compute a maximum matching among them; if the maximum is smaller than what is owed, contradiction; if the matching is tight, then any candidate that no maximum matching uses is out, and any candidate every maximum matching uses is in. Textbook, and completely reasonable.

On a k = 1 board it never fires once. Not rarely — never, and provably:

• A pair owing one stitch is satisfied by any single candidate, so the maximum matching is 1 whenever a candidate exists. No contradiction is ever detectable.
• An edge e is forced in only if dropping it leaves a maximum below 1, i.e. only if e was the sole candidate — which the cheap pair rung already handles.
• An edge e is forced out only if taking it leaves the rest unable to finish, and 1 + 0 ≥ 1, so that never happens either.

I wrote a test that hunts for a board where the matching rung decides a gap the counting rungs leave open, gave it 4,000 random maps, and got zero hits. The rung was dead weight.

The fix was to lift the same idea one level up the hierarchy: not the block pair, the block.

A block R owes k stitches to each of its neighbours. Each of those spends one of R's cells, and — this is what makes it bite — a cell can only serve a neighbour it physically touches. So this is an assignment problem:

• left: the cells of R that are still available
• right: one slot per stitch R still owes, labelled by which neighbour it owes it to
• an edge when that cell touches that neighbour

Now several neighbours compete for the same cells, the matching can be tight, and Hall's condition has teeth.

The implementation builds one maximum matching saturating the slots, then runs an alternating-path BFS from the unmatched cells. Any cell the BFS cannot reach is in every valid assignment, so it is pierced — even though which neighbour it ends up serving is still unknown:

// Every slot is served. A cell that no alternating path can free is in
// every assignment, so it is pierced.
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);

The same test now passes, and 9 of the 36 shipped boards cannot be finished without search unless this rung is present.

The lesson generalises past this puzzle: "use Hall's theorem" is not the decision. Which bipartite graph you point it at is the decision, and the obvious one can be provably vacuous.

(3) The 2 × 2 that no number can see

Label a 2 × 2 square of cells a b over c d. Suppose all four gaps between them cross block borders. Then the square can be sewn two ways — {ab, cd} or {ac, bd} — and crucially, both pierce the same four cells.

No row margin can tell them apart. No column margin can either. The only clue with a chance is the per-pair count, and it works exactly when the four cells lie in four different blocks: then the turn shuffles stitches between four distinct pairs and the counts notice.

Which means: if either diagonal of the square is monochromatic, every single clue survives the quarter turn. With a and d both in block P, {ab, cd} uses pairs (P,B) and (C,P); {ac, bd} uses (P,C) and (B,P). Same multiset. The board has a twin, and nothing you write in the margins can break the tie.

There are two flavours, and they could not behave more differently.

The checkerboard flavour cannot exist

a, d in block P and b, c in block Q. This never happens. P needs an orthogonally connected path joining a to d; Q needs one joining b to c; the two paths are disjoint; and in the plane they would have to cross.

That is an argument, not a measurement, so I measured it. For every 2 × 2 position of every grid up to 5 × 5, enumerate every way of splitting the remaining cells between the two blocks, and check whether any split leaves both connected:

grid	2 × 2 positions tested	splits enumerated each	realisable checkerboards
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

Zero. Planarity is doing the puzzle a favour.

The three-block flavour is real, and always fatal

a, d share a block, while b and c sit in two different blocks. Now there is no second diagonal pair to cross, so the block holding the diagonal simply routes around the outside:

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

Block 0 reaches its own diagonal the long way round, and blocks 1 and 2 are singletons that need not connect to anything.

These are rare:

grid	maps cut	turnable squares	per 1,000 maps	maps with ≥ 1	checkerboards
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

Rare, but unsurvivable. Of 91 sampled answers that lit all four cells of a turnable square, 91 had a second answer under full margins. So the generator discards the answer the moment one lights up, which is far cheaper than finding out in the uniqueness test — and much easier than debugging "why does this generator occasionally emit a non-unique board".

Weighing the three clue systems

A Stitches board carries three counting systems at once: per block pair, per row, per column. The first is free — written in the block map rather than in any number — which invites the suspicion that the margins are decoration.

So: take a random block map, sew a random answer, read the margins off it, and count how many answers each system admits on its own (capped at 500).

grid	boards	block map only	unique	margins only	unique	both	unique
8 × 8	400	≥ 500 median	0 (0.0%)	2 median	132 (33.0%)	1 median	258 (64.5%)
10 × 10	400	≥ 500 median	0 (0.0%)	6 median	36 (9.0%)	2 median	182 (45.5%)
12 × 12	400	≥ 500 median	0 (0.0%)	40 median	7 (1.8%)	2 median	138 (34.5%)

The block map alone has never once pinned the answer — 0 of 400 at every size. The margins are not decoration. And since even both together only get to 34.5% on 12 × 12, generation has to be a rejection loop rather than a construction.

(One caveat the table needs: "margins only" still uses the block map to decide which gaps are candidates, because without borders there is no such thing as a stitch. What it drops is the per-pair count and the per-block equality.)

Two margins are free, and the rest is a dial

Every stitch punches two holes, so the total number of holes on a finished board is 2k × the number of touching pairs — a number the block map fixes before a single margin is read.

So the row margins have a known sum, and so do the column margins. Erase one from each axis and nothing is lost: what it said was the remainder. That puts a hard ceiling of w + h − 2 on how many margins a board can usefully carry.

Measured rather than assumed — drop the last row margin and the last column margin from a full-margin board and count answers again:

• 8 × 8: unchanged on 120 / 120 boards
• 10 × 10: unchanged on 120 / 120 boards
• 12 × 12: unchanged on 120 / 120 boards

Below the ceiling it is a dial, and a steep one:

margins kept	8 × 8 unique	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%

Greedy minimisation beats random subsets by a lot: a median of 6 kept margins on 8 × 8 (ceiling 14), 8 on 10 × 10 (ceiling 18), 12 on 12 × 12 (ceiling 22). The shipped boards are spread along this dial deliberately — the easy ones keep enough for the line rung to finish them, the hard ones keep as few as uniqueness allows.

The ladder, priced

rung	what it knows
pair	two blocks that touch take exactly k stitches between them
block	a block with d neighbours holds exactly k·d holes
line	the same counting argument down a row or a column
hall	a block's cells against the neighbours it owes (above)
probe	assume a stitch, and keep the contradiction

grid · rung	boards	finished with no search	decides something new	gaps decided (median)	nodes (median)
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

A ≥ 400,000 figure is a board that hit the search cap, so it is a floor.

Being honest about the third column: block adds something as a rung on only 1 board in 12. Its real work happens earlier, as the screen that throws away two thirds of the cuts before a board exists. The line → hall step is where the ladder earns its keep.

Two implementation notes that mattered

Give cells a verdict, not just gaps. My first solver tracked a tri-state per gap only. But when a human solves Stitches, they constantly hold the thought "this cell gets a hole, I just don't know which way the thread runs yet". Adding a separate cellState made the two counting rungs several times stronger, because they can now record that conclusion instead of throwing it away:

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

One detail: cells in the interior of a block, touching no border at all, must be initialised to C_EMPTY. Otherwise the counting rungs keep treating them as candidates that could still be pierced, and the arithmetic silently goes wrong.

"No cell takes two holes" is not a rung. Mixing it in with the deduction rules means every rung has to remember it. Enforcing it inside setEdge — the moment a stitch goes in, every other candidate at both its ends goes out — makes it an invariant that every rung above can simply assume. The search reuses one board and rewinds with a trail, so the only real care needed is that the trail restores the cell verdicts too, not just the edge array.

What happens as k goes up

The degree equality also predicts what 2÷ boards do. k·d ≤ |R| scales with k while the cells do not, so doubling k on the same cut is usually fatal. Swept on a 12 × 12 grid:

blocks	k=1 pass	k=2 pass	k=3 pass	k=1 answers	k=2 answers	k=3 answers
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	—

If you want a higher k, you must cut fewer, fatter blocks. Ask for k = 2 on a 12 × 12 cut into 8 blocks and only 11 of the 223 maps that pass the screen have an answer at all. That is why this build ships k = 1 only.

Takeaways

• Stitches is a bipartite matching with three cardinality systems laid over it, and reading it that way is what produces every result above.
• A rule none of the three systems states — a block's hole count equals its neighbour count — turns out to be the strongest screen in the generator.
• Hall's theorem can be provably vacuous at the wrong level of the hierarchy and decisive one level up. Picking the graph is the real design work.
• There is a 2 × 2 configuration no clue can ever see, and the worst version of it is forbidden by planarity — verified by exhaustive enumeration, not just argued.

Everything numeric here is emitted by npm run stats, and the README and the page prose are written out of src/stats.json by npm run notes. No number on this page was typed in by hand.

Play it · Source