Pattern · an exhaustive proof, and the part of it you can run

The Seventeenth Clue

A sudoku with too few givens is not hard, it is ambiguous: more than one grid finishes it. For years nobody could find a puzzle with 16 givens that had exactly one completion, and nobody could prove none existed. In 2012 a year of supercomputer time closed the gap. Below, take a clue away from a published 17-clue puzzle and watch the second completion arrive.

The puzzle carries 17 clues and has 1 completion. All 17 single-clue deletions were tried, and every one of them leaves at least two. The cell you empty does not just lose its proof, it stops being determined at all: depending on which given you pull, that cell can legally hold anywhere from 4 to 7 different digits, and 101 legal digits across the seventeen deletions taken together. Seventeen clues is not seventeen clues with slack in it. It is seventeen clues with none.

The rule of the game, stated exactly. A clue is a cell whose digit is given at the start. A puzzle is proper when exactly one filled grid satisfies every row, column and box constraint and agrees with all the clues. The minimum-clue question asks for the smallest number of clues any proper puzzle can have. It says nothing about difficulty for a human, nothing about whether a puzzle can be cracked without guessing, and nothing about how newspapers set puzzles (they print far more givens than this, usually somewhere in the twenties; we have not counted a newspaper's output and do not print a figure for it).

Seven clues can be ruled out on a napkin: two of the nine digits are then missing entirely from the given cells, and any solution can have those two digits swapped throughout to give a second one. Eight has no known pencil-and-paper proof to this day. The paper is blunt about the gap: a theoretical proof of the nonexistence of an 8-clue puzzle is still lacking. Between 8 and 17 the only instrument anyone has found is a computer.

First, a problem small enough to finish

The same question has an answer for a 4×4 board with 2×2 boxes, and there the whole problem fits in a browser tab. There are only a couple of hundred completed 4×4 grids, and the minimum-clue question only ever needs the small subsets: if no subset of size 3 or less is proper anywhere, and some subset of size 4 is, the minimum is 4, and larger subsets cannot change that. So the census below tests every completed grid against every clue set of size 1, 2, 3 and 4, which is 2,516 subsets per grid and 724,608 uniqueness tests in all. Sizes above 4 are skipped, and skipping them is exactly what the argument licenses. It is a few seconds of work on a laptop and up to half a minute on a phone; the progress bar is honest about which you have.

There are 288 completed 4×4 grids. Across all of them, 200,448 subsets of three clues or fewer were tested and 0 were proper; of the 524,160 four-clue subsets, 25,728 were. So the answer for 4×4 is 4, which is what the literature summary in the paper records for the 2×2-box case. That table also lists 8 for the 6×6 board, 14 for 8×8, and 17 for 9×9. Only the first of those is small enough to finish here; the last is the one that needed the cluster.

Notice the shape of the thing. The proof that three clues never suffice is not an argument, it is a list: every grid, every subset, checked. That is exactly the shape of the 9×9 proof too. The only difference is the size of the list, and it is the size that turns a browser tab into a year on a cluster.

What the search was actually searching

Brute force over the clue subsets does not scale: a single grid has 33,594,090,947,249,085 ways to pick sixteen cells, which is far too many to test one at a time, and that is the cost of a single grid with 5,472,730,538 equivalence classes still to get through. The paper's move is to turn the question into a hitting set problem. Find the unavoidable sets of a grid first, the small patches that can be rearranged into a different valid grid. A proper puzzle has to place a clue inside every one of them. So instead of enumerating clue subsets you enumerate hitting sets of a collection of unavoidable sets, which is a much smaller space, and only the survivors go to the solver. Hitting sets are still NP-complete in general, which is why the enumeration algorithm was the research contribution and the cluster time was still needed.

Hitting every unavoidable set you know about is necessary and not sufficient. That is why the original program ran every surviving candidate through a full sudoku solver before believing it. The instrument below is the same asymmetry, made operable.

The grid that needs eighteen

Here is the sophisticated version of the mistake. Seventeen is the minimum, so seventeen clues are enough, right? No. Seventeen is a minimum over all grids: it means some grid somewhere contains a proper 17-clue puzzle. Almost no grid does. And one particular grid, structured enough that the argument can be made by hand, provably cannot be pinned down by seventeen clues no matter where you put them. You can check that by hand, and you can check it here.

The grid below is Figure 10 of the paper. Its 9 tinted regions are not boxes. Each is three rows of one band crossed with one column from each stack, so each holds 9 cells, and between them they cover all 81. Each region carries three digits arranged as a 3×3 Latin square. Every such region is an unavoidable set of degree 2: give the whole rest of the grid away plus one cell of the region, and the region still has more than one legal filling. Press the button and the page tests that for all 81 cells.

Withdraw a region entirely and it has 12 legal fillings, which is the number of 3×3 Latin squares on three symbols. Hand back exactly one of its cells as a clue and 4 survive, for every one of the 81 choices. Four is more than one, so one clue never settles a region.

That is the whole lower bound, and it is genuinely a hand proof. Nine regions, pairwise disjoint, covering all 81 cells. Each needs at least two clues. Seventeen clues cannot give two to each of nine regions, so some region gets at most one, so that region still has a second filling, so the puzzle is not proper. Minimum 18 for this grid, with no computer search over clue subsets at all.

Now the second half, which is the part that gets skipped. Two clues per region is necessary. It is nowhere near sufficient. Of the 36 pairs of cells inside a region, only 9 settle it even when the other 72 cells are handed over, so picking two clues per region is already a delicate choice. Load the near miss: 18 clues, with 2 in every region, and every one of those nine pairs is a settling pair. The puzzle still has 516 completions. The regions are not independent: alternative grids can differ across several regions at once in ways no single region notices. That gap between "hits every unavoidable set I listed" and "has one solution" is exactly the gap the cluster had to spend its time closing, candidate by candidate, in a solver.

Proper 18-clue puzzles in this grid do exist, and load a proper 18 is one: 18 clues, two per region, 1 completion, and all 18 of its single-clue deletions fall back to at least two completions, so nothing in it is spare. We exhibit it rather than derive it: it is shipped as a literal clue string and everything said about it here is re-solved from scratch. We make no claim about how it was originally found.

How thin is the ice under it? Every region has exactly nine settling pairs, so there are 9⁹ = 387,420,489 ways to give each region one of them, and the proper 18 above is one of those. Draw from that space at random and almost nothing comes back proper. The button samples it: same generator, same seed, in this tab and in the offline verifier, so the two agree cell for cell.

The sample comes back with 0 proper puzzles. Zero hits is not "none exist", it is a bound: with no hits in n draws the one-sided 95% limit on the rate is 3/n, so proper puzzles are rarer here than one in 6,667. Offline, on the same stream, we pushed the same script to 2,000,000 draws and found 1. One event in two million is a rate of about one in two million and also a very weak estimate of one: the interval around a single observation runs from roughly one in eighty million to one in four hundred thousand. Either way, thin ice. That longer run is recorded in research/sudoku-16-clue/longrun.json, it is not rerun in this tab, and it is the one number in this section you are taking on our word rather than watching happen.

Is this the most symmetric grid there is?

It would be a good story. It is not true, and the paper is where the story comes from. On the catalogue page the authors write The largest automorphism group occurring has order 648, and is realized, up to equivalence, by exactly one grid, and the cross-reference they attach to that sentence points at Figure 10, the grid above. The lemma about Figure 10, later in the paper, makes no such claim: it says only that a hand proof is possible because this grid is highly structured.

An automorphism is a symmetry of a single grid: a permutation of bands, of rows inside bands, of stacks, of columns inside stacks, optionally a transpose, which lands the grid back on itself once you also relabel the digits. There are exactly 3,359,232 positional moves to try, which is small enough to try all of them. For each one the relabelling is forced by the top row of the image, so the whole test is a table lookup and a comparison. Press the button and the page does it three times: once for Figure 10, once for a grid built to realise the published maximum, and once for a shuffled copy of Figure 10.

Figure 10 has 54 automorphisms. The comparison grid, built from the rule digit = 3·((stack + row-in-band) mod 3) + ((column-in-stack + band) mod 3) + 1, has 648, which is the maximum the paper reports. And the count is an invariant of the equivalence class: conjugating a grid by any symmetry conjugates its automorphism group, so the order cannot change. The page shows that too, by transposing Figure 10, swapping its first two bands and relabelling every digit d to d+1, then recounting: 54 again. So the gap between the two counts is not a near miss or a matter of drawing. Figure 10 is not in the class that realises the maximum, and the paper's cross-reference is wrong.

Nothing else on the page depends on this. The lower bound of 18 comes from the nine disjoint degree-2 regions, which the button above tests directly, and that argument never needed the grid to be extremal. What the superlative would have bought is only rhetoric, and it was not ours to spend.