Fill-a-Pix: showing every clue does not always pin the picture. When a side is 2 mod 3, the twins can be listed and counted exactly

I built Fill-a-Pix in the browser with a three-rung solver. The standard way to generate one is: draw a picture, show every clue, then remove clues while the answer stays unique. That quietly assumes the full set of clues pins the picture.

It does not, whenever a side of the grid is 2 mod 3. Showing every clue is a linear map, the map is a Kronecker product of tridiagonal all-ones matrices, and their determinants run 1, 0, −1, −1, 0, 1, … with period six: zero exactly at n = 2 (mod 3). On such grids a share of all pictures have a twin, a different picture with exactly the same clues, and no choice of clues can ever turn them into a puzzle. That is 73.4% of all 5×5 pictures and 39.9% of 8×8 ones.

I show that twins come in exactly two families, count them exactly, and check the count four independent ways over all 33,554,432 pictures on 5×5. They agree on every one.

Demo: https://sen.ltd/portfolio/fill-a-pix/ · Source: https://github.com/sen-ltd/fill-a-pix

The rules

• Paint cells to reveal a picture.
• A number counts the painted cells in the 3×3 block around it, its own cell included.
• At the edges the block is cut off: a corner clue sees 4 cells, an edge clue 6.
• Cells without a number may still be painted; they just carry no information.

I checked the rules against Conceptis's description of Fill-a-Pix, because "the clue's own cell counts" changes the implementation and I didn't want to guess it from the name.

The generator assumes something

In this series of solver-backed puzzles there are two ways to build a generator: draw the answer and add clues until it is unique, or show everything and remove. For Fill-a-Pix, removing is natural. Draw a picture, write every clue, delete them one at a time in random order, and keep a deletion only if the answer stays unique. What is left is locally minimal.

That only works if the full set of clues is unique to begin with. If the author's dial is "how many clues to show", I wanted to know whether the dial can max out and still not be enough.

The determinant has period six

A clue sums nine cells, so "show every clue" is a linear map x ↦ A x. It factors: sum each column over three rows, then sum the result over three columns. So

A = T_h ⊗ T_w

where T_n is the n×n matrix with ones on the diagonal and next to it. A Kronecker product is injective exactly when both factors are.

Expanding det T_n along its last row gives d(n) = d(n−1) − d(n−2), with d(0) = d(1) = 1. For n = 1, 2, 3, … that is

1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1, …

Period six, and zero exactly when n ≡ 2 (mod 3).

export function detT(n: number): number {
  let a = 1; // d(0)
  let b = 1; // d(1)
  if (n === 0) return a;
  for (let i = 2; i <= n; i++) [a, b] = [b, b - a];
  return b;
}

When n ≡ 2, the kernel of T_n is spanned by u = (+1, −1, 0, +1, −1, 0, …, +1, −1). It sums to zero over every window of three, so adding it to a column changes no clue. A picture accepts that flip when the column reads 0 1 ? 0 1 ? … 0 1 (or its complement) on the nonzero positions of u, and then it has a twin.

for (const sign of [1, -1]) {
  let ok = true;
  const cells: number[] = [];
  for (let i = 0; i < len && ok; i++) {
    const d = u[i] * sign;
    if (!d) continue;
    const c = at(i);
    if ((d > 0 && pic[c]) || (d < 0 && !pic[c])) ok = false; // +1 paints, -1 clears
    cells.push(c);
  }
  if (ok) out.push({ kind, index, cells });
}

So there are two kinds of grid. When neither side is 2 mod 3, full clues pin every picture and remove-until-minimal always works. Across 24,000 random pictures on the 12 square sizes of that kind, the solver never found a second answer. When a side is 2 mod 3, some pictures can never become puzzles. The page has a twin lab at the bottom: it draws such a picture, outlines the cells that flip, and you can press Flip and watch every number stay put.

Counting it four ways: all 33.5 million 5×5 pictures

The claim is that twins correspond exactly to kernel vectors with entries in {−1, 0, 1}. I checked it by brute force, four ways that share as little code and theory as possible:

1. Group pictures by their clues and count the groups with more than one member. No theory at all; up to 20 cells.
2. Enumerate the ternary kernel directly, row by row, keep its minimal vectors, and test each picture against them.
3. The classifier below, picture by picture.
4. The closed-form count.

grid	pictures	with a twin	grouping	kernel	formula	a line flips	only a two-block flips	kernel vectors (minimal)
2×5	1,024	996 (97.3%)	996	996	996	996	0	344 (42)
3×5	32,768	10,816 (33.0%)	10,816	10,816	10,816	10,816	0	26 (6)
4×4	65,536	0	0	0	0	0	0	0
4×5	1,048,576	433,920 (41.4%)	433,920	433,920	433,920	433,920	0	80 (8)
5×5	33,554,432	24,644,272 (73.4%)	—	24,644,272	24,644,272	24,587,824	56,448	3,194 (216)

(All 15 sizes from 1×1 to 5×5 are on the demo page and in the README.) All four agree everywhere. And on 5×5, for the first time, 56,448 pictures (0.23% of the twins) have a twin even though no single row or column flips.

The complete list of twins

If only one side is 2 mod 3, say the height, the kernel is u ⊗ (anything), so the ternary kernel vectors are just "each column gets +u, −u or nothing". A picture has a twin iff some column fits. Columns are disjoint, so the count is a product: with L nonzero entries in u, a column misses both patterns in 2^L − 2 of its 2^L fillings.

If both sides are, the kernel is u ⊗ a + b ⊗ u, and a second family appears. Split rows by whether u_i = 0, and columns likewise. Lines through a zero row or column live on their own cells. On the cells where both u's are nonzero,

d_ij = u_i u_j (a_j + b_i),   every a_j + b_i ∈ {−1, 0, 1}

The spread of a plus the spread of b is at most 2, which leaves two cases:

• a or b is constant: d is a set of whole lines.
• Neither is: after a shift, a takes values {0, 1} and b takes {−1, 0}. That 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.

That is the whole list. Now recolour the both-nonzero cells as Y_ij = x_ij XOR [u_i u_j = −1], and the conditions become statements about a small 0/1 matrix. A line fits iff its row or column of Y is constant. A two-block vector fits iff every row of Y is all 0 on J or all 1 off J. The classifier is literally that:

const full = (1 << b) - 1;
for (let J = 1; J < full; J++) {
  if (!Y.every((y) => (y & J) === 0 || (y | J) === full)) continue;
  // row i goes in I' if (Y[i] & J) === 0, otherwise in the complement
  ...
  return { kind: 'block', cells };
}

Counting has the same shape. Stack Y one row at a time and keep, as the state, the set of J's that every row so far allows. Each row can only shrink that set by intersection, so the number of states stays small (0.35 s for a 6×6 Y).

let states = new Map<bigint, bigint>([[(1n << BigInt(Js.length)) - 1n, 1n]]);
for (let r = 0; r < a; r++) {
  const next = new Map<bigint, bigint>();
  for (const [st, cnt] of states)
    for (const [s, mult] of groups) {   // rows grouped by the set of J they allow
      const t = st & s;
      next.set(t, (next.get(t) ?? 0n) + cnt * mult);
    }
  states = next;
}
return states.get(0n) ?? 0n;            // no J survives: no twin

The number of m×m 0/1 matrices with no constant row or column has a closed form by inclusion–exclusion: 2, 102, 22874, 17633670, 46959933962, … It matches OEIS A283624 for eight terms. The number with no twin at all, which also excludes the two-block splits, is 2, 102, 22730, 17564070, 46913648762, and that sequence is not in the OEIS. The stats run checks both against brute force up to m = 4 every time.

How often, size by size

The exact twin share is cheap while Y is at most 6×6 (grids up to 8×8). The line-only share is exact at every size. I compared both against 2,000 random pictures per grid, each handed to the solver with every clue shown:

grid	with a twin (exact)	a line flips (exact)	solver, sampled (95%)
5×5	73.446%	73.277%	74.80% ± 1.90%
8×8	39.873%	39.814%	38.55% ± 2.13%
11×11	—	15.848%	14.40% ± 1.54%
14×14	—	5.327%	5.35% ± 0.99%
17×17	—	1.647%	1.50% ± 0.53%
20×20	—	0.487%	0.35% ± 0.26%
8×10	27.202%	27.202%	27.10% ± 1.95%
10×11	7.543%	7.543%	6.90% ± 1.11%

Every other size (6×6, 7×7, 9×9, …) is 0%. The classifier and the solver disagree on 0 of 50,000 pictures, and every twin the classifier names is verified 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 million draws found 617 (593 expected). On 11×11 a million draws found 10. Past 8×8 the line share is the twin share to every digit shown.

The generator: redraw the twins

The generator paints each cell with a fair coin. On a grid with a side of 2 mod 3 it asks the classifier whether the picture has a twin and redraws if so. No search is needed for that. Then it shows every clue and removes clues in random order while the answer stays unique. Uniqueness checks branch away from the known answer first, so a second answer, if there is one, turns up within a few nodes. A check that hits the node cap keeps its clue: the generator never guesses.

Sixteen boards at every size from 5 to 15, 176 in all:

grid	clues kept	redraws (expected)	finishes at count / pair / probe / search	ms per board (median / worst)
5×5	41.5% ± 1.4%	54 (44.3)	0 / 14 / 2 / 0	9 / 16
8×8	45.4% ± 1.3%	15 (10.6)	0 / 6 / 10 / 0	151 / 414
10×10	43.4% ± 0.7%	0 (0.0)	0 / 1 / 14 / 1	561 / 2,459
11×11	43.1% ± 0.8%	1 (3.0)	0 / 1 / 14 / 1	1,275 / 7,030
13×13	42.0% ± 0.5%	0 (0.0)	0 / 1 / 10 / 5	5,218 / 14,580
15×15	44.2% ± 0.7%	0 (0.0)	0 / 0 / 8 / 8	19,040 / 216,501

It redrew 71 pictures across 176 boards; the exact twin share predicts 58.8. Apart from that, the two kinds of grid behave the same downstream: minimal boards keep 44.2% of their clues on sizes that are not 2 mod 3 and 43.2% on sizes that are.

Complementing a picture maps each clue v to (block size − v), so a picture has a twin iff its complement does. The redraw therefore leaves the painted share at one half (49.9% in the generated boards), and a test checks the symmetry.

Greedy removal makes hard boards. Of the 176, 0 finish at count, 37 at pair, 118 at probe and 21 need search. The larger the board, the more often the search is needed: 8 of 16 at 15×15.

Which clues survive

I pooled every generated board and asked which of the original clues were kept. I expected the extreme values, the ones that settle a whole block on their own, to survive most often. They survive least.

• Position matters. 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, and the clues next to it see all four as well.
• The value barely matters. Inside, the values 1 to 8 all land between 44.8% and 46.7%.
• Block-settling clues (0 anywhere, 4 in a corner, 6 on an edge, 9 inside) survive 35.3% of 357 (± 2.5%), against 43.6% for everything else.

My reading: a one-colour block pushes the clues around it to their bounds, and a clue at a bound is exactly what count and pair act on, so the neighbours usually rebuild it. That is a guess; the rates are what I measured.

The ladder, priced rung by rung

rung	what it does
count	a clue already met blanks the rest of its block; a clue that needs every open cell paints them
pair	two clues with overlapping blocks: bound the painted count of their shared open cells from both sides
probe	paint a cell (or blank it), run the cheaper rungs; a contradiction settles it the other way

pair precomputes each pair's shared and one-sided cells, so an evaluation is a tally:

const needA = p.clues[q.a] - inkBoth - tally(q.onlyA, a);
const needB = p.clues[q.b] - inkBoth - tally(q.onlyB, bb);
// painted cells among the shared open ones: lo .. hi
const lo = Math.max(0, needA - a.length, needB - bb.length);
const hi = Math.min(both.length, needA, needB);
if (lo > hi) return -1;
if (lo === both.length) fill(both, INK);
else if (hi === 0) fill(both, BLANK);
if (a.length) {
  if (needA - hi === a.length) fill(a, INK);
  else if (needA - lo === 0) fill(a, BLANK);
}

On the 20 shipped boards (five each at 8×8, 10×10, 11×11 and 15×15: 2,550 cells, 1,092 clues shown):

rung	cells settled, climbing	finished, climbing	cells settled without it	finished without it	search nodes without it
count	93 (3.6%)	0 / 20	2,210 (86.7%)	7 / 20	≥ 1,986,479 (1 board hit the 1M-node cap)
pair	694 (27.2%)	1 / 20	353 (13.8%)	0 / 20	≥ 5,625,115 (5 boards hit the cap)
probe	2,434 (95.5%)	19 / 20	694 (27.2%)	1 / 20	—

The search column runs without probe, with count and pair at every node; with both it needs 390,758 nodes over the whole bank.

I had to build this table twice. The first version said dropping count or dropping pair still finishes 19 of 20, which read as "with probe around, the cheap rungs are free". The cause was the probe itself: it tested each assumption with a hard-coded only('count', 'pair'), so a rung I had "removed" kept running inside it. Once the probe uses only the cheap rungs that are switched on, dropping count finishes 7 of 20 and dropping pair finishes none. Every rung carries weight.

function probeRule(P: Prepared, s: Uint8Array, set: Setter, rules: Rules): number {
  // the probe runs whichever cheaper rungs are switched on, never itself
  const inner = rules.map((on, i) => on && RULE_NAMES[i] !== 'probe');
  ...

An ablation switch has to reach inside the rungs that call other rungs. A test now pins it: with only probe switched on, not a single cell settles.

What I'd tell you to steal

1. Prove "all clues shown is unique" before you generate by removal. For Fill-a-Pix it fails when a side is 2 mod 3, and a one-line recurrence tells you why.
2. With linear clues, a second answer is a small integer kernel vector. Twins here are exactly the {−1, 0, 1} kernel vectors, and classifying them turns "is there a second answer?" into a lookup.
3. Back a classification with counts that don't share assumptions. Grouping by clues, enumerating the kernel, the classifier and the formula agreed on all 33.5 million 5×5 pictures.
4. Look for the rare family. Line flips miss 0.23% of 5×5 twins. A 2,000-picture sample would never show it; the full census did.
5. Measure the hypothesis you're sure of. "Extreme clues survive" was backwards. Position matters, value hardly at all.
6. When you remove a rung, remove it from inside the rungs that call it. My probe called the cheap rungs by name, and that made them look free.

Every number here comes from npm run stats, and the README and page prose are generated from src/stats.json by npm run notes. 20 boards shipped, 20 tests.

Play it · Source