Tatamibari: three of the four rules are an exact-cover matrix, and the fourth is the one that matters

Tatamibari in the browser with five rule sets inside. Cut the grid
into rectangles so that every rectangle holds exactly one clue, and the clue
says what shape it is: + a square, - wider than tall, | taller than
wide. And one more rule, which belongs to no rectangle in particular:
no four rectangles may meet at a point. Puzzle #31 in the solver series.

Demo: https://sen.ltd/portfolio/tatamibari/
Repo: https://github.com/sen-ltd/tatamibari

I picked this puzzle because the first three rules are exact cover written
out verbatim — a rare thing, and a good excuse to write dancing links. What I
did not expect was how much of the puzzle turned out to live in the one rule
that would not go in the matrix.

Three findings:

• The fourth rule cannot be a column, and it is the rule that makes the answer unique. Switch it off on 10×10 boards that have exactly one solution, and only 17% of them still do. One went to 1953.
• Incremental reach and ablation gave me opposite verdicts on the same rule. One propagator looks like the second-biggest contributor climbing the ladder and is worth literally zero removed from the top.
• The rule that does not fit does not help the search either. It costs 5–20% more nodes, because it has no column, so the column-choice heuristic cannot see it.

Three rules are a matrix

"Every cell belongs to exactly one rectangle" plus "every clue gets exactly one
rectangle, of the shape it asks for" is exact
cover with nothing left over. One
column per cell, one row per candidate rectangle, hand it to Algorithm X.

The pleasant surprise is what you don't need. My first sketch had n²
columns for the cells plus one column per clue, to force one rectangle per
clue. That second block is redundant. A candidate rectangle only exists if it
contains exactly one clue — a rectangle swallowing two clues is not a legal
piece — so the column for that clue's own cell already forces exactly one
rectangle per clue. The matrix is n² columns wide and that is all of it.

Generating the candidates is the whole model:

for (let r0 = 0; r0 <= cr; r0++) {
  for (let r1 = cr; r1 < n; r1++) {
    const h = r1 - r0 + 1;
    for (let c0 = 0; c0 <= cc; c0++) {
      for (let c1 = cc; c1 < n; c1++) {
        const w = c1 - c0 + 1;
        if (cl.type === '+' && w !== h) continue;
        if (cl.type === '-' && w <= h) continue;
        if (cl.type === '|' && h <= w) continue;
        if (clueCount(r0, c0, r1, c1) !== 1) continue;   // ← the load-bearing filter
        ...

clueCount is a 2-D prefix sum, so "how many clues does this rectangle
contain" is four array reads. It matters: a centre cell on a 10×10 board sits
inside 900 rectangles, and almost every large one swallows a second clue.

The fourth rule is not a column

No four rectangles may meet at a point.

This is not a statement about a cell being covered once. It is a statement
about a lattice point being cornered at most three times. Exact cover
speaks "exactly one" (primary columns) and, with Knuth's secondary columns,
"at most one". There is no way to write "at most three".

So it rides along the search as an incremental counter. Every rectangle knows
which interior lattice points it corners at, and when dancing links offers a
row, those counters get bumped:

for (let i = D[best]; i !== best; i = D[i]) {
  const a = ROW[i];
  // The one rule that is not a column.
  let bad = false;
  if (useCorners) {
    const cs = cands[a].corners;
    let t = 0;
    for (; t < cs.length; t++) {
      if (++cornerCount[cs[t].p] === 4) { bad = true; t++; break; }
    }
    if (bad) for (let u = 0; u < t; u++) cornerCount[cs[u].p]--;
  }
  if (!bad) { /* ...cover, recurse, uncover... */ }
}

Everything else in the function is textbook Algorithm X. The one rule I could
not express is fifteen lines bolted to the side of it.

Getting the corner predicate right is fiddly enough that I gave it its own
tests. A lattice point (lr, lc) has four cells around it, and a rectangle
owning the north-west one corners there only if it stops exactly at lr-1,
lc-1:

export function cornersAt(rect: Rect, lr: number, lc: number, q: number): boolean {
  switch (q) {
    case 0: return rect.r1 === lr - 1 && rect.c1 === lc - 1;  // NW cell
    case 1: return rect.r1 === lr - 1 && rect.c0 === lc;      // NE cell
    case 2: return rect.r0 === lr     && rect.c1 === lc - 1;  // SW cell
    default: return rect.r0 === lr    && rect.c0 === lc;      // SE cell
  }
}

There is a small lemma hiding in there that the propagator leans on: no
single rectangle can corner at two quadrants of the same point. NW wants
c1 = lc-1, NE wants c0 = lc, and c0 > c1 is not a rectangle. So "all four
cells corner here" really does imply "four distinct rectangles", which is what
lets the propagator work in terms of cornering rather than in terms of
identity. There is a randomised test asserting exactly this over 500 rectangles
× 25 points, because I did not want to find out later that I had been assuming
it.

And it is the rule that makes the answer unique

Here is the measurement I did not see coming. Take boards with exactly one
solution under all four rules. Switch off the one rule that would not fit in
the matrix. Count again. 60 freshly generated boards per size:

board	boards	still unique	solutions without it: median	mean	max
6×6	60	31 (52%)	1	2.2	15
8×8	60	24 (40%)	2	3.2	16
10×10	60	10 (17%)	5.5	66.4	1953

At 10×10, five out of six well-posed puzzles stop being puzzles. The matrix on
its own hands you a median of five and a half answers, and one board in the
sample had 1953.

The trend is the point. On 6×6 the corner rule is close to decorative — you
could nearly drop it and still ship. By 10×10 it is carrying the puzzle. The
part of the problem that fits the framework beautifully is not the part that
makes the problem well-posed, and the gap widens with size.

Most tilings are dead before a clue is written

The same rule does the same work one level up, on the generator. Draw random
rectangle tilings — no clues, nothing solved — and just ask how many are legal.
4000 draws per row, maxSide capping how long a piece may get:

board	maxSide	rectangles (mean)	four rectangles meet	survivors
6×6	2	18.8	100%	0%
6×6	4	10.7	60%	40%
6×6	6	7.6	29%	71%
8×8	2	32.7	100%	0%
8×8	4	17.9	84%	16%
8×8	6	13.4	60%	40%
10×10	2	50.5	100%	0%
10×10	3	34.8	100%	0%
10×10	4	27.3	95%	5%
10×10	6	19.8	76%	24%

Cap the pieces at 2×2 and not one tiling in four thousand survives, at any
board size. That is not a near miss, it is structural: a fine tiling by small
rectangles is made of points where four pieces meet. You need long pieces to
get away with it, which is exactly why real Tatamibari boards look the way they
do.

Useful going up, worthless coming down

The solver has five rule sets, each adding one propagator: shape (a clue with
one rectangle left is placed), cover (a cell only one clue can reach must be
inside that clue's rectangle), disjoint (a rectangle overlapping every
remaining rectangle of some other clue cannot be chosen), corners, probe.

Climbing the ladder, on 60 unique boards per size — share of surplus
candidates eliminated / share of boards finished outright:

board	shape	cover	disjoint	corners	probe
6×6	5% / 0%	76% / 28%	88% / 48%	99% / 97%	100% / 100%
8×8	3% / 0%	67% / 12%	87% / 32%	98% / 87%	100% / 100%
10×10	4% / 0%	54% / 2%	81% / 12%	96% / 82%	100% / 100%

disjoint looks indispensable. It takes 10×10 from 54% to 81% of candidates
cut and from 2% to 12% of boards finished — the biggest jump on the board
except for corners. I was pleased with it. It is the one rule in there I had
to think about.

Now drop one propagator from the full set instead. Same 60 boards, same
code:

dropped	6×6 cut / done	8×8 cut / done	10×10 cut / done
nothing	100% / 60	100% / 60	100% / 60
shape	100% / 60	100% / 60	100% / 60
cover	72% / 1	70% / 0	69% / 0
disjoint	100% / 60	100% / 60	100% / 60
corners	93% / 31	96% / 24	93% / 10
probe	99% / 58	98% / 52	96% / 49

disjoint is worth exactly nothing. Not "a percentage point" — zero, at
every size, on both measures. So is shape. Anything they can prove, cover
and corners prove anyway.

Two tables, same boards, same code, opposite verdicts. They are answering
different questions:

• Incremental reach asks "what can this rule do that the weaker ones cannot?"
• Ablation asks "what can this rule do that the stronger ones cannot?"

A rule sitting in the middle of a ladder answers the first question loudly and
the second one not at all. And the natural way to build a hint ladder — switch
propagators on one at a time and watch the numbers climb — measures only the
first. I would have shipped disjoint as a headline result on the strength of
that first table alone, and it would have been a headline about a rule that does
nothing.

This is the second time in this series I have gone looking for what a rule is
worth and got a different answer depending on where I stood. Last time
(Ripple Effect)
it was the solver-vs-generator split: a rule worth almost nothing to the solver
was deciding which boards existed at all. This time it is inside the solver:
the same rule, on the same boards, measured two defensible ways, comes out
essential and worthless. A propagator does not have "a" contribution. It has a
contribution relative to a set, and if you only ever report one set you are
reporting a preference, not a measurement.

They stay in the codebase, by the way — a hint ladder needs rungs a player can
reason with, and "that rectangle blocks that clue entirely" is an explanation,
not just an elimination. But they are not there to make the solver stronger,
because they don't.

corners is the only rule here load-bearing in both directions. Drop it and
10×10 goes from 60 boards finished to 10.

The rule that does not fit does not help the search either

The corner check cannot inform Knuth's column-choice heuristic. It has no
column, so it has no size, so S cannot see it. All it can do is reject a row
after the matrix has already offered one. DLX nodes to the first solution,
summed over the shipped bank:

board	boards	nodes with the check	nodes without	ratio
6×6	16	291	238	1.22×
8×8	16	291	277	1.05×
10×10	16	746	626	1.19×

5–20% more nodes. Which is the honest shape of the whole thing: the rule that
makes these puzzles well-posed is the rule the machinery cannot help with, and
it pays for its own enforcement.

I am not sure there is a fix, only a trade. You could encode "at most three of
these four" with auxiliary rows and secondary columns, at which point the
heuristic can see it — and you have added (n-1)² structures to a matrix
that was n² columns of pure signal. I did not try it. The counter is fifteen
lines and it is correct.

Where the clue sits inside its rectangle

There is no "prune the redundant givens" step in this generator, which is
unusual for the series. The clue count is fixed the moment the tiling is drawn
— one per rectangle. The only free variable left is where inside its rectangle
each clue sits.

That turns out to matter enormously, and for a reason specific to this puzzle:
a rectangle that would swallow a second clue is not a candidate at all. Move
one dot and the candidate sets of every clue near it change. Fix a tiling,
redraw only the clue positions, 16 layouts each:

board	tilings	unique layouts	tilings with ≥1 unique layout
6×6	120	27%	64%
8×8	120	5%	15%
10×10	60	0%	0%

At 10×10 not one of 960 randomly placed layouts was unique. The generator still
finds them — 5247 layouts over 10127 tilings for sixteen boards — but roughly
one draw in three hundred lands.

One more small thing, from the same run. Mean candidate rectangles kept per
clue:

| board | + (square) | - (wide) | \| (tall) |
|---|---|---|---|
| 6×6 | 2.3 | 5.6 | 5.4 |
| 8×8 | 3.7 | 12.8 | 11.2 |
| 10×10 | 3.7 | 15.3 | 12.3 |

A + pins both dimensions at once; - and | only put them in order. Same
symbol size, four times the information — and + barely grows with the board
(2.3 → 3.7) while - triples, because a square anchored at a cell has O(n)
shapes and an oblong has O(n²).

Cross-checking

Every shipped board is counted by two solvers that enumerate the problem in
opposite directions, and they have to agree:

• dancing links over the cell columns, choosing the column with the fewest live rows;
• an anchored brute force, keyed on the observation that the first uncovered cell in row-major order is necessarily the top-left corner of whichever rectangle owns it. Branching factor is "candidates anchored exactly here", and the enumeration order shares nothing with the matrix.

A third counter runs the rule sets to a fixpoint and branches on the clue with
the fewest survivors. The tests check all three agree, with the corner rule on
and off — the "off" case matters, because a corner-rule bug that only fires
when the rule is on would otherwise hide behind agreement.

And validate re-reads all four rules from scratch against a proposed tiling,
sharing no code with the model or any solver: it builds its own cell→rectangle
owner map and reads the corner rule straight off it. That is the one that would
catch a subtly wrong cornersAt.

One test failure was worth the trip. I had asserted that on an unsolvable board
the propagators either report a contradiction or leave the board unfinished.
They report the contradiction — and isSolved still returned true, because a
fixpoint that aborts half-way leaves an array where every clue happens to have
one candidate left. The contract was fine (every caller already guards on ok);
my assertion was not. It is now a documented precondition rather than a thing
you find out about.

36 tests. TypeScript, no runtime dependencies.

---

Repo: https://github.com/sen-ltd/tatamibari
Demo: https://sen.ltd/portfolio/tatamibari/