Statue Park: the no-touching rule isn't a rule, and the circle that names nothing costs 60% more

Statue Park in the browser with five rule sets inside. The clue is a
bag of polyominoes: shade cells so the shaded groups are exactly that bag, and
keep the unshaded cells — the park — in one piece. Puzzle #50 in the solver
series.

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

The rules

Shade some cells of an H×W grid.

1. The shaded cells fall into orthogonally connected groups. The multiset of their shapes, up to rotation and reflection, must equal the given bank — every piece used exactly once.
2. The unshaded cells — the park — form one orthogonally connected region.
3. A black circle must be shaded. A white circle must not be.

There is not a single number anywhere. The clue is the bag, plus the circles.

The most famous rule is not a rule

Every write-up of Statue Park lists "two pieces may not touch" among the
rules. It isn't one.

A maximal connected group of shaded cells is never orthogonally adjacent to
another maximal group — that is what maximal means. So the moment you take the
answer to be a shading rather than an assignment of placements to pieces, the
non-touching rule is free.

What is left over is that the rulebook's model names its pieces, and the name
is unobservable. Therefore:

Two banks with the same shape multiset give the same shadings, and the
labelled count = the shading count × ∏ mₜ!, one factorial per repeated
shape.

This is not an interpretation, it is a measurable claim. The repo ships two brute
force engines that share no code with the propagators. On 5×5:

Two practical payoffs. No symmetry breaking anywhere — the trick you would
otherwise need to stop equal pieces permuting simply does not exist in the
shading model. And two answers always differ as sets of cells, which is what
the next section stands on.

Theorem: black circles alone always suffice, and so do white circles alone

Two answers to the same bank shade the same number of cells, because the bank
fixes the total area. So if two answers differ, then

• there is a cell shaded in A and not in B, and
• there is a cell shaded in B and not in A.

(Equal totals, so it cannot be one-sided.)

Print a black circle on the first and B dies. Print a white circle on the second
and B dies. So a black-only clue set exists and a white-only clue set exists,
for every puzzle.

Existence is settled. What is left is the price.

Measurement: white circles cost about 60% more

Same greedy chooser (look at the second answer, pick a cell where it disagrees
with the intended one, print a circle there), same minimisation afterwards. Only
the alphabet changes:

size  n   mixed  black-only  white-only   black share of mixed   shaded share of board
6x6  40     6.0         5.1         8.1                  55.2%                   36.2%
8x8  23    13.0        11.3        18.6                  63.0%                   34.7%

White-only needs 18.6 circles at 8×8 where black-only needs 11.3. The explanation
is available after the fact: a white circle only says "no statue here", which
kills placements one at a time; a black circle says "a statue passes through
here", which is a claim about a whole piece, and it kills every placement of
every piece that cannot cover that cell.

The interesting column is the third one. Restricting the greedy chooser to black
circles beats letting it choose freely (11.3 vs 13.0 at 8×8). The chooser picks
uniformly among the disagreeing cells, so left alone it keeps buying cheap white
circles. Adding a constraint made it better — a clean example of that.

Corroborating: in the freely-chosen sets, 55–63% of the surviving circles are
black, while only 35–36% of the board is shaded. Minimisation keeps black
circles at nearly twice their base rate.

Five rungs

Every rung is sound (its fixpoint never disagrees with the answer — asserted in
the tests) and monotone (a stronger rung never decides fewer cells).

Incremental: nothing below probe ever finishes a board

Fixpoint on the board an editor would print — the minimal circle set that buys
uniqueness:

size  n      clue   place     fit   white   probe   completions
6x6  40    16.7%   18.8%   25.3%   29.1%   74.0%   clue:0 place:0 fit:0 white:0 probe:26
8x8  24    20.5%   22.6%   25.7%   29.2%   48.9%   clue:0 place:0 fit:0 white:0 probe:5

The bottom four rungs all stall under 30% and probe jumps. There are no
clue-, place-, fit- or white-graded puzzles at all. If you want a
difficulty ladder in the shipped bank you have to buy it, by adding circles until
a weaker rung can finish. That turns out to be nearly free:

size  n   unique-min  solve-min   ratio
6x6  40         6.0        6.5    1.08
8x8  24        13.1       14.3    1.09

Ten percent more circles than uniqueness needs, and the board no longer needs a
search at all. Uniqueness drags search-freeness along almost for nothing.

Ablation: all four rungs are load-bearing

Same boards, full stack minus one rung:

size  variant   fixpoint-bits  boards moved  probe assumptions  search assumptions
6x6  full              1440             0               3098                   0
6x6  −count            1426             1               3385                   2
6x6  −place             736            35               5461                2136
6x6  −fit               834            25               6368                 122
6x6  −white             629            36               4289                1002
8x8  full              1536             0               4274                   0
8x8  −count            1404             6               4543                  28
8x8  −place             845            24               6122               23790
8x8  −fit               807            21               7804                 254
8x8  −white             528            24               4741                5700

The row worth staring at is count. The head count is nearly free at the
fixpoint — it moves one board in forty at 6×6, fourteen bits across all forty —
and it is not free in the search (0 → 28 assumptions at 8×8). Incremental
numbers alone would have called it dead weight. In the other direction, dropping
place at 8×8 makes the search buy 23,790 assumptions.

Ambiguity is not one piece sliding over

Peel circles off until a board goes ambiguous, then compare the second answer to
the intended one, component by component:

size  ambiguous  one piece moved  two    three or more   avg pieces moved
6x6         40            17.5% 42.5%           40.0%               2.23
8x8         24            16.7% 25.0%           58.3%               3.13

In earlier entries of this series a cheap search-free certificate — a two-cell
swap, a 2-opt reversal, a whole row sliding — explained 90%+ of second answers.
Statue Park does not do that. The second answer moves two or three pieces on
average and only one board in six moves exactly one. There is no cheap local
certificate here, and given that the bank is an inherently global clue (where
one piece can go depends on where all the others went), that is probably the
honest picture rather than a gap in the analysis.

How much is the park rule actually worth?

Count answers to the bank constraint alone, then again with the park rule on, no
circles either way:

config          boards  with park  without park   killed
6x6 2x size4/5      30        833          1399    40.4%
6x6 3x size4        30       5730         15149    62.2%
6x6 3x size5        30        704          4431    84.1%
7x7 3x size5        30      18744         57546    67.4%

The bigger the pieces the bigger the connectivity rule's share — pentominoes cut
the park more easily, so at three pentominoes on 6×6 it is throwing away 84% of
the answer space on its own. Give the same three pentominoes more room (7×7) and
its share drops to 67%: the rule bites hardest when the board is tight.

The generator never guesses at a bank

No "draw a partition, print clues, pray a solution exists". Answer first:

1. Drop pieces one at a time at a random legal spot, never touching an existing piece.
2. After every drop, check the park is still connected, and refuse placements that would cut it.
3. When the last piece lands, that already is a legal answer — so the bank is read off it rather than guessed at.

Legality is structural, so only uniqueness has to be bought: look at the second
answer, print a circle where it disagrees, then minimise the set.

Soundness

• Three engines agree. The propagating search, a placement-first brute force, and a cells-first brute force that never names a piece. Solution counts agree on 80 clue sets at 6×6, zero disagreements — and the count does not change across the rungs of the ladder either.
• External ledger. Give the bank k monominoes and switch the park rule off, and an answer is exactly a k-element independent set in the grid graph. Summed over k that has to be 2, 7, 63, 1234, 55447 — OEIS A006506. The tests check it per k against a separate independent-set counter, and check the totals.
• Closed form on a 1×m strip. The park is connected only if the unshaded cells are contiguous, so the shaded cells are a prefix plus a suffix; with monominoes each end holds at most one, giving 1, 2, 1 (for m ≥ 3), 0 for k = 0,1,2,3. The tests reproduce it for every m.
• probe ⇔ unique. Sweeping 300 clue prefixes at 6×6 and 364 at 8×8: zero boards where probe finished but the answer was not unique. The other direction happens — six and four boards are unique without probe seeing it — for 98.0% and 98.9% agreement. probe never lies; it just does not see everything.

69 tests.

The implementation lesson

The thing that cost the most time was the brute force engine that does not name
its pieces. It walks the cells in reading order, shades or doesn't, and whenever
a shaded group is sealed off — every neighbour decided — it charges that
shape against the bank.

The bug: sealed groups were recomputed from scratch at every step. A group sealed
at step i is still sealed at step i+1, so the same piece was charged to the
bank twice. It only misbehaves on banks with a repeated shape, and it only ever
loses answers — the quiet kind of wrong.

The fix was one array of "cells already charged", rolled back on backtrack. The
lesson has the usual shape: you write the brute force engine to check that the
fast implementation is right, and the brute force engine is the thing that breaks
most quietly. Which is why the soundness claim cannot rest on one engine — the
placement-first engine cannot make this mistake structurally (each placement is
handed to exactly one bank slot, so double-charging has nowhere to happen), so
agreement between the two is the detector.

src/statue-park.ts   model, shapes, placement catalogue, five rungs, referee
src/brute.ts         two engines sharing no code with the propagators
src/generate.ts      answer-first layout and the circle-buying loop
tools/stats.mts      every table above

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