A Latin square with boxes

The puzzle has a short history and a long ancestry. Howard Garns published it in 1979 in an American puzzle magazine under the name Number Place; the Japanese publisher Nikoli adopted it in 1984 and named it Sudoku; a British newspaper introduced it to Europe in 2004. The mathematics behind it is two centuries older.

A completed Sudoku is a Latin square: nine rows and nine columns, each holding the digits one to nine once. What makes it a Sudoku is one further condition, that each of the nine 3×3 boxes holds every digit once as well. The puzzle is a partly filled grid with exactly one way to finish it. That is all the definition there is, and it places Sudoku squarely inside the subject of the thirty-six officers — a Latin square, made rarer by one more demand, presented as a partial square to be completed.

Three questions follow from the definition, and each has the same shape as the questions already asked about Latin squares. How many grids are there? How many are genuinely different, once the symmetries of the rules are allowed for? And how few given digits can force a unique completion? At order nine the answers are known, and each took a computer search at the edge of what was feasible. At order four, the smallest size at which the box rule means anything, the same searches take a second, and they show the shape of every answer before the numbers get large.

Half of the squares of order four #

A Sudoku of order four — sometimes called Shidoku — has four rows, four columns and four 2×2 boxes, and uses the digits one to four. There are 576 Latin squares of order four, counted on the way to the reduced squares, and they are few enough to build every one and test each box.

Exactly half pass, 288 of them. The count can be built up by hand, and building it shows where the box rule bites. The top-left box can be filled in $4! = 24$ ways. The first row’s other two cells must hold the two digits the first row still lacks, in either order; the second row’s other two cells must hold the digits the second row lacks, which are exactly the first row’s opening pair, in either order. So there are $24 \times 2 \times 2 = 96$ top halves, and the search confirms 96.

The bottom half is where the rule does something unexpected. Each column of the bottom half must hold the two digits its column lacks, so each bottom-half column is filled from a known pair, and the two bottom boxes must each contain all four digits. When the right-hand top box stacks the same two pairs of digits in its columns as the left-hand box does, the bottom half can be filled in four ways; when it stacks different pairs, in only two. Half of the 96 top halves are of each kind, and $48 \times 4 + 48 \times 2 = 288$. The search checks that rule for every one of the 96, not only the total.

The cyclic square — the addition table of the whole numbers modulo four, one of the two groups of that order — fails for a transparent reason. Its rows are shifts of one another by one place, so its top-left box contains $1, 2$ above $2, 3$, and the digit 2 appears twice. A Latin square built by shifting rows is as far from satisfying the box rule as a Latin square can be, because shifting by one keeps neighbouring digits together.

Four clues, and no fewer #

A puzzle is a set of given cells whose digits leave exactly one grid consistent with them. At order four the question of how few clues a puzzle can have is a finite search in the most literal sense: for every set of cells and every grid, ask whether any other grid agrees with it on those cells.

Three clues never suffice. There are 560 ways to choose three cells, and for each one the 288 grids fall into groups that agree on those cells; no group ever has exactly one member. Four clues can suffice, and there are 25,728 four-clue puzzles, each a set of four cells together with the one grid it determines. The drawn one gives two digits in the top row and two in the third, and everything else follows by elimination.

Part of that can be seen without the search. If two of the four digits never appear among the clues, then swapping those two digits everywhere in a completion gives a different completion that agrees on every clue, so the puzzle is not unique. A puzzle must therefore mention at least three of the four digits. Three clues can just manage that, one of each of three digits, and for that case the argument has nothing to say. The search covers it, and finds that even three different digits in three cells always leave some second grid that fits.

That digit-swapping argument is the one that works at every order, and it gives a lower bound at once: a puzzle of order nine needs at least eight clues, since with seven or fewer two digits are missing and can be swapped. The truth is much larger. Gary McGuire, Bastian Tugemann and Gilles Civario proved in 2012 that no Sudoku of order nine has a unique solution with sixteen clues, by checking every one of the essentially different grids for a sixteen-clue set that pins it down — a computation of about seven million processor-hours. Tens of thousands of seventeen-clue puzzles are known, so seventeen is the answer.

Every puzzle must touch every trap #

The search for the fewest clues has a cleaner formulation than trying every set of cells, and it is the one that made the order-nine answer computable. Take a grid $G$ and any other grid $H$. The cells where they differ form a set that every puzzle for $G$ must include a clue from: if no clue lies in those cells, the clues cannot tell $G$ from $H$. Such a set is called unavoidable, and a set of clues pins $G$ down exactly when it contains a cell of every one of them. Finding the fewest clues is finding the smallest set of cells that meets every unavoidable set — a hitting-set problem.

At order four the smallest unavoidable sets have four cells: two different grids always differ in at least four places, and every grid has four or eight others that differ from it in exactly four. A typical one is a rectangle of four cells, two in each of two boxes, holding $a, b$ above $b, a$ — swap them and the grid is still a grid. Every puzzle must put a clue in every such rectangle, and the searches above are, in effect, finding the cheapest way to do it.

That reformulation is what McGuire, Tugemann and Civario used at order nine. For each of the $5.47$ billion essentially different grids they listed its small unavoidable sets and then searched, cleverly pruned, for a set of sixteen cells meeting all of them. No grid had one. The certificate is a list of unavoidable sets for each grid that no sixteen cells can hit, and the only way to check it is to repeat the computation.

Two grids in disguise #

Many of the 288 grids are the same grid, rearranged. The rules of Sudoku do not care which digit is called which, so relabelling the digits of a grid gives a grid. They do not care about the order of the two bands of rows, or of the two rows within a band, or of the two stacks of columns, or of the two columns within a stack, and a grid reflected in its diagonal is still a grid. Every one of those moves carries grids to grids, and two grids related by such moves are the same puzzle wearing different clothes.

Applying the moves over and over from each grid and collecting what is reached sorts the 288 into exactly two families, of 96 and 192. So there are two essentially different Shidoku grids, and every one of the 288 is one of them in disguise. What separates them is not the feature that decided how a top half could be finished. That feature — the two top boxes stacking the same pairs of digits in their columns — holds for every grid of the smaller family and for exactly half of the larger, so it is not preserved by the symmetries: some of them carry grids that have it to grids that do not. The search is what settles that there are two families, and it checks the half-and-half split as well.

At order nine the symmetry group has $9! \times 2 \times 6^8 = 1{,}218{,}998{,}108{,}160$ elements — relabellings, band and stack shuffles, row and column shuffles within them, and the reflection — and Ed Russell and Frazer Jarvis counted the families in 2006 using Burnside’s lemma, which counts orbits by averaging the number of grids each symmetry leaves fixed. There are $5{,}472{,}730{,}538$ essentially different grids. The count of families is much smaller than the count of grids divided by the size of the group, because some grids are fixed by some symmetries — the same subtlety that makes counting necklaces harder than dividing by the number of rotations.

The top band, and an estimate within a fifth of a per cent #

The count of order-nine grids is where Sudoku’s mathematics started in earnest, and its first step is small enough to redo. Fix the top-left box as the digits one to nine read row by row, and count the ways to finish the top three rows.

The search finds $2{,}612{,}736 = 56 \times 6^6$ completions. The factor $6^6$ is the freedom to reorder the three digits within each of the six rows of the two unfinished boxes; the 56 counts which sets of three digits go in each row of those boxes, and it splits into the two cases the order-four grid already showed: rows that keep the first box’s triples together, and rows that mix them. Multiplying by the $9!$ ways of filling the first box gives $948{,}109{,}639{,}680$ possible bands.

Bertram Felgenhauer and Frazer Jarvis carried that computation through the rest of the grid in 2005, grouping the bands into classes that complete in the same number of ways and counting the completions of each class by computer. The total is $6{,}670{,}903{,}752{,}021{,}072{,}936{,}960$, about $6.67 \times 10^{21}$. For comparison there are about $5.52 \times 10^{27}$ Latin squares of order nine, so roughly one Latin square in eight hundred thousand also satisfies the box rule — far from the half that passed at order four.

What is striking is how well a naive estimate does. Treat a grid as nine rows, each a random arrangement of the digits. The chance that three random rows form a legal band is the band count divided by $(9!)^3$. Pretend that the three bands and the three stacks succeed or fail independently, and the number of grids should be $(9!)^9$ times that chance to the sixth power: $6.657 \times 10^{21}$, within a fifth of a per cent of the truth. Nothing justifies the independence assumption except that it works, and nobody has a proof that explains why it works so well.

Regions that are not boxes #

Sudoku was not the first appearance of this object. In 1956 the agricultural statistician W. U. Behrens proposed gerechte designs — German for “fair” — for field trials. A Latin square design plants $n$ treatments on an $n \times n$ plot so that every treatment appears once in each row and each column, which balances out soil that improves from north to south or from east to west. A gerechte design adds a partition of the plot into $n$ regions, perhaps following a drainage channel or a change of soil, and asks that every treatment appear once in each region too. Sudoku is the gerechte design for the partition into boxes.

The shape of the regions decides everything. The boxes admit 288 squares, the jigsaw partition in the middle admits 96, and the partition on the right admits none, for a reason visible in one glance. Its first region takes three cells of the top row and one cell of the second row, beneath the fourth. The top row’s fourth cell must hold the one symbol the first three lack, and so must the region’s fourth cell, which sits directly beneath it in the same column. No Latin square can do that. A region that nearly covers a row forces a clash in a column, and the partition fails before a single symbol is placed.

Which partitions admit a gerechte design at all is a question with no general answer, and it has the same flavour as the existence questions the rest of this subject keeps raising: a counting condition that is necessary, and a structure that sometimes refuses to cooperate. Rosemary Bailey, Peter Cameron and Robert Connelly showed in 2008 that the most symmetric Sudoku grids come from the affine geometry over the field of three elements, and that those grids are closely tied to error-correcting codes — the connection the next essay makes for orthogonal squares in general.

What the grids cannot show #

They cannot show order nine. Every order-four number here was found by exhaustion: all 576 squares built, all 560 three-cell sets tried against all 288 grids, every symmetry applied. The order-nine numbers — $6.67 \times 10^{21}$ grids, $5.47$ billion families, seventeen clues — are quoted from computations that are far too large to rerun, and they are exactly the kind of result a proof that checks every case makes: correct, published, independently rechecked, and not surveyable by any reader. The band count is the one piece of the order-nine story recomputed here.

They cannot show difficulty. Whether a puzzle is hard for a person depends on which deductions a solver can see, and no count of clues measures it. The general problem — given a partly filled grid of order $n^2$, can it be completed? — was shown NP-complete by Takayuki Yato and Takahiro Seta in 2003, which means there is no known method that is fast for every large grid, and the published puzzles are the lucky ones that yield to a chain of simple eliminations.

And they cannot show why the estimate works. The independence estimate lands within $0.2\%$ of the true count, and so do similar estimates for larger Sudoku-like grids that have been counted. Whether that accuracy is a coincidence of small numbers or a theorem waiting to be proved is not known.

Where the boxes lead next #

Orthogonal Latin squares answered Euler’s question about thirty-six officers, and a field supplies as many of them as the order allows; a Sudoku grid can be paired with an orthogonal mate that is also a grid — Euler’s question with boxes. More interesting is the step from squares to codes. A set of orthogonal squares, read one cell at a time, is a list of words in which any two words agree in at most one place, and that list turns out to be an error-correcting code as good as a code of its size can be — the plane hiding in the squares read one more way. That is where the next essay goes, and it explains why the squares a field builds and the codes a field builds are the same object.

One more rule, and every question gets harder #

A Sudoku grid is a Latin square in which every box also holds each symbol once. At order four the extra rule keeps 288 of the 576 squares — 96 top halves, finishing in two ways or four according to how the boxes stack their pairs — and the symmetries of the rules sort them into just two essentially different grids. No three clues ever force a unique grid and 25,728 four-clue sets do.

At order nine the same questions were answered by computer: $6{,}670{,}903{,}752{,}021{,}072{,}936{,}960$ grids, $5{,}472{,}730{,}538$ families, and no puzzle with fewer than seventeen clues. The top band’s $56 \times 6^6$ completions are small enough to count again, and an estimate that treats bands and stacks as independent comes within a fifth of a per cent of the full count, for reasons nobody can prove. Behrens’s gerechte designs are the same object with regions of any shape, and the shape can make the count anything from 288 to none.

Adding one condition to a structure already understood is the cheapest way to make every question about it new again.