The Mathematics of Sudoku: How Many Grids, Why 17 Clues

The mathematical family of Sudoku is much older than the puzzle itself. An n×n grid that obeys only the row and column rule, with no box condition, is called a Latin square, and Leonhard Euler studied them systematically in a long paper published in 1782. The question Euler pursued there was whether thirty-six officers, from six different regiments and of six different ranks, could be arranged in a 6×6 square so that every row and every column held exactly one officer of each regiment and each rank. That amounts to finding two orthogonal Latin squares at once. Euler guessed that no such arrangement exists and he was right. For 6×6 the answer was proved negative in 1900 when Gaston Tarry went through every case one by one. The more ambitious version in which Euler extended this guess to other orders was refuted in 1959.

Latin squares took a long time to reach the newspapers. In the 1890s some French newspapers ran number squares, but the form we know today, a 9×9 grid with the box rule and a few digits given in advance, appears in the United States in 1979. Puzzles prepared by Howard Garns, a retired architect from Indiana, were printed in Dell's pencil puzzle magazine under the name "Number Place". In 1984 the Japanese publisher Nikoli discovered the puzzle and gave it a long name meaning roughly "the digits must remain single", which Nikoli's founder Maki Kaji shortened, and that is how the name Sudoku was born. Its spread around the world began when Wayne Gould, a retired judge from New Zealand, wrote a program that generated the puzzles by computer. The Times printed its first Sudoku on 12 November 2004, and within a few months the puzzle had settled onto the back pages of nearly every newspaper.

Seen from mathematics, Sudoku is a Latin square with one more condition added. I will show with numbers in the counting section how much that single extra condition changes, but first I want to fix the language I will use, because it will not change until the end of the article.

I number rows from top to bottom 1 to 9 and columns from left to right 1 to 9. I write a cell in the notation of J. F. Crook, who published a pencil-and-paper algorithm in 2009, as c(row, column). So c(6,7) is the cell where the sixth row meets the seventh column. Like Crook, I number the boxes in typewriter order, starting at the top left and going left to right and top to bottom from 1 to 9, so the middle box is box 5.

A cell must obey three units, its row, its column and its box. I will call rows, columns and boxes together units, and I note now that a grid has 27 units. Two larger structures will be useful in the counting section. Three stacked rows, that is rows 1-2-3, 4-5-6 or 7-8-9, I call a band, and three adjacent columns a stack. Each band consists of three boxes, and so does each stack.

Finally, two words need to be kept apart. A filled grid, all 81 cells filled in accordance with the rule, is a solution or completed Sudoku. A puzzle is a grid with digits written in some cells and the rest empty, and I call those digits clues. The question "how many Sudokus are there" counts filled grids, while "how few clues" is about puzzles. Not mixing up these two questions will make several subtle points later easier to see.

Counting the small version by hand before moving to the 9×9 grid shows from the start why the big calculation is hard. 4×4 Sudoku, which some books call Shidoku, has four 2×2 boxes and digits running from 1 to 4. The rule is the same, every row, column and box contains 1, 2, 3, 4 once each.

I can write the first row however I like, since no rule has come into play yet, and there are 4! = 24 options there. Noticing a symmetry among these 24 options makes my job easier. Whether the first row is 2 4 1 3 or 1 2 3 4, I can pass from one to the other by renaming the digits. If I rename 2 as 1, 4 as 2, 1 as 3 and 3 as 4, the row 2 4 1 3 becomes 1 2 3 4, and this renaming carries every valid filling of the rest of the grid to another valid filling. So it is enough to count the grids whose first row is 1 2 3 4 and multiply the result by 24.

When the first row is 1 2 3 4, the first two cells of the second row lie in the same box and cannot take 1 and 2, so they are forced to be {3, 4}. The last two cells, for the same reason, are {1, 2}. Since each box has two orderings, the second row can be written in four ways.

Things get interesting with the bottom two rows, and the whole difficulty of the big calculation appears here in miniature. When filling the third and fourth rows, each column has two digits unused in its top half, and these two digits must settle into the two cells below in some order. The bottom boxes also each need four different digits. When the second row is 3 4 1 2, the top half of the first column holds {1, 3} and the top half of the third column holds {3, 1}. These two columns have the same missing digits, {2, 4} in both. The same holds for the second and fourth columns, both missing {1, 3}. Because the columns pair up two by two in this way, four different completions of the bottom half appear.

When the second row is 3 4 2 1, however, the top halves of the columns are {1, 3}, {2, 4}, {3, 2} and {4, 1}, and all four missing pairs are different. This time there is no pairing between columns and the options lock into one another. When I write a digit in one cell, the choice forces another cell through the column, that cell forces another through the box, and at the end of the chain only two completions remain. The same reasoning applies to 4 3 1 2 and 4 3 2 1, and you can see every completion one by one in the diagram below.

Altogether there are 4 + 2 + 2 + 4 = 12 completions, and the number of filled 4×4 Sudokus is 24 × 12 = 288. I also confirmed this number by having a computer check every possibility, and the result does not change.

This small calculation teaches two lessons of the big one in advance. First, the count cannot be made by multiplying options cell by cell. The sum 4 + 2 + 2 + 4 is not a product, and the reason is that how many options remain in a cell depends not just on how many digits were written in earlier cells but on exactly which digits they were. With second row 3 4 1 2 the bottom half has four options, with 3 4 2 1 it has two, yet in both cases the same digits were written in the second row. That is exactly why there is no tidy product formula for 9×9 either.

The second lesson concerns symmetries. Renaming the digits, swapping two rows within a band, swapping two bands, doing the same with columns and stacks, or reflecting the grid in the diagonal from top left to bottom right all carry a valid Sudoku to another valid Sudoku. If I count grids that can be transformed into one another this way as the same, the 288 grids turn out to come from just two different structures. Their numbers of copies are not equal either, one has 96 copies and the other 192. Unequal copy counts show that the first structure maps back onto itself under some transformations, that is, it is more symmetric. I will meet the same phenomenon again when counting "essentially different" 9×9 Sudokus.

One step up, 6×6 gives a feel for the rate of growth. In 6×6 Sudoku, which is also common in newspapers, the boxes are not squares but rectangles of 2 rows and 3 columns. Crook calls these irregular Sudokus in his paper and lists the regular ones with box side m in a table. For m = 2 you get the 4×4 grid with 16 cells, for m = 3 the 9×9 grid with 81 cells, for m = 4 the 16×16 grid with 256 cells, for m = 5 the 25×25 grid with 625 cells and for m = 6 the 36×36 grid with 1,296 cells. When I had a computer count the filled 6×6 Sudokus, I got 28,200,960. Going from 4×4 to 6×6, the number of cells rises from 16 to 36 and the number of grids grows about a hundred thousand times. It is not hard to guess where this number will go at 9×9.

The question is simple. In how many different ways can I fill an empty 9×9 grid according to the rule? Rather than giving the answer straight away, I want to start with estimates that get steadily tighter, because seeing where and why each estimate goes wrong is the best way to understand why the true number, when it comes, is so hard to find.

Without any rule

The first crude estimate looks at no rule at all. I imagine filling the grid starting at the top left corner, row by row, left to right. I can write any of 9 digits in the first cell. The second cell also has at most 9 options, so there are at most 9 × 9 = 81 ways to fill the first two cells. The third cell multiplies this by 9 again, giving at most 9 × 9 × 9 ways for the first three cells. Carrying the same reasoning to the end of the 81 cells, I find that a filled grid can be written in at most

different ways. That is roughly a thousandth of the 10⁸⁰ usually quoted for the number of atoms in the observable universe. Mathematicians call an estimate like this an upper bound. It does not say what the true number is, it only guarantees that the true number cannot be larger. The true number could be much smaller, and as I will show shortly, it is in fact much smaller.

Adding the row rule

Now I bring in a single rule, each row contains each digit at most once. Filling a row from left to right, the first cell has 9 options, the second has at most 8 because the digit in the first cell can no longer be used, the third 7, and the last cell just 1. So a row can be written in at most 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 9! = 362,880 ways. Even if the nine rows were filled independently, the total could not exceed this, and the new upper bound is the following.

One rule brought a drop of 27 digits. It is useful for later steps to show this as a table that writes in each cell the most options that cell can have. Multiplying the 81 numbers in the table gives the upper bound.

Why such a big improvement? Because in the first estimate I counted 9 options even for the last cell. But once the first eight cells of a row are filled, only one digit can go into the ninth. The number of ways to fill the first eight cells of a row is the same as the number of ways to fill the whole row. The crude estimate does not see this simple fact and kept multiplying by 9 at every cell.

Twelve cells that slip through

The row table still misses something. When filling the grid row by row, there are cells besides the end of each row that have only one option left. The ninth, that is the last filled, cell of a box is condemned to a single digit, since the other eight cells of the box are full. The last cell of box 1 is c(3,3), of box 2 c(3,6), of box 4 c(6,3), of box 5 c(6,6). The last cells of boxes 3, 6 and 9 are already at the end of a row, so their table value is 1. Likewise the last cell of a column has a single option, since the eight cells above it are full. The last cells of the columns sit in the ninth row, and apart from the row's own last cell c(9,9) there are eight of them. The last cells of boxes 7 and 8, c(9,3) and c(9,6), are among those eight.

In these twelve cells the table counts 7, 4, 7, 4, 9, 8, 7, 6, 5, 4, 3, 2 options, whereas in reality each has one. So the previous upper bound overcounts by a factor of at least 7 × 4 × 7 × 4 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 = 9 × 8 × 7³ × 6 × 5 × 4³ × 3 × 2, and the new upper bound is

Another nine digits have dropped. But this method has a limit, since I only caught cells with a single option. Better is to take all three rules into account separately for every cell.

Three tables and their minimum

Next to the row table I place two more. In the column table I write in each cell the most options that cell has according to the column rule. Since I fill the grid from top to bottom, cells in the first row have 9 options, those in the second row 8 because one cell of their column is already filled, and those in the last row 1. In the box table each box repeats the sequence 9, 8, 7, 6, 5, 4, 3, 2, 1 internally, because the nine cells of a box are also filled row by row.

Whatever the true number of options in a cell is, it cannot exceed any of the three values. The row rule says at most so many, the column rule says at most so many, the box rule says at most so many, and the true value must satisfy all three at once. So taking the smallest of the three values for each cell is legitimate. The fourth table shows these minima, and the product of its 81 numbers becomes the new upper bound. In the selector below you can see the four tables and the product of each.

The product of the 81 numbers is about 1.53 × 10³¹. I am 46 digits below where I started, about a 10⁴⁶th of 9⁸¹. But the true number is still about 2.3 billion times smaller than this, and a single example is enough to see where the gap comes from.

What the table cannot see

Suppose I filled the first row as 3 1 5 7 6 2 9 4 8 and the first five cells of the second row as 8 9 2 4 5, and it is now the turn of the sixth cell of the second row, c(2,6). According to the minimum table this cell has at most four options. In reality c(2,6) sees 8, 9, 2, 4 and 5 in its row, sees 7, 6, 2, 4, 5 in its box and sees 2 in its column. Only 1 and 3 remain. The table says four, the truth is two.

The difference comes from this. When computing the table value I applied each rule separately. The row rule said "five digits are used in this row, four remain", the box rule said "five digits are used in this box, four remain", and I took the smaller, four. But the digits used in the row and the digits used in the box are not the same digits, and their union excludes far more. The rules do not work one at a time but together, and together they are much stronger than any of them alone. It is impossible to fit this interaction into a table that writes a single number per cell, because the size of the interaction depends on exactly which digits were written in earlier cells. Remember how in 4×4 the second row being 3 4 1 2 or 3 4 2 1 changed the bottom half. The same phenomenon is at work here on a much larger scale.

While the tables look at each cell separately, the road to the right answer runs through bigger pieces, especially bands. I can count by hand the number of ways to fill the first band, the top three rows, according to the rule, and this count is both pretty in itself and the first step of Felgenhauer and Jarvis's computer calculation.

Counting the first band

I use the relabelling symmetry here as well. Whatever the first row is, I can make it 1 2 3 4 5 6 7 8 9 by giving the digits new names. So if I fix the first row that way and count the other two rows, multiplying the result by 9! gives all bands.

With the first row fixed, what matters is which set of digits the second row puts into each box. The left box's first row holds {1, 2, 3}, the middle box's {4, 5, 6}, the right box's {7, 8, 9}. The second row of the middle box cannot take {4, 5, 6}, so it collects its three digits from {1, 2, 3} and {7, 8, 9}. There are four possibilities.

First, the second row of the middle box is entirely {7, 8, 9}. The whole second row must contain each digit from 1 to 9 once, the left box cannot take {1, 2, 3}, the middle box has taken {7, 8, 9}, and what remains is {4, 5, 6} for the left box and {1, 2, 3} for the right box. The third row is then determined. Second, the middle box's second row is entirely {1, 2, 3}, which likewise leads to a single arrangement. I call these the pure cases, and there are two of them.

In the third possibility, the middle box's second row takes one digit from {1, 2, 3} and two from {7, 8, 9}. There are 3 choices for which digit comes from {1, 2, 3} and 3 for which two come from {7, 8, 9}. Once that choice is made, the left box's second row cannot take {1, 2, 3}, so it must take the single digit left over from {7, 8, 9} and two digits from {4, 5, 6}, giving 3 more options. The right box's second row fills up with what is left. In total 3 × 3 × 3 = 27 arrangements. The fourth possibility mirrors the third, with the middle box taking two digits from {1, 2, 3} and one from {7, 8, 9}, and again gives 27 arrangements. I call these the mixed cases.

Altogether there are 2 + 27 + 27 = 56 content arrangements. In each arrangement, each of the six box pieces of the second and third rows, six groups of three digits, can be written in 3! = 6 orders internally, and these orderings break no rule, because inside a band the column rule only asks that a digit not repeat in the three rows of a box, which the box rule already ensures. So with the first row fixed, the band can be completed in 56 × 6⁶ = 2,612,736 ways, and together with the 9! ways of writing the first row, the number of filled bands is the following.

I also checked this number with a separate computer count.

The calculation of Felgenhauer and Jarvis

In 2005 Bertram Felgenhauer and Frazer Jarvis start exactly here. What they fix is the first box rather than the first row. By relabelling digits, the box 1 of every grid can be brought into the form 1 2 3 / 4 5 6 / 7 8 9, and that is why the total is exactly divisible by 9!. The problem reduces to finding how many ways the rest of the grid can be completed with box 1 fixed.

With the first box fixed, boxes 2 and 3, the rest of the band, have 2,612,736 different fillings. The key idea of Felgenhauer and Jarvis is to notice that most of these fillings are equivalent as far as the number of completions of the bottom six rows is concerned. Swapping boxes 2 and 3, permuting the columns inside a box, swapping rows of the band and relabelling digits do not change the number of ways to complete the bottom six rows. Gathering the band fillings that transform into one another under these operations into one class, the 2,612,736 fillings come down to 44 classes. They take a single representative from each class, have the computer count how many ways the bottom six rows can be completed for it, multiply by the size of the class and add everything up. The resulting number is this.

This number is about a 2.3-billionth of the best upper bound I found by hand, 1.53 × 10³¹, and about a 3 × 10⁵⁵th of the crudest bound, 9⁸¹. I also picture a newspaper printing one Sudoku a day. If each puzzle's solution were a different filled grid, the paper could keep going for more than a billion times the current age of the universe. For anyone wondering whether a newspaper will run out of Sudokus, the answer is clear.

Within 0.2 percent by pencil and paper

It is possible to get surprisingly close to this number with pencil and paper, and I think this is the most elegant moment in the whole counting story. I imagine choosing each row independently as a random permutation of the nine digits. That gives (9!)⁹ grids, all of which already satisfy the row rule. I want to estimate what fraction of these also satisfy the column and box rules.

The probability that three random rows together form a valid band is the number of valid bands divided by the number of triples of random rows.

So about one in 50,000 random triples of rows forms a valid band. The grid has three horizontal bands and each must be valid. By symmetry I use the same probability for the three vertical stacks. A grid is a Sudoku only if all six structures are valid. If I assume these six conditions are independent, which they are not, since the same cells belong to both a band and a stack, my estimate becomes the following.

As far as I know there is no rigorous explanation for why this estimate works so well. The band and stack conditions are dependent, but the dependence works both ways, sometimes raising the probability and sometimes lowering it, and in the end the effects seem to largely cancel. It is an observation, not a proven result.

Comparison with Latin squares

One way to see how powerful the box rule is, is to leave it out. The number of 9×9 grids obeying only the row and column rules, the Latin squares of order nine, is this.

Every Sudoku is a Latin square but not the other way round. The ratio is 6.67 × 10²¹ / 5.52 × 10²⁷ ≈ 1.2 × 10⁻⁶, so roughly one Latin square in 830,000 is a Sudoku. The box rule is no innocent decoration on top of the row and column rules, it cuts the number by six digits.

How many truly different Sudokus are there?

Most of the 6.67 × 10²¹ grids can be regarded as copies of one another. Every transformation I saw for 4×4 also works for 9×9, and here their numbers are much larger.

There are 9! = 362,880 ways to relabel the digits. I can order the three bands in 3! = 6 ways. I can order the three rows inside each band in 3! ways too, which for three bands gives (3!)³ = 216. The same operations on stacks and columns give 6 and 216 options. Finally there is reflecting the grid in the diagonal, reflect or not, 2 options. The number of transformations other than relabelling is

and together with relabelling the total is 3,359,232 × 362,880 = 1,218,998,108,160 transformations. Rotating the grid by 90 degrees seems missing from this list but is actually there, since a rotation is a reflection combined with reversing the order of the rows.

If every grid had 1,218,998,108,160 distinct copies under all transformations, dividing the total by this number would give the number of essentially different grids. I do the division.

That the result is not a whole number is information in itself. The division could only come out clean if every grid produced completely distinct copies under all transformations. A fractional result proves, without showing a single example, that some grids map back onto themselves under some transformations, that is, symmetric Sudokus exist. Such a grid has fewer distinct copies, and plain division undercounts them. In 4×4 I saw two structures with 96 and 192 copies, and the same thing happens here in a far more complicated way.

The correct count uses a tool from group theory called Burnside's lemma. The lemma says the number of distinct structures equals the average, over all transformations, of the number of grids each transformation leaves unchanged. Most transformations leave no grid unchanged, some fix a small number of grids, and the calculation rests on counting those one by one. In 2006 Ed Russell and Frazer Jarvis do this calculation and find the number of essentially different filled Sudokus to be this.

About 282,000 more than plain division. Roughly five and a half billion structures. This number will come back shortly in the 17-clue story, because the computation proving there is no 16-clue puzzle examines exactly these five and a half billion grids one by one.

Imagine you are working on a puzzle a friend made by hand. Let it be something like the one below.

After a while two questions start to nag at you. Does this puzzle have a solution, and if so, is it unique? Both sound simple, but in general they are very hard to answer without a computer. This puzzle has a solution, but not a unique one. I have put two of its solutions side by side above, and if you look closely the two differ in only four cells. I will show shortly why those four cells form an exact rectangle. A unique solution with fourteen clues is impossible anyway, but why that is so is the subject of a 2012 proof I describe at the end of this section.

First I want to separate the two questions. The existence question asks "is there at least one solution", the uniqueness question "is there at most one". Nearly all puzzles printed in newspapers and books are made to have a unique solution, and most solvers regard this as a mark of quality. But it is not always so. Crook tells in his paper how the final puzzle of the 2007 World Sudoku Championship had exactly two solutions. I will return to that story later.

Three empty cells always give a unique solution

I approach uniqueness from the extreme end. If only three empty cells remain in the grid, the other 78 cells are filled according to the rule, and I know the puzzle has at least one solution, then the solution is certainly unique. To see this, it is enough to show that at least one of the three empty cells is alone in its row or alone in its column.

I assume the opposite, that none of the three cells A, B and C is alone in its row or its column. A shares its row with someone, say B. A must also share its column with someone, and that cannot be B, since two cells in the same row and the same column would be the same cell. So A and C are in the same column. B also shares its column with someone, and since it is in the same row as A, that someone cannot be A, so it is C. Then C is in the same column as both A and B, so A and B are in the same column too, and A and B lie in the same row and the same column. That is the contradiction.

The value of the cell that is alone in its row or column is determined automatically as the one digit missing from that row or column. Since I know the puzzle has a solution, I am also sure that digit fits the cell. Once I write it, the situation for the two remaining empty cells is even easier. The two cells are either in the same row, in the same column, or in neither. Whichever it is, each is at least alone in its row or its column, because if they share a row they are in different columns and alone in their columns. So each is condemned to a single digit and the solution is unique.

Four empty cells are not enough

With four empty cells the same guarantee disappears, and seeing why is the key to a structure that will come up again in the rest of the article. The grid below appears as an exercise in the Cornell notes. When everything that can be filled with easy techniques is filled, four empty cells remain, and those four cells can be filled in two different ways.

The four cells are c(1,3), c(1,4), c(3,3) and c(3,4). They form a rectangle spread over two rows, two columns and two boxes, boxes 1 and 2. Each row is missing {1, 2}, each column is missing {1, 2}, and each box is missing {1, 2}. When I write 1 in one corner, the opposite corner also gets 1 and the other two corners get 2, and both diagonal arrangements obey every rule.

The rectangle splitting into exactly two boxes is essential here. If the four corners fell into four different boxes, that is if the rectangle spanned two bands and two stacks, each box would have only one empty cell and the box rule would force each cell to a single digit. If the four corners were in a single box, the box would demand four different digits even though the corners share rows and columns, and the diagonal arrangement would not work. The rectangle must cross two rows and two columns, its corners must fall two by two into two boxes, and the digits at the corners must match diagonally. Some puzzle books call this pattern a deadly rectangle, because if such a structure exists in a puzzle's solution and the puzzle gives no clue in it, the puzzle is doomed to two solutions.

Unavoidable sets

This observation generalises. I consider a group of cells in a filled Sudoku. If the digits in those cells can be rearranged, the digits themselves staying the same but their positions changing, so that the grid is still valid, that group of cells is called an unavoidable set. The name comes from its consequence. A puzzle with a unique solution must give at least one cell of every unavoidable set of its solution as a clue. Otherwise the digits in that set swap places without touching any clue and a second solution is born. The puzzle setter cannot avoid these sets and must leave at least one clue in each.

The four-cell rectangle above is the smallest kind of unavoidable set. Nothing smaller is possible, and the three-empty-cell proof says exactly this. If every solvable puzzle with three or fewer empty cells has a unique solution, there is no unavoidable set of three or fewer cells. Not every grid has a four-cell unavoidable set, but larger ones always exist, and a typical grid has hundreds. That is also why the two solutions of your friend's fourteen-clue puzzle differ in an exact rectangle. That grid has a four-cell unavoidable set and the puzzle gave no clue in it.

The eight-digit rule

Another short and pleasant result follows from the same idea. Among the clues of a uniquely solvable puzzle, at least 8 of the 9 digits must appear. If two digits, for example 5 and 7, never appear among the clues, then in any solution I can turn every 5 into 7 and every 7 into 5 without touching the clues, and the new grid also obeys the rules, because every unit still has one 5 and one 7. So I get a second solution. In the language of unavoidable sets, the 18 cells holding the 5s and 7s in the solution form an unavoidable set and the puzzle put no clue in any of them. Agnes Herzberg and Ram Murty prove this result in 2007 in the language of graphs, and I will return to that language at the end of the article.

It is worth noticing that the rule says eight, not nine. The ninth digit not appearing among the clues does not by itself spoil uniqueness, because a swap needs two missing digits and a single missing digit has no partner to trade places with. Eight digits are of course not enough for uniqueness, only necessary. Mathematics calls such conditions necessary rather than sufficient.

The proof of 17

For years the number of clues in uniquely solvable puzzles did not drop below 17. Gordon Royle, a mathematician at the University of Western Australia, collected 17-clue puzzles sent in from around the world from 2005 onward, and the collection eventually reached about 49,000 different puzzles. One of them is below. Not a single 16-clue puzzle ever entered the collection.

Still, finding nothing does not prove there is nothing. Perhaps 16-clue puzzles existed and were just very rare. So for years the question stayed an open conjecture. Many sources, the Cornell notes included, still say "the minimum number of clues is probably 17", but that sentence is now out of date.

A quick calculation shows why brute-force search does not work. If I took one filled grid and wanted to test every subset of 16 of its cells to see whether it formed a uniquely solvable puzzle, I would have to try the C(81, 16) ≈ 3.4 × 10¹⁶ ways of choosing 16 cells out of 81 one by one. And this has to be done for each of the 5.47 billion essentially different grids. Even if I could check a single puzzle for uniqueness in a millisecond, the total time would far exceed the age of the universe.

In early January 2012 Gary McGuire, Bastian Tugemann and Gilles Civario publish the work that settles the question, and the paper appears in Experimental Mathematics in 2014. The skeleton of the method is built from the unavoidable sets above. They take each of the 5,472,730,538 essentially different grids in turn and first look for unavoidable sets in each. In a typical grid they find about 360, and they report that this takes about 30 seconds per grid. Then they ask the following question. Is there a selection of 16 cells that touches every one of these sets in at least one cell?

In computer science this is called the hitting set problem. A family of sets is given and a small selection is sought that "hits" every set in the family with at least one element. If a uniquely solvable 16-clue puzzle existed, its 16 clues would have to hit every unavoidable set of the grid. So they first find the 16-cell selections that hit all unavoidable sets, and the unavoidable sets narrow the search enormously from the start, then they check only these candidates for uniqueness. In no grid does a 16-cell selection pass the hitting set test and also give a unique solution.

The whole computation takes about 7.1 million core hours on the Stokes machine at the Irish Centre for High-End Computing. With a single processor core that would be about 800 years. The paper also has a nice example showing, using more complex structures where several unavoidable sets in the same grid combine, that some grids can be proven without a computer to need at least 18 clues.

So 17 stops being a conjecture and becomes a theorem. 16 clues are never enough, and a unique solution with 17 clues is possible. That the 17 clues of the puzzle above contain all nine digits is no accident either, the eight-digit rule already requires at least eight of them.

The existence question

The existence question has a plainer answer. Whether a grid can be completed can always be decided, because there are finitely many ways to fill the grid and scanning them all systematically always gives a result. The problem is not whether the answer exists but how much effort it takes. The next section is exactly about how to organise that effort.

The most basic requirement of an algorithm is that it stops. "Looking at the puzzle and trying things" is not an algorithm for that reason, a person might never finish, might repeat the same attempts again and again or might give up somewhere. A real algorithm for Sudoku must take a partly filled grid and, after a finite number of steps, stop either by finding a solution or by showing there is none. The simplest method that does this is the direct continuation of the "fill cell by cell" idea from the counting section.

The simple solving algorithm

The Cornell notes call this method the "simple solving algorithm". In computer science it is called backtracking. The steps are as follows.

1. Number the empty cells in typewriter order, left to right and top to bottom.
2. Make the first cell in the list the current cell.
3. Write 1 in the current cell. If this creates a repeat in a row, column or box, try 2, then 3, and continue until you either find a digit that breaks no rule or try 9 and still meet a violation.
4. If you found a digit that obeys the rule and this is the last cell in the list, the puzzle is solved. If it is not the last cell, make the next cell in the list the current cell and return to step 3.
5. If every digit up to 9 is a violation and this is the first cell in the list, the puzzle has no solution. If it is not the first cell, empty this cell, go back to the previous cell in the list, continue trying there by increasing its digit by one and make the checks of step 3.

It is not hard to see the method is correct. As the algorithm fills cells in order, it tries digits from small to large for each cell, and when all digits are exhausted in one cell it moves on to the next digit of the previous cell. This means scanning the list of filled grids in lexicographic order, the order in which words are arranged in a dictionary, and during the scan it never continues a partial filling that breaks the rule. If a solution exists the scan must reach it, because every partial filling in front of it leads either to a solution or a dead end, and the dead ends are finite. If there is no solution the scan exhausts all possibilities and stops when the first cell goes past 9.

Changing the algorithm to find all solutions is easy too. When a suitable digit is written in the last cell, instead of stopping you record the solution, erase that digit and continue the search as if you had hit a dead end. When the scan ends all solutions are recorded. I found the second solutions of the two-solution examples above with this method. For someone making puzzles this change is very useful, because they can check whether a puzzle has a unique solution by seeing whether a second solution turns up.

It is also clear that this method is almost impossible to apply on paper. The number of digits to write and erase, as I will show shortly, runs into the hundreds of thousands. The MATLAB code Paul Meerkamp wrote in 2009 for a summer programme at Cornell solves the "fiendish" puzzle below in about five minutes, and Meerkamp writes that his code is about as fast as a human on most puzzles and much slower on some.

Tightest cell first

A single small change shortens that time incredibly. Choose the next cell not in typewriter order but as the cell with the fewest options at that moment. A cell with one option is really a forced move, and making it immediately narrows the rest of the search without any branching. A cell with zero options tells me I am on the wrong path before I even enter that branch, and the algorithm backs up at once. Typewriter order only notices such a cell when its turn comes, and until then it branches pointlessly in all the cells in between.

Below you can run the two methods side by side on the same puzzles. Both step at the same speed, that is, in every frame each writes or erases the same number of digits. The difference comes entirely from which cell gets chosen.

The numbers tell their own story.

The numbers in the table are the total count of digits written into a cell because they broke no rule. In the opening puzzle the tightest-cell rule fills 42 empty cells with 42 digits, so it never backs up. This means there is a single-option cell at every step, and as I will show shortly, this puzzle is indeed solved by the single-candidate rule alone. In Shortz 301, by contrast, typewriter order writes and erases more than half a million digits while the tightest-cell rule finishes the job with 1,426.

I notice something else. A puzzle a human finds hard and a puzzle a program working in typewriter order finds hard are not the same thing. For typewriter order, difficulty depends on how late wrong choices in the first rows are discovered. A puzzle with an empty first row can be very expensive for typewriter order however full its lower rows are. A human never thinks in typewriter order anyway, the eye goes to the fullest unit, the tightest cell. The tightest-cell rule is, in a sense, human intuition taught to a computer.

The true shape of Sudoku, exact cover

Computer scientists look at Sudoku a little more abstractly, and this view shows both how fast solvers work and how Sudoku is related to other problems. I write every possible move as a triple "row r, column c, digit d". There are 9 × 9 × 9 = 729 such moves. Each move satisfies exactly four conditions.

1. It fills cell c(r, c). There are 81 conditions of this kind, one for each cell.
2. It puts digit d in row r. 81 conditions for 9 rows and 9 digits.
3. It puts digit d in column c. Again 81 conditions.
4. It puts digit d in the cell's box. Again 81 conditions.

There are 324 conditions in total. For example, the move "row 2, column 7, digit 9" fills cell c(2,7), puts 9 in row 2, puts 9 in column 7 and puts 9 in box 3. Solving a Sudoku means choosing 81 of the 729 moves so that each of the 324 conditions is met exactly once. No condition may be met twice, since that would mean two digits in one cell or the same digit twice in a unit, and no condition may be left open. The clues make part of this choice in advance.

This is a general problem called exact cover. Picture a 0-1 table with 729 rows and 324 columns. Each row is a move, each column a condition, and there is a 1 where a move meets a condition. Every row has exactly four 1s. What is wanted is to choose rows so that, laid on top of one another, they leave exactly one 1 in every column. Pentomino puzzles, some scheduling problems and the problem of placing queens on a chessboard fall into the same mould.

In a paper published in 2000, Donald Knuth describes a search method for such problems called Algorithm X, and a data-structure technique he calls "dancing links" for running it efficiently. Algorithm X at each step chooses, among unmet conditions, the one that can be met by the fewest moves, tries one of those moves, temporarily removes all conflicting moves from the table, and puts them all back if it hits a dead end. Dancing links does this removing and restoring almost for free. It is not hard to see that the tightest-cell rule is the Sudoku special case of choosing the condition with the fewest options first in exact cover. The difference is that Algorithm X looks not only at cell conditions but also at conditions like "where can 9 go in row 2", and so it automatically includes the technique humans call a "single place". A 9×9 Sudoku is solved this way in a small fraction of a second.

So is Sudoku an easy problem?

For 9×9, yes. But when I ask the question for general Sudoku the answer changes. Sudoku of size n²×n² with box side n, the family growing as 4×4, 9×9, 16×16, 25×25, was shown to be NP-complete in 2003 by Takayuki Yato and Takahiro Seta. What does that mean?

If I can quickly check a proposed solution to a problem, the problem is in the class NP. Sudoku is like that, checking the 27 units of a filled grid is a job that grows very slowly as the grid grows. Being NP-complete means every problem in NP can be quickly translated into this problem. If a method were found that solves general Sudoku quickly in every case, the same method would quickly solve every problem in NP, the decision version of the travelling salesman problem, the satisfiability of logical formulas, whether a timetable can be built and thousands more. That would mean answering the most famous open question in computer science, whether P equals NP. Most researchers think no such method exists.

Yato and Seta's actual result is a little subtler. They show that deciding whether a puzzle with a known solution has a second solution is also hard. This is a familiar trouble for puzzle setters, because checking that a puzzle has a unique solution is no easier than solving it.

That the 9×9 newspaper puzzle is solved quickly comes not from the nature of the problem but simply from its being small. 81 cells and 729 moves are no trouble for a computer even in the worst case. But if you announced you had written a program that quickly solves 100×100 Sudoku in every case, the mathematical world would hand you a million-dollar prize along with some very serious questions.

Backtracking does not work on paper. Most newspaper puzzles, however, fall to two simple techniques, and I want to define them a little more carefully, because Crook's algorithm is built on top of both.

In the first method I look at cells. For each empty cell I check which digits are already present in its row, column and box and determine the rest, the candidates that could be written in that cell. If a cell has a single candidate left, I write that digit. The Cornell notes call this candidate-checking, and I will call it the single-candidate rule for short. Puzzle books also call the same thing a naked single.

In the second method I look at digits and units. Every unit must contain every digit exactly once. I take a row, column or box and look at how many cells in that unit the digit 1 could go into. If only one cell remains, the 1 goes there. Then I do the same for 2, then for 3, and I go through every unit. The Cornell notes call this place-finding, and I will call it the single-place rule. Books also call it a hidden single.

The two methods look like two faces of the same thing but they are not. The single-candidate rule looks at a cell and says "only 7 can go here". The single-place rule looks at a unit and says "7 can only go into this cell here", and it makes me write the 7 even if that cell has other candidates. They catch different situations, and a good solver uses them alternately. When one stalls the other may find a new digit, and that digit may set the first going again.

Knowing when these two methods are exhausted matters too. If since the last digit was written I have gone through every cell for a single candidate and every unit for a single place for every digit, and found nothing, I am sure these two methods cannot take me further. However long I look the result will not change, because the state of the puzzle has not changed.

The opening puzzle, step by step

The puzzle at the start of the article is a good example of how far these two methods can go. First I write the candidates of every empty cell. Crook calls this list of small digits the mark-up, and I will use that word from now on.

Looking at the mark-up, several cells with a single candidate stand out immediately. As I fill them, I delete the same digit from the mark-up of their neighbours, and new single candidates appear. After the first six steps the grid looks like this. Subscripts show the order in which digits were written, and struck-out small digits are the candidates eliminated in those steps.

Right to the end of the puzzle, at every step at least one cell has a single candidate, and I never need the single-place rule. The table below holds all 42 steps. When building the table I scanned the grid in typewriter order at every step and filled the first cell with a single candidate, so a different order would lead to the same result.

Even in so easy a puzzle the power of the mark-up shows. It is also the reason the tightest-cell rule in the race finished this puzzle with 42 digits without a single backtrack. At every step there is a single-option cell and the tightest-cell rule picks it.

In hard puzzles, though, both methods stall at once. An exercise in the Cornell notes suggests the reader find a puzzle labelled "hard" and try to solve it with these two methods alone, and the purpose of the exercise is precisely to experience this stalling. In Shortz 301 the two methods together write only a few digits and then stop. In Mepham's puzzle they stop after ten digits. A stronger tool is needed.

J. F. Crook, professor emeritus of computer science at Winthrop University, proposes in a 2009 paper in the Notices of the AMS a method that solves any Sudoku with pencil and paper. The paper opens with an interesting sentence. According to Crook, Sudoku is in fact a trivial puzzle, because an algorithm exists that solves it, a tree search based on backtracking. He asks why people bother with pencil and paper when anyone could punch the digits into a computer and wait for the solution, and takes his answer from Herzberg and Murty. The puzzle is hard enough to be a serious mental challenge, yet scanning rows and columns to find missing digits is easy enough to encourage the solver to persist. I also like a side story in the paper. Crook received his first Sudoku book as a present at Christmas 2005 and his second on his seventieth birthday in 2007, and he says so in the acknowledgements.

Crook's first example is the puzzle below with its mark-up. Crook himself says that marking up by hand is tedious and error-prone, and adds that he wrote a small Visual Basic program running in Excel for the job, since Excel's table structure is perfect for holding a Sudoku.

Preemptive sets

Crook's method rests on a single concept. In puzzle books the same idea goes by different names, matching, partnership, naked pair, naked triple. Crook chooses the name preemptive set, which he finds more precise mathematically.

The subtlety of the definition is that the cells need not carry all m digits. {[4, 7], [c(2,1), c(2,9)]} is a preemptive pair because both cells have mark-up {4, 7}. But in a triple such as {[1, 2, 6], [c(1,7), c(1,9), c(2,9)]} the mark-ups of the cells can be {1, 6}, {1, 2} and {2, 6}. No cell carries all three digits, but across the three cells only these three digits occur, and that is enough. When a preemptive set is found, how its m digits will be distributed among its m cells is not yet known, that distribution emerges as the puzzle progresses.

The proof is nothing more than the pigeonhole principle. The m cells of X can take only the m digits of X. If one of the digits of X is written in a cell of the range outside X, that digit is used once in the range and can no longer enter the cells of X. Then m − 1 digits remain to be distributed over the m cells of X and one of the cells must stay empty. That contradicts the definition of a solution, which wants every cell filled. So the digits of X cannot be part of the solution anywhere in the range outside X.

The most common form of the occupancy theorem is the preemptive pair. If two cells in a row both have mark-up {4, 7}, then 4 and 7 are locked into these two cells. Even though I do not yet know which goes where, 4 and 7 cannot be in any other cell of that row, and I can cross them out. This crossing out sometimes leaves a single candidate in a cell, sometimes squeezes a digit into a single place in a unit, and sometimes reveals a new preemptive set. Crook's method uses this chain reaction systematically.

Hidden sets are really preemptive sets

Besides naked sets, puzzle books talk about hidden sets. A hidden pair is the situation where two digits in a unit occur only in the same two cells. The mark-up of those two cells may contain other digits too, but since these two digits cannot go anywhere else in the unit, they claim those cells and the other candidates can be crossed out. The second theorem in Crook's paper says hidden sets are really another face of preemptive sets. I want to write it with its proof, because it shows why what books present as two separate techniques are the same thing.

Let a unit have k empty cells. The unit is missing k digits, and these k cells, together with the k missing digits, form a preemptive set by default, in Crook's phrase. Because no digit not missing from the unit can appear in the mark-up of these cells. Now suppose I find a preemptive set of m cells inside this unit. Those m cells will share the m digits among themselves, and the remaining k − m cells must share the remaining k − m digits. So these k − m cells also form a preemptive set with the remaining k − m digits. Hence every preemptive set has a complement within the unit.

What books call a hidden set is a preemptive set whose complement is easier to spot by eye. Finding a hidden single in a box with four empty cells, that is, seeing that a digit can go to only one place in the box, is the same job as seeing that the remaining three cells form a preemptive triple. Crook states this as saying that whenever a preemptive set is found, its complement can always be seen too, and adds that the only exception is the singleton, since a one-cell set already means writing a digit.

Crook illustrates the idea in his paper with a three-box figure. In box 3, the mark-ups of cells c(1,7), c(1,9) and c(2,9) contain only 1, 2 and 6. This preemptive triple crosses 1, 2 and 6 out of the rest of the box. After the crossing out only 8 remains in c(1,8). Writing it also crosses 8 out of the mark-up of c(3,8), and the two empty cells left in the box, c(2,7) and c(3,8), form a preemptive pair with digits {3, 5}. The pair was hidden at first by the 6 and by the 2 and 8 in between, which is why it is a hidden pair. At the start the box was a default preemptive set of six cells and six digits. In the end it split into a three-cell triple and a two-cell pair, with a singleton in between. Crook's method consists of splitting every unit into ever smaller preemptive sets in this way.

The first half of the algorithm

The part of Crook's algorithm that needs no guessing can be summarised as follows.

1. Find the forced digits. Crook suggests starting with the most frequent digit. You find a box missing that digit and see whether the digit can go into only one cell of that box. If so, you write it. When that digit makes no more progress you move on to the next most frequent.
2. Mark up the puzzle.
3. Search all rows, columns and boxes for preemptive sets. Whenever you find one, cross digits out of the mark-ups according to the occupancy theorem, write any singletons that appear, and keep searching.
4. If the puzzle is solved, stop. If no unit can be split into smaller preemptive sets, move to the guessing stage.

In the next section I will show how this part solves Shortz 301 from start to finish, with every step.

Crook's example that needs no guessing is puzzle 301 from a book compiled by Will Shortz, the puzzle editor of the New York Times. The book prints it labelled "Beware! Very Challenging". It has 23 clues and is noticeably sparser than most newspaper puzzles.

First I try the two simple methods. Single candidates and single places together write only seven digits. In row 2 the only cells for 9 and for 1 are c(2,6) and c(2,3). These are the two digits Crook calls forced numbers in the paper. Next the only place for 7 in column 9 turns out to be c(5,9), only 5 remains in c(4,7), and in box 3 the digits 5, 8 and 3 fall into place in turn. Then everything stops. The initial mark-up is below.

At this point Crook's method comes in. From here on, at every step I either find a preemptive set and cross digits out of mark-ups, or fill the single candidates and single places those crossings reveal. On the path I followed, six preemptive sets are enough. All are pairs, and I show each one below at the moment it was found.