Shakashaka: the rule is about whole regions, and it is exactly a rule about one lattice point

Shakashaka in the browser with five rule sets inside. Drop black
triangles into the white cells — each fills half a cell, right angle in one
of the four corners — so that every piece of white left over is a
rectangle, upright or turned 45°. A number on a black cell says how many of
the four cells around it hold a triangle. Puzzle #32 in the solver series.

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

I picked this one because its main rule is stated in the worst possible shape
for a solver. "Every white region is a rectangle" is a sentence about connected
components: you cannot ask it anything until the last cell is filled, and once
you finally can, answering it costs a flood fill. Every other puzzle in this
series hands you something local to propagate. This one hands you a region.

Except it does not, quite. The rule turns out to be exactly equivalent to a
condition on the white angle at a single lattice point — eight bits and a table
lookup, no regions anywhere — and that changes what a solver can be.

Three findings:

• The global rule is local, and provably so. Every maximal run of white 45° sectors around a lattice point must be 90°, 180° or 360°. I checked that against a flood-fill oracle on 12.5 million configurations, including every picture on every 3×3 board. Zero disagreements.
• The obvious local rule is wrong in both directions at once. "The white angle at a point is a multiple of 90°" accepts 13 958 pictures on an empty 4×4 board where only 23 are legal — while rejecting 21 of those 23.
• Adding a redundant propagator moved another propagator's ablation score by 27 points. Same rule, same boards, same metric. A propagator does not have a contribution; it has a contribution relative to a set.

The rule that will not propagate

Here is the whole puzzle. Cells are black (given, sometimes numbered) or white.
In a white cell you may place one black right triangle filling half the cell,
right angle in one of the four corners, or leave the cell alone. So each white
cell has five states.

export const E = 0;    // no triangle: white to the edges
export const TNW = 1;  // right angle at the NW corner
export const TNE = 2;
export const TSE = 3;
export const TSW = 4;

And then: the white area left over must be a disjoint set of rectangles,
upright or turned 45°.

A search wants to hear no as early as possible. This rule says nothing at all
until every cell is decided, at which point a flood fill tells you whether the
last five hours were wasted. That is a leaf test, and a leaf-only search over
84 white cells has 5^84 ≈ 10^59 states to walk.

Eight bits around a point

Stand on a lattice point — a corner of the grid, not a cell. Four cells meet
there. Each one contributes a white angle of 0°, 45° or 90°, and nothing else
about the board is visible from where you are standing.

Chop the full turn into eight 45° sectors, numbered clockwise from north:

sectors 0,1 → the cell NE of the point      2,3 → SE
        4,5 → SW                            6,7 → NW

Each cell state fills two of those bits. A black or off-board cell fills none.
An empty white cell fills both of its quadrant's bits. A triangle fills both if
its right angle is in the far corner, none if it is in the near corner, and one
of the two otherwise:

export const PAT: number[][] = [
  // q0: the cell NE of the point; the point is that cell's SW corner.
  //     E     TNW   TNE   TSE   TSW
  [0b11, 0b10, 0b11, 0b01, 0b00],
  [0b11, 0b00, 0b10, 0b11, 0b01],  // q1: SE
  [0b11, 0b01, 0b00, 0b10, 0b11],  // q2: SW
  [0b11, 0b11, 0b01, 0b00, 0b10],  // q3: NW
];

Now the claim. Take the maximal unbroken cyclic runs of white sectors around
the point. Then:

The white area is a disjoint set of rectangles ⟺ every run is 2, 4 or 8
sectors long.

90°, 180° or 360°. A corner, a straight edge, or the inside of something.

Why that is enough: every vertex of the white boundary sits on a lattice point
(triangle hypotenuses go corner to corner), so the boundary of a white region
is a polygon with lattice-point corners. A run of 4 is a straight point, a run
of 8 is an interior point, and a run of 2 is a corner turning 90°. Rule out
everything else and a region's boundary is a simple polygon whose every corner
turns 90° in the same direction — which has exactly four corners, because the
turns must sum to 360°. Four corners, all right angles: a rectangle. And the
edges are cell sides or cell diagonals, so consecutive perpendicular edges are
either both axis-aligned or both diagonal. Upright or 45°, nothing in between.

Runs of 6 are the reflex corners that make an L an L. Odd runs are 45° wedges —
the tip of a lone triangle. Both are exactly what the rule forbids, and there
is no third failure to rule out.

So the entire rule is a 256-entry table:

export const VALID_FULL = table((arcs) => arcs.every((L) => L === 2 || L === 4 || L === 8));

Runs, not the total — and this is where I would have shipped a bug

The version you write first is "the white angle at each point adds up to 0°,
90°, 180° or 360°". One popcount, no arc decomposition, obviously the same
thing.

It is not the same thing, and it is not even a safe approximation. It is wrong
in both directions:

board	legal	naive says legal	legal ones it rejects	illegal ones it accepts
empty 2×2	2	13	0 (0%)	11
empty 3×3	3	1	2 (67%)	0
empty 4×4	23	13958	21 (91%)	13956

On an empty 4×4 there are 23 legal pictures. The naive rule accepts 13 958 of
them and agrees with reality on two.

Both failures come from one fact: two rectangles may touch at a single
point. Two white 1×1 squares on a diagonal, with black cells on the other
diagonal, is the most ordinary picture in the puzzle. At the shared corner that
is 180° of white — but split into two separate right angles. Sum the angle and
you cannot tell it from a straight edge, so:

• 45° + 45° in opposite quadrants sums to 90° and gets accepted, though it is two illegal wedges;
• 180° + 90° as two separate runs sums to 270° and gets rejected, though it is a perfectly legal edge next to a perfectly legal corner.

The temptation is to file this under "edge case". It is not. Counting the
lattice points of the answers shipped with the demo:

board	lattice points	empty	one corner	one edge	interior	two arcs
6×6	784	10%	38%	16%	11%	25% (on 16/16 boards)
8×8	1296	8%	35%	16%	13%	28% (on 16/16 boards)
10×10	1936	5%	33%	13%	13%	35% (on 16/16 boards)

A third of the lattice points on a 10×10 answer are places where two separate
pieces of white touch at a point. The naive rule is wrong on every board there
is.

How do you test a claim like that?

An equivalence between a global property and a local one is not something a
unit test can assert directly. What you can do is build the other reading —
properly, independently — and run both on everything.

The literal reading needed to avoid every concept the local rule uses: no
angles, no corners, no sectors. Here is what I landed on.

Cut every cell into four quarter triangles with both diagonals. Every legal
half-cell triangle is a union of two of them, so the quarters are the atoms of
the picture:

black corner NW → black quarters N, W      NE → N, E
             SE → S, E                     SW → S, W

Flood fill the white quarters — edge adjacency only, so two regions touching at
a point stay two regions. Then, for each region, the rectangle test is areas:

// A quarter triangle has area 1 in doubled coordinates.
const upright = (Xmax - Xmin) * (Ymax - Ymin);
const tilted = (Umax - Umin) * (Vmax - Vmin);   // = 2 × the tilted box area
if (count !== upright && 2 * count !== tilted) { /* not a rectangle */ }

where U = X + Y and V = X − Y. A region always fits inside its own bounding
box, so if the areas are equal the region is the box — no shape comparison
needed, and it is exact integer arithmetic because doubling the coordinates
puts cell corners on even numbers and cell centres on odd ones. Upright
rectangles are boxes in (x, y); 45° ones are boxes in (x+y, x−y). There is
no third orientation to worry about.

Then run both readings on everything I could afford:

configurations	source	legal ones among them	disagreements
625	every picture on an empty 2×2	2	0
1,953,125	every picture on an empty 3×3	3	0
46,656	every picture on every 2×3 board, black cells and all	46	0
10,077,696	every picture on every 3×3 board, black cells and all	328	0
400,000	random pictures on crowded random 5×5 boards	1	0
75,264	every one- and two-cell edit of every answer in the bank	232	0

That fourth row is 6^9: nine cells, each of them black or one of five states.
Every Shakashaka board of that size, and every picture on it.

The last row is the one that matters, though. Look at the "legal" column on the
random 5×5 sweep: one legal picture in 400 000. Random boards only exercise
the easy side of the claim — both readings say no, loudly, for unrelated
reasons. Boards that are one or two cells away from a real answer are the ones
sitting on the boundary, and 232 of those 75 264 are legal. That is the sweep I
would trust if I had to pick one.

A separate test pins the table itself to the geometry: for all 1296 ways four
cells can meet at a point, step a hair away from the point in the middle of
each of the eight sectors and ask the actual picture — x + y > 1, y > x —
whether that spot is white. If PAT had one bit wrong, everything above would
be a self-consistent verification of the wrong thing.

What it buys

The local rule is a constraint over four cells with five values each, so it is
an arc-consistency propagator. Each cell's domain collapses to at most four
distinct 2-bit patterns, which makes the whole constraint 16 bits in, 16 bits
out, memoised:

const packed = supported(rules.valid, key);
for (let q = 0; q < 4; q++) {
  const next = dom[cells[q]] & STATESET[q][(packed >> (4 * q)) & 15];
  if (next === 0) return false;
  ...
}

Same search, same boards, same answers — the only difference is whether the
rules may look before the leaves:

board	white cells	answers	nodes, propagating	nodes, leaf checks only	ratio
3×3	6	0	0	19,531	19,531×
3×3	8	2	3	488,281	162,760×
4×4	11	1	1	61,035,156	61,035,156×

And on the boards the demo ships, the right-hand column stops being a number
you can print:

board	white cells	nodes to settle it	states without pruning
6×6	30	1 (median)	5^30 ≈ 10^21
8×8	54	1.5 (median)	5^54 ≈ 10^38
10×10	84	1 (median)	5^84 ≈ 10^59

A median of one node. On the shipped boards, arc consistency over the lattice
points settles the entire answer without a single guess.

The per-test speed is the boring half of the win and it is there too — 10.5 µs
for the flood fill against 3.2 µs for the table lookups on the same finished
boards — but three times faster is not the point. Being askable at all, on a
board that is one tenth filled, is the point.

Two ways to score a propagator, and they disagree

The full rule splits into two independent local rules: tips (no odd runs —
no 45° wedges) and reflex (no runs of 6 — no corner bending the wrong way).
Their intersection is the whole thing, which is a nice test to have:

expect(Array.from(intersect(VALID_TIPS, VALID_REFLEX))).toEqual(Array.from(VALID_FULL));

I added a fourth, deliberately: parity — the white angle at a point must be
a whole number of right angles, never mind where the sectors sit. That is one
popcount instead of an arc decomposition, it is implied by tips, and it is
exactly the kind of cheap approximation someone reaches for.

Climbing the ladder — what can this rule do that the weaker ones cannot:

board	rule set	reduction	finished
10×10	(nothing)	0.0%	0%
10×10	clues	5.3%	0%
10×10	clues + parity	24.0%	0%
10×10	clues + parity + tips	74.7%	0%
10×10	clues + parity + tips + reflex	93.8%	27%

Leave one out — what can this rule do that the stronger set cannot:

board	dropped	reduction	finished	vs. full set
10×10	(nothing)	93.8%	27%	—
10×10	clues	68.8%	0%	−25.0% reduction, −27 boards
10×10	parity	93.8%	27%	−0.0% reduction, −0 boards
10×10	tips	32.9%	0%	−60.9% reduction, −27 boards
10×10	reflex	74.7%	0%	−19.1% reduction, −27 boards

Incrementally parity is the second-biggest jump on the ladder — it more than
four-times the reduction over clues alone. By ablation it is worth zero, to
the last decimal, at every board size. That much I expected; it is redundant by
construction, and it is the same shape of result I got out of the previous
puzzle in this series.

What I did not expect was the other direction. Score tips by ablation against
two different sets:

board	set	without tips	drop in reduction
10×10	clues + tips + reflex	6.1%	−87.7%
10×10	clues + parity + tips + reflex	32.9%	−60.9%

Same rule. Same boards. Same metric. The number moved by 27 points because a
different rule — one that is worth nothing on its own showing — was standing
behind it to catch what it dropped. Ablation does not measure a propagator. It
measures a propagator against a particular bench of substitutes, and adding a
redundant rule to the set quietly deflates the ablation score of the rule it
duplicates.

Which is the honest version of a thing I already believed: a propagator has no
contribution of its own. Report both directions or you are stating a
preference.

Who actually makes the answer unique

Take boards with exactly one answer, switch off one rule, count again:

board	boards	clues dropped: still unique	shape rule down to tips: still unique
6×6	60	5 (8%), median 6.5 answers	20 (33%)
8×8	60	0 (0%), median 52.5 answers	4 (7%)
10×10	36	0 (0%), median 335 answers	0 (0%)

Both halves load-bearing, and the shape rule is the bigger one — which is why
these boards carry so few numbers. The generator numbers every black cell from
the answer and then takes numbers away for as long as the answer survives:

board	black cells	numbers kept	share	which digits
6×6	6.0	1.7	28%	0:6% 1:37% 2:40% 3:16% 4:0%
8×8	10.0	3.3	33%	0:9% 1:25% 2:45% 3:16% 4:5%
10×10	16.0	5.5	35%	0:6% 1:29% 2:41% 3:21% 4:2%

Two thirds of the numbers are things the geometry already knew. A 10×10 board
here ships with about five numbers on it and one answer.

Cross-checking

Every count is produced three ways, and the tests fail if they disagree:

1. Propagating search — smallest-domain-first backtracking driven by arc consistency over the lattice points and the clues.
2. The same search with the propagators unplugged — assign cells in row-major order, test the rules only at the leaves. Same answers, up to 61 million times the nodes.
3. Brute force through validate — enumerate every assignment and re-read the rule book from the top: clue arithmetic, then flood fill and bounding boxes. The only pruning it is allowed is counting to four, so the thing under test stays untouched.

The rung labels are checked too, not just believed: for a generated board the
test takes the difficulty label, runs that rung, and asserts the domains it
reaches are the intended answer cell by cell. And a soundness test asserts that
every rung, on every board, keeps every real solution inside its domains —
which is the property that makes a propagator a propagator rather than a guess.

26 tests. TypeScript, no runtime dependencies.

---

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