Heteromino

The clue is a hole, and the hole is also a wall

Heteromino has no numbers. No arrows, no regions, no circles. A setter hands you a grid with some cells blacked out, and that is the entire message — every board in this puzzle is a subset of cells and nothing else. Which makes the clue language unusually easy to describe and unusually awkward to use, because one black cell does two jobs at once. It takes a cell out of the tiling, which is the obvious job. And it stands between pieces, so that two pieces of the same shape which would have been illegal neighbours are legal after all. You cannot spend one job without spending the other.

The second job is not a curiosity. Of the 72 boards shipped here, 65 (90.3%) contain at least one pair of same-shaped pieces sitting on opposite sides of a single black cell — 263 such pairs across 1,968 pieces, a median of 3 per board and 11 at the most. Take that one cell away and those two pieces are touching twins.

The blank board

Before any clue at all: how many ways does an empty grid fall into heterominoes? The cell count has to divide by three, so most rectangles are disqualified before we start (marked ·).

* a lower bound — the count was still running when it hit its node budget. Every other figure is exact, and the small ones are re-derived from scratch on each test run.

The first row is the whole rule in miniature. A 1×n strip has no tiling at all 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 can hold one piece and never two. That also makes the blank 1×3 the only board in this puzzle that is a legal puzzle with no clues whatsoever: one answer, nothing printed.

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

Exactly, at every width measured. The count is the boring part; the structure behind it is checked directly and says more than the arithmetic does. Across every one of those tilings, no bar is ever used and no piece ever crosses a three-column boundary. The strip is not really a strip — it is a row of independent 2×3 blocks, each cuttable by two L's in two ways, and 2^m is just the product. The argument is short enough to check by hand: put a bar in the top row of the leftmost three columns and the cell underneath it still needs a piece; every L that could take that cell wants a top-row cell that is already gone; the only thing left is the bar directly underneath, which is the same shape, touching. So no bar can start at the left edge — and the same trap then propagates rightwards.

It is the rule doing this and not the shape set: 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.

Clue space is thin, and thinnest where it matters

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: walk every black-cell set of every legal size on a small board and count the answers each one admits.

Two things fall out. Unique boards are rare everywhere — the best cell in that table is 3×4 at 3 clues, and even there only 42.7% of clue sets work. And the failure mode flips as clues are added: at low clue counts the boards that fail have too many answers, at high clue counts they have 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.

That also fixes how sparse a board can be. The census is exhaustive, so these are exact minima rather than search results:

A setter cannot scatter clues; they have to search

Scale up by sampling and the band closes fast:

At 6×6 you can find a puzzle by throwing clues at the board. By 12×12 you cannot: across every clue count in the sweep, 0 of 5,100 randomly clued boards had exactly one answer. So the generator here does not sample. It scatters k black cells, counts the answers, and then walks the black cells around the board one move at a time, downhill in answer count. Moving is the only edit available: black cells cannot be added or removed one at a time without breaking the multiple-of-three constraint, which is also why this puzzle has no "erase clues while it stays unique" step of the kind most solvers' generators end with. What the walk reaches inside a fixed budget:

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

Every clue is load-bearing

Take a shipped board and move one black cell to a random empty cell, leaving the clue count untouched:

Almost every move destroys the puzzle, and most destroy it by making it unsolvable rather than ambiguous — the same asymmetry the exhaustive census shows, seen this time from inside a board that works.

What each half of the rule is worth

The same-shape rule is not a garnish on a packing puzzle; it is load-bearing for essentially every board. Tightening it the other way is just as destructive. Count a rotated L as the same shape — the convention LITS uses — and boards do not become more constrained and more unique; they become unsolvable, because the intended answer itself stops being legal.

Which trominoes actually get used

I expected bars to be 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. It barely does: bars are 31.6% of the pieces in the shipped answers against the 33.3% an unweighted shape set would give, and 29.9% across every tiling of a blank 6×6. 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.0% of pieces — the two-row strip cannot use one, as above. Where the geometry is tight enough the rule excludes bars outright; where it is not, it hardly leans on them.

A pleasant consequence of the rule, visible on the board above: colouring each piece by its shape is automatically a proper colouring of the piece-adjacency graph, because same-coloured pieces are exactly the ones forbidden from touching. Six colours, guaranteed to suffice, for free.

What the ladder costs

Branch points needed to prove the shipped boards unique, at each rung, summed over the set. For scale, a board carries 170.7 candidate pieces on average at 8×8 and 377.1 candidate pieces on average at 12×12.

That is a strange-looking ladder. region — the rule that an open region has a multiple of three cells, which sounds like it should be doing a lot — 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.

The reason shows up more plainly if you ask what each rung can prove from an untouched board, before any guess at all — which is exactly what the checkbox above the board displays:

There is nothing on the board 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 a fixpoint somewhere to start. Heteromino prints holes. Every open cell starts with 9.5 candidate pieces on average and no local rule can eliminate any of them, so the first three rungs between them settle 2.1% and 4.2% of the board and then stop. One level of lookahead — assume a piece, propagate, keep it only if that survives — settles 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.

The bug the second engine caught

The search branches on "which piece owns this cell", which partitions the answers, 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, as a tidy-looking optimisation. Propagation could then commit a later candidate to that same cell — and when that candidate's own branch came up, the commit found the cell already owned, returned false, and the branch was skipped in silence. It lost answers without ever raising an error: the propagator reported 5 tilings of a blank 3×4 where 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.