Heteromino: when the clues are holes, local reasoning dies completely

Heteromino in the browser with a four-rung solver. This puzzle has no
numbers. No arrows, no region boundaries, no circles. The only thing a setter
can hand you is which cells are black — the clue language is a subset of
cells. Two things fell out of that. First, a black cell does two jobs at
once: it removes a cell from the tiling, and it stands between pieces so
that same-shaped neighbours become legal. 65 of the 72 shipped boards depend on
the second job. Second, and more interesting: if nothing is written on the
board then there is nothing to propagate from. The bottom three rungs
settle 2.1% of an untouched 8×8 and then stop. One level of lookahead takes
it to 100%. Puzzle #56 in the solver series.

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

Rules

1. Cut every white cell of the board into trominoes — three-cell pieces, so either a straight bar or an L.
2. Two pieces of the same shape may not share an edge.
3. "Shape" means shape as drawn. Rotate an L a quarter turn and it counts as a different piece, so there are six shapes (2 bars + 4 Ls).

That is all of it. There is not a single number anywhere.

Rule 3 — distinguishing rotations — is the hinge. Later I compare it against the
LITS convention, which merges rotations. Spoiler: merging them leaves all 72
shipped boards with no answer at all.

For the first time in this series, the clue is not a written thing

Numberlink prints numbers. Sashigane prints circles and arrows. Heyawake prints
regions and numbers. Every puzzle in this series has a setter who writes
something on the board. Heteromino's setter writes nothing. They delete
cells.

What makes that more than a subset-picking exercise is that one black cell does
two jobs, and you cannot buy one without the other:

1. The hole job. That cell drops out of the tiling.
2. The wall job. Pieces on opposite sides of it do not share an edge, so two pieces of the same shape become legal there.

Job 2, measured. I walked the answers to all 72 shipped boards and counted pairs
of same-shaped pieces facing each other across a single black cell:

Take that one black cell away and those two pieces are touching twins, in
violation. The wall job is not decoration.

1. The blank board — one-row strips are almost all dead

With no clues at all: how many ways does an empty h×w grid fall into
heterominoes? Exhaustively counted. Rectangles whose cell count is not divisible
by three are disqualified before we start, marked ·.

* is a lower bound — the count hit its node budget. Everything else is
exact, and the small entries are recomputed from scratch on every test run.

The first row is the whole rule in miniature. A 1×n strip has no tiling for any
n except 3. In a single row the only piece that fits is the horizontal bar, and
two horizontal bars in one row always share an edge. So a strip holds one piece
and never two.

Which also means 1×3 is the only board in this puzzle that is a legal puzzle
with zero clues: exactly one answer, nothing printed on it.

None of 3×n, 4×n, 5×n or 6×n returns anything from OEIS.

2. Two rows, and the answer is a power of two

The second row is not a mess either.

tilings of a blank 2 × 3m strip = 2^m

Matched through m = 9 (2×27 = 512). But the count is the least interesting part
of that claim — numeric agreement can be coincidence, so the test suite checks
the structure behind it instead. That is the bottom two rows: across every one of
those tilings, no bar is ever used and no piece ever crosses a three-column
boundary.

So a two-row strip is not a strip. It is a row of independent 2×3 blocks, each
cuttable by two Ls in two ways, and 2^m is just the product.

The argument is short enough to do by hand. Put a bar in the top row of the
leftmost three columns. The cell directly beneath it still needs a piece. Every L
that could take that cell wants a top-row cell, and the bar already has them all.
The only thing left is the bar directly underneath — same shape, touching, and so
illegal. No bar can start at the left edge, and the same trap propagates
rightwards.

This is the rule doing it, not the shape inventory: switch the same-shape rule off
and a blank 2×6 has more than four tilings again, bars included. That check is in
the test suite too.

3. Clue space is thin — and small enough to enumerate

Because a clue set is nothing but a subset of cells, "how good is this as a clue
language" is a question you can answer by brute force. For small boards I
walked every black-cell set of every legal size and counted the answers each
one admits.

(An excerpt; the complete table is on the demo page.)

Two things read off it.

Unique boards are rare everywhere. The best cell in the entire census is a 3×4
with 3 clues, and even there only 42.7% of clue sets work.

And the failure mode flips. With few black cells, boards fail by having too
many answers. With many, they fail by having none — because the black cells have
chopped the grid into regions whose sizes are not multiples of three. Uniqueness
lives in a narrow band between "hasn't said enough" and "has said something
impossible", and the band narrows as the board grows.

Since the census is exhaustive, the minimum clue count is an exact bound, not a
search result:

Smallest by count is 4×5 with 2 — a twenty-cell board pinned by two black
cells. Smallest by density is 6×6 at 8.3%. (4×4 and 5×5 need 4 only because
their cell counts are 1 mod 3, so the legal clue counts are 1, 4, 7, … and 1 is
not enough.)

4. A setter cannot scatter clues

Scale up and sample, and the band closes fast. Random black-cell placements, with
the peak unique rate over all legal clue counts:

On 12×12: 17 legal clue counts × 300 draws = 5,100 boards, and not one of them
had exactly one answer.

So the generator does not sample. And here is where generating this puzzle
diverges from every other one in the series.

The other generators all have the same shape: draw an answer, read the clues
off it, then erase clues one at a time while the board stays unique. Heteromino
permits none of that.

• The clues are not a function of the answer. Blacking a cell in or out changes which cells even need covering.
• The number of white cells must stay a multiple of three, so black cells cannot be added or removed one at a time at all.

There is no legal single-step edit that removes a clue, so a minimisation phase
cannot be written. What is left is: scatter k black cells, count the answers,
and walk the black cells around the board one move at a time.

There was one implementation trap here. Scoring naively by solution count
cannot move. As the census shows, in the interesting density band most random
placements have no answer rather than too many, so most of the search space is a
flat plateau of "zero solutions". I gave unsolvable boards a secondary gradient —
how many open regions have a size that is not a multiple of three. That is a
necessary condition for solvability and never a sufficient one, but it is a
usable slope out of the impossible region.

What the search reaches inside a fixed budget:

That is a bound on the search, not on the puzzle. The exhaustive table above
is the one that says what exists.

5. The main result — the ladder is flat, then falls off a cliff

Branch points needed to prove the shipped boards unique, summed per rung:

That is a strange-looking ladder. region — "an open region has a multiple of
three cells", which sounds like it should carry the puzzle — takes 7.1% off fit
at 8×8 and 24.2% at 12×12. hetero, the rung that encodes the puzzle's own
rule, takes off another 0.2% and 0.8%. Then probe takes 8×8 to 0 and
12×12 to 39. Almost flat, then a cliff.

Asking what each rung can prove from an untouched board makes the reason
plain (this is exactly what the checkbox on the demo page displays):

There is nothing to propagate from. Every other puzzle in this series prints
something — a number, an arrow, a region edge — that pins a cell or two locally
and gives the fixpoint computation somewhere to start. Heteromino prints holes.
Each open cell begins with 9.5 candidate pieces on average and no local rule
eliminates a single one of them. The bottom three rungs between them settle 2.1%
and 4.2% of the board and stop.

Add one level of lookahead — assume a piece, propagate, kill it if that
contradicts — and it goes to 100% and 88.1%. Heteromino is, to a good
approximation, exactly singleton-consistency-hard: nothing below probe works,
and probe needs almost no search on top of it.

The hetero rung is still the interesting inference, because it reasons about a
piece it has not identified yet: if every surviving candidate for some cell has
the same shape, then whoever ends up owning that cell has that shape, whichever
one it turns out to be — so every piece of that shape touching that cell is
already dead. It just turns out that on a board with no numbers, that inference
has almost nothing to fire on until a guess has been made.

6. Dropping each half of the rule

The same-shape rule is not a garnish on a packing puzzle; it is structural for
every board.

The other direction is the interesting one. Tightening the rule — merging
rotations, as LITS does — does not make boards more constrained and more unique.
It makes them unsolvable, all 72 of them, because the intended answer itself
stops being legal.

7. Two things I expected and did not get

Bars are barely suppressed. A bar has one long flat side, and a long flat side
is a lot of edge on which to run into a twin, so the rule ought to punish it.

An unweighted shape set would give 33.3%. Measured: 31.6% and 29.9%. Two or
three points. Recorded as a null result rather than quietly dropped.

The exception is the one place the effect is not statistical at all: in a blank
2×12, bars are 0% — the two-row strip cannot use one, as shown above. Where
the geometry is tight enough the rule excludes bars outright; where it is not, it
barely leans on them.

Every clue is load-bearing — more than I wanted. Move a single black cell on a
shipped board to a random empty cell, leaving the clue count untouched:

Almost every move destroys the puzzle, and the dominant failure is not "ambiguous"
but "unsolvable" — the same asymmetry the exhaustive census shows, seen from
inside a board that works.

8. The bug the second engine caught

There are two engines and they share no code. The first makes each cell a variable
whose domain is the trominoes that could still cover it, and propagates the four
rungs to a fixpoint. The second builds no domain at all: it walks the grid and, at
the first uncovered cell, tries every piece that would cover it, checking legality
directly against the pieces already down.

The search branches on "which piece owns this cell". That partitions the answer
space, so the subtrees are disjoint and nothing needs excluding between them.
The first version excluded each tried candidate from the parent state anyway and
re-propagated — it looks like a tidy optimisation.

It breaks. After excluding a candidate and propagating, propagation can commit a
later candidate to that same cell. Then when that candidate's own branch comes
up, commit finds the cell already owned, returns false, and the branch is
skipped in silence. No error. Just fewer answers.

The propagator reported 5 tilings of a blank 3×4. The scanner reported 14.

Nothing about the propagator looked wrong on its own. It took a second engine
sharing no code with it to say so.

The test suite carries a soundness property for this: any cell the propagator
assigns an owner to must have that same owner in every answer the scanner
finds.

Implementation

TypeScript + Vite, no runtime dependencies, plain arrays in the solver.

src/heteromino.ts    rules, candidate generation, the four rungs, engine 1
src/brute.ts         engine 2 — shares no code
src/generate.ts      the clue-walking generator
src/ledger.json      blank-board tiling counts  (npm run ledger)
src/stats.json       every figure in this article (npm run stats)
tools/notes.mts      generates the demo page's notes from stats.json

Every number on the demo page is generated by tools/notes.mts out of
src/stats.json, so not one figure there is transcribed by hand — re-run the
measurements and the prose follows them. 39 tests.

Puzzle #56 in the solver series.