Stitches

The block map is a clue, and on its own it says almost nothing

A Stitches board carries three counting systems at once: one stitch between every pair of blocks that touch, a hole budget per row, and a hole budget per column. The first of those is free — it is written in the block map, not in any number — which invites the suspicion that the margins are decoration. They are not, and the measurement is one-sided enough to be worth stating plainly.

Take a random block map, sew a random answer on it, read the margins off that answer, and then ask how many answers each clue system admits on its own. The block map alone never once pinned the answer: 0 of 400 boards at every size tried, with a median of ≥ 500 answers on an 8 × 8 grid. The margins alone do better but still leave most boards open. Only together do they land on one answer, and even then only about 35% of the time on the biggest grid here — which is why generating a Stitches board is a rejection loop and not a construction.

A caveat the table needs: "margins only" still uses the block map to decide which gaps are candidates at all, because without borders there is no such thing as a stitch. What it drops is the per-pair count and the per-block equality. The counts in the table are capped at 500 answers; a capped cell is a floor, not a total.

A block with d neighbours holds exactly d holes

Read the puzzle as a matching and a rule falls out that none of the three counting systems states. Every stitch a block sends to a neighbour spends one of the block's own cells, and no cell is spent twice, so a block touching d neighbours holds exactly k·d holes. Not at most: exactly. The per-pair rule knows how many stitches cross each border and the margins know how many holes sit in each line, but neither of them ever adds the stitches up per block.

Stated as an inequality — k·d ≤ |R|, a block needs at least as many cells as it has neighbours — it is a screen that runs on the block map alone, before any answer exists. It is not a formality. Cutting an 8 × 8 grid into 8 connected blocks at random, only 35.6% of the cuts survive it, and of the survivors a further slice has no answer for reasons the screen cannot see.

As a solver rung it earns its place differently: it is the rung that first says this cell is pierced without yet saying which way the thread runs, and that verdict is what the row and column counts then consume.

The one 2 × 2 square no clue can see, and why half of it cannot exist

Label a 2 × 2 square of cells a b over c d. If all four gaps between them cross a block border, the two ways of sewing the square — {ab, cd} and {ac, bd} — pierce the same four cells. No row margin and no column margin can tell them apart. The only clue left that might is the per-pair count, and it separates them exactly when all four cells lie in four different blocks. When some diagonal of the square is monochromatic, the turn moves the two stitches between the same two block pairs, every count survives, and the board has a twin.

There are two ways for a diagonal to be monochromatic, and they behave completely differently. The first is the checkerboard: a and d in one block, b and c in another. It cannot happen. Both blocks would need an orthogonally connected path joining their own diagonal pair, the two paths would have to cross, and in the plane they cannot. That is an argument, so it is checked rather than asserted: for every 2 × 2 position of every grid up to 5 × 5, every way of splitting the remaining cells between the two blocks was enumerated, and no split ever left both connected.

The second way is real. Let a and d share a block while b and c sit in two different blocks, and the block holding the diagonal simply routes around the outside. The turn still moves one stitch between each of the same two pairs, so nothing notices. These squares are rare — about 3.3 per thousand 8 × 8 maps — but they are not survivable: of 91 sampled answers that lit one up, 91 had a second answer under full margins. The generator therefore throws an answer away the moment it lights one, which is cheaper than discovering it in the uniqueness test.

What each rung costs, and what it saves

The ladder is five rungs, cheapest first. pair counts the stitches owed across each block border. block is the degree equality above. line is the same counting argument down a row or a column. hall is the assignment: a block's cells against the neighbours it owes, settled by a maximum matching and an alternating-path sweep for the cells no assignment can avoid. probe assumes a stitch and lets the cheap rungs find the contradiction.

Put the per-pair version of the matching rung in hall's place and it does nothing whatever on a one-stitch board — a pair owing a single stitch is satisfied by any one of its candidates, so its matching is never tight and no candidate is ever forced. Moving the same idea up to the block, where several neighbours compete for the same cells, is what gives it teeth. Of the 36 shipped boards, 9 need it and cannot be finished without it.

Two rungs never finish a board alone at any size, and that is not a defect: pair and block read only the block map, and the block map on its own has never pinned an answer in any sample here. Their honest column is the fourth one — how many boards the rung decides something on that the rung below it could not. block's real work is done earlier anyway, as the screen that throws away two thirds of the cuts before a board exists at all.

"decided" is the share of gaps settled with no search; "nodes" is the search still needed afterwards to prove the answer is the only one, and a node figure written ≥ 400,000 is a board that hit the search cap, so it is a floor rather than a total.

Two of the 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 times the number of block pairs that touch — a number the block map fixes before a single margin is read. The row margins therefore have a known sum, and so do the column margins. Erase one margin from each axis and nothing is lost: what it said is whatever is left over.

That makes w + h - 2 a hard ceiling on how many margins a board can usefully carry, and it is checked rather than assumed. Dropping the last row margin and the last column margin from a full-margin board left the answer count unchanged on 120/120, 120/120, 120/120 boards — every one.

Below the ceiling it is a dial, and a steep one. Keeping a random subset of the margins, uniqueness climbs from hopeless to near-certain across a handful of margins; and greedy minimisation of a full board settles far lower than the ceiling, at a median of 6 on 8 × 8, 8 on 10 × 10, 12 on 12 × 12. The shipped boards are spread along this dial on purpose: the easy ones keep enough margins for the line rung to finish them, the hard ones keep as few as uniqueness allows.

Two-stitch boards need fat blocks

The degree equality also says what happens when a board asks for two stitches between every pair of neighbours instead of one. The requirement k·d ≤ |R| scales with k while the cells do not, so doubling k on the same cut is usually fatal; the way to buy it back is to cut fewer, larger blocks. The table sweeps a 12 × 12 grid.