Stostone: the rule says drop the stones — and nothing ever has to move

Stostone in the browser with a five-rung solver. The headline rule is
written as physics — drop the stones, they must fill the bottom half — and it
is not physics at all. It is a per-column count plus one invariant, and both
can be checked without moving anything. Puzzle #53 in the solver series.

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

Rules

The board is H×W with H even, and it is cut into regions.

1. Shade some cells. The shaded cells of each region form exactly one connected group — a stone — and every region has one.
2. Two stones may not touch.
3. A number in a region gives the size of that region's stone.
4. Drop the stones straight down, each one rigid. They must come to rest exactly filling the bottom half of the board.

Rule 4 is the reason the puzzle exists. It is also the only rule in this whole
series of genre implementations that is stated as a process: do a thing, then
look at the result. Every other pencil puzzle states a property of the grid in
front of you. So the first question is whether the process is really necessary.

It is not.

The counting half

Falling moves cells vertically. It cannot change how many shaded cells a column
holds. And "the bottom half is exactly full" says every column ends with
H/2 shaded cells. Therefore:

Every column starts with exactly H/2 shaded cells.

A statement about a configuration nobody has computed yet is really a local
count on the one in front of you. That is one line of code and it is the whole
col rung of the solver.

The rest of it

Number the shaded cells of a column from the bottom. The one with b blanks
under it has to land on row H−1−b, so it wants to travel H−1−b−r. A stone
is rigid — every one of its cells travels the same distance — so:

blankBelow(r, c) is the same for every cell of a stone, and that common
value is exactly how far the stone falls.

That is the entirety of rule 4, with no simulation in it:

export function packsByRank(h: number, w: number, cells: Int8Array): boolean {
  if (!columnsBalanced(h, w, cells)) return false;
  const below = new Int32Array(h * w);
  for (let c = 0; c < w; c++) {
    let seen = 0;
    for (let r = h - 1; r >= 0; r--) {
      below[r * w + c] = seen;
      if (cells[r * w + c] === BLACK) seen++;
    }
  }
  for (const comp of blackComponents(h, w, cells)) {
    let key = -1;
    for (const k of comp) {
      const v = Math.floor(k / w) + below[k];
      if (key === -1) key = v;
      else if (v !== key) return false;
    }
  }
  return true;
}

There is a second thing hiding here, which is that "drop the stones" is not
obviously well defined at all. Which stone falls first? Does the answer depend
on the order? It does not, and the reason is worth stating: two stones sharing a
column impose d_i − d_j ≤ gap on their displacements, a system of difference
constraints is closed under componentwise maximum, so a unique maximal solution
exists and any greedy schedule reaches it. The repository simulates the fall
twice on two different schedules — one row at a time for everything at once, one
stone at a time all the way down — and checks both against the invariant that
does not simulate it. On every grid the tests can enumerate exhaustively, all
three agree.

The corollary you can see

Apply the invariant to two cells of one stone in the same column, r < r'. With
B shaded cells strictly between them, blankBelow(r,c) = blankBelow(r',c) +
(r' − r − 1 − B), and the invariant forces B = r' − r − 1 — all of them. So:

A stone never has a vertical hole.

That gives three nested readings of rule 4:

• count: every column carries H/2.
• convex: that, plus no stone has a vertical hole.
• exact: the real thing.

All three ship as switchable rule sets, which is what makes the next section
possible.

Counting is necessary and is not sufficient

The smallest witness is 4×3. Every column carries 2 of 4, neither stone has a
vertical hole, and the arch still comes to rest one row high, because its middle
prong lands on the cell underneath:

# . #        . . .
# # #   ↓    # . #
. . .        # # #
. # .        . # .

Counting the region-free grids — no regions, no numbers, just the shadings an
H×W board admits — puts numbers on the gap. count has the closed form
C(H, H/2)^W; the other two were enumerated by walking only the balanced grids.

board	exact	convex	count	exact/count
2×n	2ⁿ	2ⁿ	2ⁿ	100.0%
4×2	28	36	36	77.8%
4×4	640	1,296	1,296	49.4%
4×10	7,618,204	60,466,176	60,466,176	12.6%
6×2	226	376	400	56.5%
6×4	31,820	133,760	160,000	19.9%
6×6	4,482,592	47,582,864	64,000,000	7.0%
8×2	1,940	4,248	4,900	39.6%
8×4	1,717,396	15,963,452	24,010,000	7.2%

Two edges of that table are provable and both come out right. On a two-row
board the three readings coincide: a stone straddling a gap would need three
shaded cells in a column and there are only two, so exact = 2^W exactly. A
single column packs whenever it is balanced, so exact = C(H, H/2). Column
convexity is likewise vacuous at four rows — the convex and count columns
are identical for every 4×n — and only starts costing anything at six rows.

The 4×n counts are 6, 28, 134, 640, 3058, 14612, 69822, 333640, 1594282,

1. They are not in OEIS. They do satisfy

a(n) = 6·a(n−1) − 5·a(n−2) − 4·a(n−3)

for every term computed — fitted from the first three and confirmed by the next
seven. A transfer matrix of that width would be the proof; this repository does
not have one, and the README says so.

The half that cannot open a board is the half you cannot do without

The solver is a five-rung ladder: col (the counting half of rule 4), clue
(the numbers, one stone per region, stones apart, reachability), fit (list
every way a region's stone could still be drawn and keep what they agree on),
drop (the invariant and its corollary), probe (singleton consistency).

Run each rung on its own, cumulatively, from an empty grid, over the 77 shipped
boards:

size	col	clue	fit	drop	probe
6×6	0.0%	37.9%	75.4%	78.5%	100.0%
8×8	0.0%	11.7%	26.2%	28.5%	100.0%

col settles nothing. It is pure saturation — it can finish a column, and
at the start no column is finished either way. It cannot open a board. But
attribute every cell the full stack writes to the rung that wrote it:

size	boards	col	clue	fit	drop	probe
6×6	44	19.5%	37.8%	31.1%	5.5%	6.1%
8×8	33	14.6%	29.2%	22.1%	7.9%	26.2%

Give it one cell from anywhere else and it writes about a sixth of the board.
And take each rung out of the full stack:

variant	settled	finish without guessing	assumptions
all rungs	100.0%	77/77	0
− col	48.8%	1/77	350,027
− clue	98.6%	75/77	4
− fit	90.1%	67/77	47
− drop	76.1%	36/77	4,917

Without probing on top the same order holds: 593,084 assumptions without col,
14,306 without drop. The half of rule 4 that cannot open a board is 71 times
the more expensive half to do without.

Now ablate rule 4 as a rule of the puzzle instead of as an inference, and the
picture turns over. Here the arithmetic half is the one that is not enough:

size	exact	convex	count	none
6×6	44/44	34/44	34/44	0/44
8×8	33/33	2/33	2/33	0/33

At 6×6, weakening the real rule to counting costs 10 of the 44 boards their
unique answer — and adding convexity back buys none of them; exactly the same 10
fall either way. At 8×8, 31 of the 33 lose uniqueness under both, with a median
of 37 answers where there had been one. On the shipped 6×6 region maps, counting
alone admits 8,081 answers where the real rule admits 2,870: 35.5%.

So the two halves are not two smaller versions of the same rule. One does almost
all of the deducing and none of the disambiguating; the other does almost none
of the deducing and all of the disambiguating.

The clue language, and what it cannot say

A number lives in a region and gives that region's stone size, so the entire
clue language is the vector region ↦ size. The strongest clue set that exists
is a number in every region. So an answer can be pinned down iff it is the
only legal grid with its size vector — and that fails a lot:

board	stones aimed at	pinned by every number	median answers
6×6	2	57.1%	1
6×6	3	32.7%	2
6×6	4	20.6%	3
8×8	3	50.0%	1.5
8×8	4	33.3%	4

Fewer, larger stones means fewer regions means a shorter vector, and the vector
runs out of things to say. This is the one measurement here that the shipped
boards cannot provide, because the generator draws the stones first and the
region map second, and simply redraws the map until the full number set does pin
the answer. Measuring the rate on the boards it kept would be measuring its own
filter. So it is measured separately with the filter switched off, and the
README says which is which.

Once a board is pinnable, very few numbers are needed: 2.6 of 9.5 regions at
6×6, 5.3 of 11.5 at 8×8.

Generation runs backwards

Every legal position is a bottom half packed solid, cut into connected pieces,
and lifted. That is the invariant read right to left, so the generator never has
to reject an answer for failing rule 4:

1. Fill the bottom H/2 rows — what the stones must look like once they have landed.
2. Cut that block into connected pieces.
3. Lift each piece. Two pieces sharing a column must keep their order, so the upper lifts at least as far as the lower; those constraints form a DAG, and the occasional cycle just means the two pieces would have to interleave and the draw is thrown away.
4. Refuse a lift that leaves two pieces touching — that fuses them into one stone whose cells disagree about how far they want to fall.
5. Grow the regions outwards from the stones, then buy numbers adversarially.

The one thing that is a search rather than a formula is step 4. The packed block
is solid, so every pair of neighbouring pieces starts out touching and only the
lift can separate them, and on a crowded 8×8 board most random lifts fail. So
step 3 backtracks over lift values.

What the answers look like

size	stones	mean stone	mean fall	stones that never move
6×6	418	1.89	1.50	21.5%
8×8	381	2.77	2.03	17.1%

About a fifth of all stones are already resting where they will end up. Those
are free information: a stone with a blank under it in any column has a nonzero
fall distance, and one that touches the floor pins its entire column below every
one of its cells.

Cross-checks

Three engines that share no code have to agree: the propagating search, an
enumerator that treats a grid as an integer and tries all of them, and one that
picks each region's stone out of that region's connected subsets. Over 60 random
4×4 region maps they agree on all 503 answers, and under every one of the four
settings of rule 4.

probe is sound but not complete. Over 876 clue prefixes it never once claimed
to finish a board with more than one answer; three times a board had exactly one
answer and it still needed a guess. The gap only ever points one way, as it has
in every genre in this series.

The bug the cross-check caught

The interesting failure was not in the puzzle logic. It was in the second
simulation of the fall — the one that drops one stone all the way before moving
to the next. It mixed two coordinate systems: the stone's cells were being
updated in place as it fell, while the collision test still added the cumulative
drop offset on top of them. On a board with one stone it is invisible. It only
diverges when a stone lands on another stone, which is exactly the case the
whole puzzle is about.

Nothing in the puzzle-side tests would have caught it, because the puzzle side
never calls it. It was caught by the property test that asserts the two
schedules reach the same fixpoint — which exists because "the fall is
order-independent" is a claim this repository makes, and a claim like that is
worth a test whether or not you expect it to fail.

Running it

npm install
npm run dev      # the demo on localhost
npm test         # 70 tests
npm run build

MIT.