Solving Tapa: when the clue is a pattern, not a number, enumeration stops collapsing

Tapa in the browser with three rule sets inside. Shade cells to
build one connected wall that never fills a 2×2 block. A clue lists the
run lengths of shaded cells in the ring of eight around it — so the
clue is not a function of how many neighbours are shaded, it is a
function of where they are. On a full ring there are 23 distinct
clues but only 9 possible totals. In the previous puzzle of this
series, enumeration provably collapsed into interval arithmetic.
Tapa is the mirror image, and the same 900-position property test
settles it: the count relaxation saw more in 0 positions, the
enumeration table saw more in 585. Puzzle #24 in the solver-included
series.

🌐 Live demo: https://sen.ltd/portfolio/tapa/
📦 GitHub: https://github.com/sen-ltd/tapa

The rules

Three of them.

1. Shade cells to build a wall that is connected orthogonally.
2. No 2×2 block is fully shaded.
3. A clue cell is never shaded. Its numbers are the lengths of the runs of shaded cells in the ring of eight around it, read cyclically, in any order.

Rule 3 is the whole story. A 3 means "one block of three in a row". A
1 1 1 means "three separate single cells". Both shade three cells.
They are still different clues.

At the edge of the board the ring is clipped: off-grid neighbours count as
permanently unshaded, so the cycle becomes an arc. Other clue cells in the
ring are permanently unshaded too.

Turning the clue into a table

The obvious implementation enumerates the ring. It is eight bits, so there
are 256 patterns, full stop.

export function runsOfMask(mask: number): Clue {
  if (mask === 0) return [0];
  if (mask === 255) return [8];
  const runs: number[] = [];
  for (let i = 0; i < 8; i++) {
    // start of a run: set, with its cyclic predecessor clear
    if ((mask >> i) & 1 && !((mask >> ((i + 7) % 8)) & 1)) {
      let len = 0, j = i;
      while ((mask >> j) & 1) { len++; j = (j + 1) % 8; }
      runs.push(len);
    }
  }
  return runs.sort((a, b) => b - a);
}

Group all 256 masks by the clue they induce and you get 23 classes.
Group them by how many bits are set and you get 9. The clue partition
is a strict refinement of the count partition — and you can price the
difference exactly:

clue	table	count relaxation	ratio
4	8	70	11%
2 2	12	70	17%
3 1	24	70	34%
1 1 1 1	2	70	3%
summed over all 23 clues	256	984	26%

1 1 1 1 is the extreme case: four singletons around an eight-cycle leaves
exactly the two checkerboard rings. A solver that only knows the total
thinks there are seventy.

The mirror image of the previous puzzle

The previous entry in this series was
Thermometers, and it ended in a
small theorem:

Per-line witness enumeration — list every way a line can meet its
clue, keep what they all agree on — provably collapses into plain
interval arithmetic. A mercury level moves in unit steps, so its domain
never grows holes, and enumeration reaches exactly the interval
fixpoint. 900 positions, zero disagreements.

Tapa turns that upside down. A ring clue's satisfying set is an arbitrary
subset of {0,1}^8, holes and all. There is no "in between" for the two
patterns of 1 1 1 1. Enumeration cannot collapse, because there is nothing
convex for it to collapse into.

The nice part is that the same apparatus transfers: run 900 random
reachable positions through both rule sets and compare how many cells each
one settles.

the count relaxation saw a cell the table missed ......   0 / 900   (subsumed)
the table saw a cell the relaxation missed ........... 585 / 900   (65%)
average advantage over all 900 positions ............. +5.7 cells

The 0 is not luck, it is a proof. Every mask in a clue's table has the
same popcount. So whenever the count rule can fire at all — the ring is
saturated one way or the other — every surviving mask already agrees on the
remaining cells, and the table fires too. count ⊑ rings, always. The
test pins it; the 585 measures how strictly.

	enumeration vs the relaxation
Thermometers (scalar water level)	900 positions, zero disagreements
Tapa (eight-bit ring)	585 of 900 go to enumeration

The dividing line is not what the puzzle looks like. It is whether the
variable's domain can grow holes.

The three rule sets

All three carry the same two global rules:

• no 2×2 — three shaded corners force a dot in the fourth
• connectivity — a pocket no shaded cell can reach gets dotted, and a cell whose removal would cut the wall in two gets shaded

The cut-cell test is a flood fill per candidate cell: 64 fills over 64 cells
on an 8×8 board, which costs nothing in practice.

Count relaxation (propagateCount) — knows only the total. Shipped as
the falsified rival, exactly the role enumeration played last time.

Ring tables (propagateRings) — generalised arc consistency on one
clue. Keep the masks still compatible with the board, fix every cell they
agree on:

for (const con of cons) {
  let anySet = 0, allSet = 255, live = 0;
  for (const m of con.masks) {
    if (!compatible(m, con, state)) continue;
    live++; anySet |= m; allSet &= m;
  }
  if (live === 0) return false;        // this clue is dead
  // a bit every surviving mask sets  → shaded
  // a bit no surviving mask sets     → dot
}

Probing (propagateProbe) — singleton consistency. Assume a cell
shaded, run the ring rule set to fixpoint, erase the value if the board
dies. Iterated to its own fixpoint.

How far each one reaches on unique boards generated with no solvability
filter at all — otherwise "probing finishes everything" would be circular:

size	count relaxation	ring tables	probing
4×4	14%	65%	100%
5×5	7%	54%	100%
6×6	2%	31%	100%
7×7	2%	25%	100%
8×8	0%	12%	100%

Probing finished every one of the 860 unique boards sampled. The
difficulty knob is the size: at 4×4 two thirds of boards fall to the tables
alone, at 8×8 one in eight.

Generating: clue everything, then carve

Generating Tapa the direct way is awkward — both the positions and the
values of the clues are free. So:

1. Grow one connected blob that never fills a 2×2 (the solution comes first).
2. Put a clue on every unshaded cell.
3. Remove clues one at a time in random order, keeping each removal for as long as the board stays unique.

Step 3 tests uniqueness with a table-backed search capped at two solutions.
The result is a near-minimal clue set: 10.8 clues and 53 free cells on an
8×8 board. Rejections run at 0.03 per accepted board, and they come from
blobs that are not unique even when fully clued — not from unsolvable ones.

size	ms/board
5×5	1.8
7×7	12.6
9×9	110.6

Soundness: four counters that must agree

Series standard. An independent brute force over every subset of the free
cells — it shares no code with the propagators, re-deriving each clue
from the shading, rescanning for 2×2 blocks and flooding the wall — plus
propagation-backed search under each of the three rule sets. Four counts,
one answer. The hand-made fixtures are:

• a unique board
• an unsatisfiable board that dies locally (three singletons will not fit a five-cell arc, so the table contradicts immediately)
• an unsatisfiable board that dies globally (the ring rule set survives it; probing kills it)
• a board that needs probing to finish

A disagreement means someone dropped or invented a solution, which is how an
unsound rule gets caught. 77 tests.

Takeaways

• A Tapa clue is a pattern, not a number: 23 clues over 9 totals, so the clue partition strictly refines the count partition.
• count ⊑ rings is provable (all masks in a clue share a popcount), and the 0-of-900 half of the property test is that proof, measured.
• The other half is 585 of 900, +5.7 cells. The same experiment that found zero disagreements in Thermometers finds disagreement in two thirds of positions here.
• What changed is not the genre. It is whether the domain grows holes: a scalar level flattens enumeration, an eight-bit ring needs it.
• The machine strength is probing: 12% for tables at 8×8 versus 860/860.

Which puzzle next?

---

SEN LLC — software development & technical consulting
🌐 https://sen.ltd