SEN LLC

Posted on Sep 10

Araf: the numbers only ever argue about size, so a trade is invisible to them

#typescript #algorithms #gamedev #puzzle

Araf in the browser with a four-rung solver. Cut the grid into rooms;
every room holds exactly two numbers and its area sits strictly between
them — 2 and 6 mean a room of 3, 4 or 5 cells. The load-bearing fact is a
one-line lemma: move one cell from a room to its neighbour and every other
room is untouched, both rooms keep their own two numbers, and the only
thing the rules can complain about is that the donor fell under its floor or
the receiver rose over its ceiling. So what happens if you swap one cell
each way? Both sizes survive it. The numbers have nothing to say at all.
All 665 such trades available on the boards I ship are illegal, and every
single one of them is illegal because a room falls apart — never because of a
number. Of 2,657 one-cell perturbations, 73.5% are killed by connectivity,
not by arithmetic.

Live demo: https://sen.ltd/portfolio/araf/
Source: https://github.com/sen-ltd/araf

The rule

Cut the grid into rooms.

Every room holds exactly two numbers
The room's area sits strictly between them: with a < b, the room has a+1 .. b−1 cells
Rooms are edge-connected, and every cell belongs to one

That is all of it. The numbers never move and never change. The only thing a
player does is draw lines.

It is a short rule, and the thing this post is about is that what is printed on
the board and what actually holds the answer down turn out to be different
things.

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 cheap tests rule a pair out before any search runs.

No size fits between them. a < b asks for a room of a+1 .. b−1 cells, so b − a ≤ 1 leaves the empty set. Two equal numbers can never share a room.
They are too far apart. A room of at most 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. A room may not swallow one, so the path has to avoid every other number on the board — and often the detour is too long.

Over the 72 boards I ship:

board	pairs	no size fits	too far	blocked by a third	alive
6×6	236.5	77.0	66.6	53.3	39.7
8×8	692.0	225.9	286.6	98.8	80.7

That is 33,426 pairs reduced to 4,333 — 13.0% survive.

The third screen is the one I expected to be a rounding error. The rooms are
tiny, and how often can a third number really be sitting in the only doorway?
On its own it accounts for 5,474 pairs, 16.4% of the total. Small rooms
also means a dense board, and a dense board is mostly doorways.

What happens when you move one cell

This is the whole puzzle in one paragraph. Take a finished board and hand one
cell from room i to a neighbouring room j.

Every other room is untouched.
Both i and j still hold their own two numbers — number cells never move.
Therefore the only thing the rules can object to is that i has fallen under its floor (lo) or j has risen over its ceiling (hi).

So a board with exactly one answer needs, for every available one-cell move,
that the donor already sits at its floor or the receiver already sits at its
ceiling.

Counted the blunt way. There are 1,992 one-cell donations on the shipped
answers, and every one of them is illegal:

what stopped it	count
the donor's floor	554
the receiver's ceiling	284
the donor breaks in two	1,287

(A floor and a ceiling can both apply, so the column adds to more than 1,992.)

A trade is invisible to the numbers

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 preserves every room size on the board.

There are 665 geometrically available trades across the shipped answers.
All of them are illegal, and all of them are illegal because a room falls
apart. Not one is stopped by a number.

That is not "the numbers failed to stop it". It is "the numbers cannot see it".
That share of the work of pinning the answer down was never theirs to do.

Which is why three quarters of the rigidity is not in the numbers

This is the thing I had backwards going in. The numbers are all that is printed
on the board, so I assumed they were what makes the answer unique. Count every
one-cell perturbation:

what killed it	count	share
the shape of the rooms	1,952	73.5%
a floor or a ceiling	705	26.5%
total	2,657	100%

The numbers are the part you read. The geometry is the part that does the
work.

The ration

There is exactly one equation tying the whole board together. Every cell lands
in exactly one room, so the room sizes add up to the area of the grid:

Σ lo  ≤  cells  ≤  Σ hi

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

And how far the board sits above its floors plus how far it sits below
its ceilings is exactly its slack, which is by construction the number of
window widenings the generator got past the uniqueness check.

The one-cell lemma has a second corollary 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.

If it did, the cell between them could move, and the board would have two
answers. Across 1,074 shipped rooms:

room state	count
can only take (sitting at its floor)	497
can only give (sitting at its ceiling)	156
can do both	269
can do neither (pinned exactly)	152
adjacent pairs that break the rule	0

Slack is the dial

The generator never designs difficulty. It does two things.

Draw the rooms first, then hand every room the tightest numbers that describe it — size−1 and size+1, the only pair that pins a size exactly.
If that board is unique, give it back as much freedom as it can survive: widen one window by one, keep it if the answer is still alone, otherwise put it back.

The dial below skips step 2's checking. Take a board that is unique when tight,
widen k windows at random, and ask whether the answer is still alone.

widenings	6×6 unique	8×8 unique
0	120/120	120/120
4	55/120	56/120
8	14/120	20/120
12	12/120	5/120
16	1/120	1/120
24	0/120	1/120
32	0/120	0/120
48	0/120	0/120

The 8×8 boards I ship carry 38.1 widenings each. Doing that at random works
0% of the time, which is why the generator keeps only 38.1 of the 109.4
widenings it tries per board.

And when it stops, every remaining widening of every window has been tried
and refused. The board is a local maximum. That claim is not the generator's
self-report: npm test reads the shipped file back and re-derives it.

Boards do not happen by accident

Random rooms, numbers drawn around them, a handful of random widenings:

board	widenings	drawn	one answer	more than one
6×6	6	200	9	191
6×6	12	200	0	200
8×8	10	200	0	200
8×8	20	200	0	200

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 — at 8×8 it never once
turned up by itself in 400 draws.

Both ways of misreading "between" delete the puzzle

Drop "strictly." Read the interval as closed and numbers one apart — or two
equal numbers — describe a room again. The first screen stops firing.

Drop "edge." Let rooms hold together through a corner and a five-cell room
has an order of magnitude more shapes.

misreading	board	rooms (official)	rooms	alive pairs (official)	alive pairs	still unique
inclusive	6×6	264	535	39.7	58.0	0 of 12
inclusive	8×8	731	1,788	78.3	121.1	0 of 12
diagonal	6×6	264	2,106	39.7	81.1	0 of 12
diagonal	8×8	731	6,937	78.3	179.0	0 of 12

Every board sampled runs past the 2,000-answer counting cap under both
misreadings, and not one stays unique. The nasty part: the intended answer
remains legal under both readings. Nothing looks wrong while you are solving.
It looks wrong only when you notice a second answer exists.

The four rungs

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.

rung	6×6	8×8
`pair` — the screen and nothing else	5.6%	3.4%
`cell` — unit propagation, four ways	26.6%	12.6%
`ration` — assume a room, count the cells left	100%	100%
`search` — exact cover, most-constrained cell first	100%	100%

cell is four rules run to a fixpoint:

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, which kills the partner's other rooms;
a cell whose remaining rooms all belong to one pair of numbers pins that pair's room to the cell.

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

Counting, to keep the enumerator honest

The most fragile thing in this solver is the room enumerator. Miss one
connected set and nothing crashes; the answer count is just quietly wrong.

So: point it at a single cell of an empty grid and it has to reproduce the
fixed polyominoes, A001168, exactly. It does,
out to 36,446 at ten cells. Duplicate emissions come out high, missed sets come
out low, and either shows up immediately.

While I was there, the size of 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:

grid	cuts into rooms	rooms of 2..5 only
2×2	12	3
3×3	1,434	118
3×4	27,780	1,020
4×4	1,691,690	21,190

Two engines

The pair screen and the ration are exactly the kind of optimisation that is
fast and might be wrong, so both are checked against an engine that has
neither: take the first cell nobody owns, grow every connected set out of it,
and if one happens to hold two numbers and a legal size, make it a room and
recurse. It thinks about nothing.

On the boards small enough for it to finish: 60 boards, 0 disagreements —
and they agree on the answer set, not only the count. The same cross-check
runs under the inclusive misreading, where the screens behave completely
differently.

41 tests in all.

Wrapping up

Araf looks like a numbers puzzle. Numbers are the only thing on the board.

But the numbers can only talk about room size, and any rearrangement that
preserves the sizes — a one-for-one trade between neighbours — is completely
invisible to them. 73.5% of the work of making the answer unique belongs to
connectivity, and always did.

One inequality (Σ lo ≤ cells ≤ Σ hi) and one corollary (a room that can give
must not touch a room that can take) are enough to write a generator that never
designs difficulty once and still emits locally maximal boards.