Fill-a-Pix

Every clue shown is not always enough

A clue is the sum of the nine cells around it, so showing every clue is a linear map from pictures to numbers. It factors: sum each column over three rows, then sum the result over three columns. That makes it a Kronecker product T_h ⊗ T_w, where T_n is the n × n matrix with ones on the diagonal and next to it — and the map is one-to-one on real vectors exactly when both factors are invertible.

Expanding det T_n along its last row gives d(n) = d(n−1) − d(n−2), so for n = 1, 2, 3, … the determinants run 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1, … — period six, and zero exactly when n = 2 (mod 3). On such a line the vector +1 −1 0 +1 −1 0 … +1 −1 sums to zero over every window of three, so adding it to a column changes no clue at all. A picture takes that flip whenever the column reads 0 1 ? 0 1 ? … 0 1 or its complement, and then it has a twin: a second picture with the same clues.

So there are two kinds of grid. When neither side is 2 (mod 3), every picture is pinned by its full set of clues, and the generator can always start from "all shown" and remove. Across 24,000 random pictures on the 12 square sizes of that kind below, the solver never found a second answer. When a side is 2 (mod 3), a share of all pictures can never be made into a puzzle, however many clues are shown — 73.4% on 5 × 5 and 39.9% on 8 × 8 exactly, and from single line flips alone 15.8% on 11 × 11 and still 0.49% on 20 × 20.

The census: every picture up to 5 × 5, counted four ways

The claim that twins are exactly the kernel vectors with entries in {−1, 0, 1} is checked by brute force, four ways that share as little as possible. (1) Group every picture by its clues and count the groups with more than one member — no theory at all, run up to 20 cells. (2) Enumerate the ternary kernel directly, row by row, keep its minimal vectors, and test every picture against them. (3) The classifier below, picture by picture. (4) The closed-form count.

All four agree on every grid up to 5 × 5. On 5 × 5 that is 33,554,432 pictures, 24,644,272 with a twin; the ternary kernel has 3,194 vectors, 216 of them minimal, and 56,448 twins (0.23%) are of the second kind below — no single line flips.

The complete list of twins

When only one side is 2 (mod 3), say the height, the kernel is u ⊗ anything with u = (1, −1, 0, …, 1, −1): every ternary kernel vector is a set of whole columns, each flipped one way or the other, and a picture has a twin exactly when some column fits. Columns are disjoint, so the count is a product: with L the number of nonzero entries of u, each column misses both patterns in 2^L − 2 of its 2^L fillings.

When both sides are, the kernel is u ⊗ a + b ⊗ u, and it has a second family. Split the rows by whether u_i is zero, and the columns the same way. Lines through a zero row or column are on their own cells. On the rest, write d_ij = u_i u_j (a_j + b_i); every a_j + b_i must be −1, 0 or 1. Either a or b is constant — then d is a set of whole lines — or, after a shift, a takes the values {0, 1} and b the values {−1, 0}. That last case is a two-block vector: +u_i u_j on a rectangle of rows I′ × columns J, −u_i u_j on the complementary rows × complementary columns, zero elsewhere. It contains no whole line.

Recolour the cells with both u's nonzero as Y_ij = x_ij XOR [u_i u_j = −1]. Then a line fits exactly when its row or column of Y is constant, and a two-block vector fits exactly when every row of Y is all 0 on J or all 1 off J. Counting m × m matrices Y with no constant row or column gives OEIS A283624; counting those with no two-block split either is the twin-free count, run row by row with the set of still-possible J as the state. That second sequence is not in the OEIS. Both are checked against brute force up to m = 4 on every run.

How often, size by size

The exact share needs the two-block count, which is cheap while the Y matrix is at most 6 × 6 (8 × 8 grids) and blows up past that; the share explained by lines alone is exact at every size. Against both, 2,000 random pictures per grid were handed to the solver with every clue shown. The classifier and the solver disagree on 0 of 50,000 pictures, and every twin the classifier names is checked to leave every clue unchanged.

The two-block family is real but thin, and it thins fast. On 8 × 8 it is exactly 0.0593% of all pictures; a run of 1,000,000 draws found 617. On 11 × 11, 1,000,000 draws found 10. Past 8 × 8 the line count is, to every digit shown, the twin count.

What the generator does with it

Draw a picture with a fair coin per cell, show every clue, then take clues away one at a time in random order, keeping a removal only if the answer stays unique. What is left is locally minimal: no single clue can go — as far as a node-capped check can tell, since a capped check keeps its clue. On a grid with a side of 2 (mod 3) the generator first asks the classifier whether the picture has a twin, and redraws if it does — no choice of clues could ever pin it. It redrew 71 pictures across 176 boards; the exact twin share predicts 58.8.

Nothing else about the two kinds of grid shows up downstream. A locally minimal board keeps 44.2% of its clues on average on the sizes that are not 2 (mod 3), and 43.2% on those that are. Uniqueness checks branch away from the known answer first, so a second answer, when there is one, turns up in a handful of nodes; 80 checks hit the node cap and kept their clue.

The boards are hard for the ladder. Of 176 generated boards, 0 finish at count, 37 finish at pair, 118 finish at probe, 21 finish at search. That is what greedy removal is for: it keeps taking clues until the next one would break uniqueness, and the last few clues it can drop are exactly the ones that only a deep deduction replaces.

Complementing a picture maps each clue v to (block size − v), so a picture has a twin exactly when its complement does. The redraw step therefore keeps the painted share at one half on average; the generated boards have 49.9% of their cells painted.

Which clues survive

Pool every board the generator made and ask which of the clues it started with it kept. Where a clue sits matters more than what it says: 45.3% of inside clues survive, 40.0% of edge clues, 37.6% of corner clues (standard errors 0.4%, 0.7%, 1.8%). A corner clue sees four cells, all of which the clues next to it see as well.

The number itself barely moves the rate. Inside the grid, the values 1 to 8 all survive between 44.8% and 46.7%. The clues that settle their whole block on their own — a 0 anywhere, or a full block (4 in a corner, 6 on an edge, 9 inside) — survive less often, not more: 35.3% of 357 (± 2.5%) against 43.6% for everything else. Such a block is all one colour, which pushes the clues around it towards their own bounds, and a clue at a bound is exactly what count and pair act on; the neighbours usually reconstruct it. That reading is a guess; the rates are measured.

The ladder, rung by rung

Each rung is priced twice on the 20 shipped boards (2,550 cells, 1,092 clues shown): climbing — how much the ladder settles with everything up to that rung — and leave-one-out — what the full ladder loses without it. For the last column the search runs with no probe at all, count and pair at every node, and each of those two is priced by taking it out.

count is where a person starts: a clue already met blanks the rest of its block, a clue that needs every open cell paints them. pair looks at two clues whose blocks overlap: the shared open cells hold at least as many painted cells as either clue cannot fit outside them, and at most as many as either still needs. probe paints a cell, or blanks it, and lets whichever cheaper rungs are switched on look for a contradiction — so leaving a rung out removes it from inside the probe as well. (A first version let the probe keep both cheap rungs whatever the switches said, and the table then showed count and pair as free: 19 of 20 either way.) Leave count out and the ladder finishes 7 of 20; leave pair out and it finishes 0, settling 353 cells; leave probe out and it finishes 1. Every rung carries weight. The search needs 390,758 nodes over the whole bank with both cheap rungs, ≥ 5,625,115 (5 boards hit the 1,000,000-node cap) without pair and ≥ 1,986,479 (1 board hit the 1,000,000-node cap) without count.