Araf

Most pairs of numbers were never going to be a room

A room holds exactly two numbers, so the first question is which two numbers could ever share one. Three things can rule a pair out before any search starts, and all three are cheap.

• No size fits between them. Numbers a < b ask for a room of a+1 .. b−1 cells, so b − a ≤ 1 leaves nothing. Two equal numbers can never share a room.
• They are too far apart. A room of b−1 cells holding both of them needs a path between them, so they cannot be more than b−2 steps apart.
• The only way across runs over a third number. The room is not allowed to swallow one, so the path has to avoid every other number on the board — and often there isn't one that short.

Over the 72 boards shipped here that is 33,426 pairs of numbers reduced to 4,333 — 13.0% survive. The third screen is the one I expected to be a rounding error and it is not: it alone accounts for 5,474 pairs, 16.4% of the total.

The numbers only ever argue about size

Take a finished board and move one cell from room i to a neighbouring room j. Every other room is untouched, both rooms still hold their own two numbers, and the only thing the rules can complain about is that i has fallen under its floor or j has risen over its ceiling. So a board with one answer needs, for every such move, that the donor already sits at its floor or the receiver already sits at its ceiling.

Checked the blunt way: all 1,992 one-cell donations across the shipped boards are illegal. 554 of them are stopped by the donor's floor, 284 by the receiver's ceiling, and 1,287 never got that far because taking the cell out breaks the donor in two.

Now swap one cell each way between two rooms. Both sizes come out unchanged. Both rooms keep their numbers. The rules have nothing whatsoever to say about it — the entire vocabulary of Araf is room size, and a trade keeps every room size on the board. All 665 trades available on the shipped answers are illegal, and every single one of them is illegal because a room falls apart, never because of a number.

Which is why most of the rigidity is not in the numbers

That was the thing I got wrong going in. The numbers look like the whole puzzle — they are all that is printed on the board — so I expected them to be what pins the answer down. Count the one-cell perturbations of the shipped answers and they are not:

73.5% of the way this puzzle holds still is connectivity, not arithmetic. The numbers are the part you read; the geometry is the part that does the work.

The ration

Every cell lands in exactly one room, so the room sizes add up to the grid. Write lo and hi for the floor and ceiling of each room and the whole board is squeezed between two sums:

Σ lo ≤ cells ≤ Σ hi

The solver uses the same inequality on what is left: each number that has not been given a room yet is half of a room, so the cheapest and dearest room it could possibly belong to bound the cells still open. That is the ration rung, and it is the only thing on the ladder that knows anything global.

The distance the board sits above its floors plus the distance it sits below its ceilings is exactly the total slack — the number of widenings the generator managed to sneak past the uniqueness check. On the shipped boards that splits 9.9 above and 28.1 below at 8×8.

And the one-cell lemma has a consequence worth stating on its own: a room that can afford to give a cell away must never sit next to a room that can afford to take one. Of 1,074 shipped rooms, 497 can only take, 156 can only give, 269 can do both and 152 are pinned exactly. 0 pairs of them break the rule.

The dial is slack

The generator draws the rooms, hands each one the tightest numbers that describe it — size−1 and size+1, the only pair that pins a size exactly — and then gives the board back as much freedom as it can survive, one widening at a time. The dial below skips the checking: take a board that is unique when tight, widen k windows at random, and ask whether the answer is still alone.

That is 6×6. An 8×8 has more room and the same shape of curve — 46.7% at 4 widenings, 16.7% at 8, 0.8% at 16 — and the boards shipped here carry 38.1 widenings each. Doing that at random works 0.0% of the time. Every one of them had to be checked.

Which is also why the generator refuses so much: it kept 38.1 of the 109.4 widenings it tried on an average 8×8, and when it stops, every remaining widening of every window has been tried and refused. The board is a local maximum, and npm test re-derives that from the shipped file rather than taking the generator's word for it.

Boards do not happen by accident

Random rooms, numbers drawn around them, a handful of random widenings, and then ask for the answers:

Note what never happens: a board built this way always has at least one answer, because it was built around one. Uniqueness is the part that has to be earned, and at 8×8 it never once turned up by itself in 400 draws.

Both ways of misreading "between" delete the puzzle

The rule is usually written "the number of cells is between the two numbers", and the two things people drop are the word strictly and the word edge.

Read between as inclusive and two numbers one apart — or two equal numbers — suddenly describe a room. The first screen stops firing, the catalogue swells, and nothing is unique any more.

Let a room hold together through a corner instead of only through an edge and it is worse: the catalogue grows by an order of magnitude, because a room of five cells has far more shapes when diagonals count.

Every board sampled runs past the 2,000-answer counting cap under both misreadings, and not one of them is unique. The intended answer stays legal in both cases, which is exactly what makes the misreadings dangerous: nothing looks wrong until you notice that a second answer exists.

The ladder

Four rungs over the same catalogue of possible rooms. The number is the share of cells whose room the rung can name on its own, averaged over the bank.

• pair — the screen and nothing else.
• cell — unit propagation, four ways: a cell only one room can cover fixes that room; a number only one room can serve fixes that room; a number whose remaining rooms all use the same partner marries the two; a cell whose remaining rooms all belong to one pair of numbers pins that pair's room to the cell.
• ration — assume one room, propagate, and check the cells still open against the sums the remaining numbers allow. Drop the room if that alone contradicts.
• search — the complete solver: exact cover over the catalogue, most-constrained cell first.

The interesting part is what the widening does to that. Graded before any widening — every window as tight as it goes — 35 of the 72 boards fall to cell on its own. Graded as shipped, that is 1. Slack is the difficulty.

Counting, to make sure the enumerator is telling the truth

The room enumerator is the load-bearing piece of the solver: miss one connected set and the answer count is wrong in a way nothing else would catch. Pointed at a single cell of an empty grid it has to reproduce the fixed polyominoes, A001168, exactly.

And for scale, the space an Araf answer lives in: the number of ways to cut a grid into edge-connected rooms at all, which for the square cases is A145835. The second column restricts the rooms to the 2..5 cells this generator draws.

Two engines

The pair screen and the ration are the load-bearing claims here, so both are checked against an engine that has neither: take the first cell nobody owns, grow every connected set out of it that happens to hold two numbers and a legal size, recurse, and never think about anything. On the boards small enough for it to finish, the two agree — 60 boards, 0 disagreements — and they agree on the answer set, not only the count. The same check runs under the inclusive misreading, where the screens behave completely differently.