The mathematics of Sudoku

In My Sudoku

Seen this way, a Naked Single is a vertex whose 20 neighbours already use 8 of the 9 colours: only one is left for it.

In My Sudoku

Many solvers work on this form, Donald Knuth's Algorithm X and its Dancing Links among them: they always branch on the constraint with the fewest options left. My Sudoku's own search does the same with the cell constraints: it tries first the cell with the fewest possible digits.

The matrix also shows that the two singles are one idea: a Naked Single is a cell constraint, and a Hidden Single a row, column or box constraint, with a single placement left. Either way, a column with a single 1.

Why not (9!)⁹

Each row can be put in order in 9! = 362,880 ways, so one might expect (9!)⁹ grids, about 1.1 × 10⁵⁰. But that counts any nine rows stacked up, with digits repeated in columns and boxes: the constraints are not independent, and the true number is far smaller.

How the count was made

Felgenhauer and Jarvis fixed the first box as 1 to 9 in reading order, which accounts for the 9!, then counted the ways to complete the first three rows: 2,612,736, or 56 × 6⁶. Many of these are alike, one turning into another when columns are swapped or digits relabelled, and can be completed in as many ways; grouping them, they had a computer count, for each group, the ways to fill the last six rows. The total factors as follows, its last factor being a prime number:

9! × 72² × 2⁷ × 27,704,267,971

Essentially different grids

Mirroring a grid along its diagonal, swapping two bands or two stacks of boxes, two rows within a band or two columns within a stack, or relabelling its digits gives a grid that is really the same. These moves form a group of 9! × 3,359,232 elements. Dividing the count by that gives about 5,472,448,000: close, but not right. A few grids are symmetric, left unchanged by some move, so their family is smaller than the group, and the division undercounts them. Burnside's lemma, which counts the grids each move leaves unchanged, puts it right:

5,472,730,538 essentially different grids

Among the Latin squares

A grid is a Latin square of order 9, each digit once in every row and every column, with the box rule on top. There are 5,524,751,496,156,892,842,531,225,600 Latin squares of order 9: the boxes keep only about one in 828,000.

On the limit

The 17-clue puzzle further down sits right on it: its clues show eight digits, and no 6.

On an N × N grid, the same argument requires N − 1 different symbols among the clues.

Unavoidable sets

Such a set of cells, at least one of which must be a clue, is called an unavoidable set. Here a puzzle with 77 clues, only four empty cells, has two solutions: the number of clues says little, their places say a lot.

In My Sudoku

The Unique Rectangle technique turns this around: as a proper puzzle has only one solution, such a rectangle can never come about, and the candidates that would make one can be removed.

Idea of the proof

The proof rests on the unavoidable sets met above: sets of cells of a grid that the clues must hit, or their digits could be rearranged into a second solution. Clues that determine a grid must meet every one of its unavoidable sets: they form a hitting set of the family. The search went as follows:

1. for each of the 5,472,730,538 essentially different grids, find many of its unavoidable sets;
2. list every set of 16 cells that hits them all, the hard part, for which the authors designed a new algorithm;
3. check whether the grid's digits in those 16 cells determine it;
4. they never did.

It is a real proof, but one only a computer can carry out: no one could check it by hand.

Minimal is not minimum

A puzzle is minimal when removing any one of its clues lets in a second solution, and minimum when no puzzle has fewer clues: 17. A puzzle can be minimal with 25 clues, none of which can go, while other puzzles make do with fewer.

Apart from those at the Very easy level, My Sudoku's puzzles are minimal: it fills a grid at random, then removes the clues one by one in random order, putting back any whose removal lets in a second solution. Its puzzles usually end up with 22 to 27 clues.

Part B: Sudoku is NP-hard

A Latin square of order N fills an N × N grid with N symbols, each once in every row and every column: the rules of Sudoku without the boxes.

Charles Colbourn proved in 1984 that deciding whether a partly filled Latin square can be completed is NP-complete. Yato and Seta turn any partly filled Latin square L into a partly filled Sudoku S(L), in polynomial time: the clues of S(L) are laid out so that its free cells can only be filled the way L can be completed. Each completion of L gives exactly one solution of S(L), and the other way round (a parsimonious reduction):

L can be completed ⟺ S(L) has a solution

A fast method for Sudoku would therefore give a fast method for Latin squares. As completing a Latin square is NP-complete, Sudoku is NP-hard; with part A, NP-complete.

What it does not mean

It does not mean that 9 × 9 puzzles are hard: their size is fixed, and a computer solves any of them in a moment. NP-completeness is about the whole family, as n grows: no method is known that solves every grid in a time polynomial in its size, and finding one would prove that P = NP, one of the great open questions of mathematics, with a million-dollar prize from the Clay Institute.

A second solution: ASP-complete

Yato and Seta prove more: given a Sudoku and one of its solutions, deciding whether it has another is just as hard. The problem is ASP-complete (for Another Solution Problem). It is the question every puzzle maker faces, since a proper puzzle has a single solution.

So My Sudoku's generator leaves nothing to chance: after each clue it removes, a search looks for a second solution, stopping at the first it finds, and if it finds one, the clue goes back.