The Combinatorics of Sudoku

04 january 2021

Introduction

Everyone is familiar with the Sudoku puzzle. It is a logic puzzle or game consisting of a square grid of 81 cells (nine rows by nine columns) that is divided in nine 3 × 3 subgrids called blocks. The objective is to fill the grid with the numbers 1 to 9 by placing a single number in each cell, in such a way that no digit appears twice in the same row, column, or block. The starting configuration of the grid has some digits already filled in, and then the puzzle is to complete the grid. The puzzle is well-formed if there is a unique solution from the starting configuration to a complete Sudoku grid. Here is an example of a starting configuration (the Sudoku puzzle), and the (unique) solution of it (the solved Sudoku).

Figure 1.Sudoku puzzle and solution.

History

The Sudoku puzzle became immense popular during the last fifteen years, though the first version appeared in 1979 as a puzzle in Dell Pencil Puzzles and Word Games, created by a retired architect named Howard Garns. It was published under the name of Number Place. Probably, Garns was inspired by the concept of Latin squares. A Latin square is a n × n grid filled with n symbols such that the same symbol never appears twice in the same row or column. The name Latin square was tossed by the famous 18-th century Swiss mathematician Leonard Euler who analysed some general properties and theorems. When the symbols are the numbers 1 to n, all rows and columns of a Latin square are permutations of these numbers. A Sudoku is clearly a special kind of Latin square, namely by the extra condition of the blocks being permutations as well. Garns’ puzzle remains unknown until it was introduced in Japan in 1984 under the name Sudoku. The Sudoku became popular in Japan and puzzles were published in newspaper, magazines, and puzzle booklets. Then, at the end of the 1990’s, the puzzle was discovered by Wayne Gould. He started to write computer programs for generating Sudoku puzzles, and he tried to get the puzzles published in English newspapers, which finally happened in 2004 in The Times, and in 2005 in the Daily Telegraph. Soon after, newspapers and magazines all over the world started to publish the Sudoku puzzle.

The number of Sudoku grids is exactly 6670903752021072936960 ≈6.671 × 10²¹

Mathematics

The Sudoku puzzle is a logic game that needs just strategic reasoning to get it solved. But it soon attracted mathematicians who analysed questions such as

What is the computational complexity of the Sudoku puzzle?
How easy is it to solve Sudoku puzzles by employing a set of rules or strategies?
How many Sudoku grids are there?
From what starting configurations is the puzzle uniquely solvable?
What is the minimal number of clues in the starting configuration and guarantee a unique solution?
How to generate Sudoku puzzles?
How to grade the difficulty of a Sudoku puzzle?

Here are a few answers.

Combinatorics

The Sudoku is NP-complete. There are a few ways to see this. The first one refers to the result that to complete a partial Latin square is NP-complete (Colbourn 1984). Another approach considers the Sudoku puzzle as a graph coloring problem (Delahaye 2006). Each of the 81 cells is a vertex of the graph. Two vertices associated with two cells in the same row, or in the same column, or in the same block are connected by an edge. Thus, each vertex is linked with (adjacent to) 20 other vertices, which makes a total of 20 x 81 / 2 = 810 edges in the graph. The problem is to color the vertices with 9 colors such that no two adjacent vertices get the same color. Graph coloring of this type is known to be NP-complete (Garey et al 1974).

Yet another view is integer programming (Scott Provan 2009). Let S be a grid consisting of n cells, C={1,…,m} be a set of colors, and B be a collection of blocks in the grid, each block B ∈ B having m cells (the Sudoku grid would have n=81, m=9, and the blocks are the rows, the columns and the 3 × 3 subgrids). Define 0-1 variables x_sc, where x_sc=1 means that color c is assigned to cell s, and x_sc=0 otherwise. An initial assignment A={(s_i,c_i), i=1,…,r } of colors c_i to cells s_i is given. Then we seek an assignment {X= x_sc∈ {0,1}, s ∈ S, c ∈ C} satisfying

Every cell gets one color:

Every block gets each color once:

The initial assignment:

Counting

The number of Sudoku grids is exactly 6670903752021072936960 ≈6.671 × 10²¹ (Felgenhauer and Jarvis 2005). Taking out symmetries such as rotations, reflections, permuting columns and rows, swapping digits, the number of essentially different Sudoku grids is reduced to 5472730538 ≈5.473 × 10⁹ (Jarvis and Russell 2006).

Clues

The clues are the initially filled cells with one of the digits forming the starting configuration, see Figure 1 for a 29 clue puzzle. It is yet unknown what the minimal number of clues must be to ensure a unique solution. There are examples of well-formed Sudoku puzzles having only 17 clues.

Generating Sudoku Puzzles

For generating random well-formed Sudoku puzzles, you need first a computer program that solves the grid from any starting configuration. The mostly used method is backtracking (Delahaye 2006). This is conceptually rather simple because it is a systematic trial and error approach. Consider the puzzle in Figure 1, and start filling it from column a rightward, and from row 1 upward. The first empty cell is d1. Place number 1 in it. If this is infeasible (as it is), replace by 2. Repeat until a feasible digit, which happens to be 3. The next empty cell is e1, where you place a 1. Again, continue checking feasibility and replacing until a feasible digit, here 7. You repeat this procedure at the next empty cell, etc. If you find that all digits 1 to 9 are infeasible, backtrack and increase the digit at the previous cell, and go forward again (it might be that you have to backtrack several previous cells). You continue this forward and backward filling and replacing until either you get stuck before completion, which means that there is no solution, or you find a unique solution, or you find multiple solutions. A well-written program should explore all possibilities, and find all solutions.

Also, you need a program that generates a random completed Sudoku, such as the one on the right of Figure 1. This can be done rather straightforward by an accept-reject algorithm that is based on importance sampling (Ridder 2013). The program runs over the cells one by one, keeping track of a list of feasible candidate digits, from which one is selected at random. When the list is empty before a complete Sudoku grid, it starts over. The acceptance ratio is about 3%.

Now, generate a random completed Sudoku by the importance sampling algorithm. Then, start removing digits (emptying cells) randomly. After each removal, run the solution program and check whether the solution is obtained uniquely. If this fails, restore a few removed digits, and start removing randomly again. Stop when the grid has a number of remaining filled cells (the clues in the starting configuration) is in the range 20-30.

When you get bored with the classic Sudoku, you can choose one of the many variations, like the Jigsaw Sudoku, the Killer Sudoku, the Sudoku X, the Greater-Less than Sudoku, the Double Sudoku, etc.

How to Solve it?

For humans, the backtracking method is impossible. They need strategies. Many strategies have been developed in the last years, books are written on it, websites offer tips, the Sudoku puzzle became business. When you see a puzzle like in Figure 1, the first thing to do is searching for empty cells that have exactly one feasible candidate digit, a so-called naked single. In Figure 1, cell b4 is such a cell and gets digit 1 (forced by the 1’s in c1, b9, e5, and i6). Similarly, c2 gets 5, c5 gets 4, e8 gets 5, b8 gets 9 etc. Usually, after a few of these assignments, more naked singles pop up. For instance, now c7 must get 6. You can derive these formally as follows. Mark in each cell of the starting configuration the feasible digits to fill the cell. For instance, consider block a1-c3 which gets pencil marks as shown in red in Figure 2. These pencil marks show that in this block digit 5 is feasible only in cell c2, thus this cell gets 5.

Figure 2. Pencil marks in block a1-c3 reveal a naked single.

Every time a cell gets its digit, you update the pencil marks in the other cells, which may lead to new naked singles and cell assignments. Only the easiest Sudoku puzzles are solvable by just using such simple strategies. More advanced strategies are needed for intermediate, difficult, hard and diabolic graded puzzles. To name a few strategies, hidden pairs, X-wing, swordfish, XY-wing (Davis 2012). The puzzle of Figure 1 needs a X-wing, namely, after the obvious naked single assignments you get the configuration shown in Figure 3, including some relevant pencil marks.

Figure 3. The X-wing strategy

The cells d4 and h4 are a locked pair of 7’s in row 4. Similarly, cells d8 and h8 are locked for the 7 in row 8. Note that 7 occurs exactly twice in rows 4 and 8, and in the same columns d and h of these rows. Necessarily, either d8 and h4 get the 7, or d4 and h8. This means that all 7’s in the pencil marks of the other cells in columns d and h can be removed. Doing this you see in Figure 4 a naked single appearing in row 2, meaning that you can go on filling the grid.

Figure 4. The X-wing makes the 7 in row 2 naked in b2

Variants

When you get bored with the classic Sudoku, you can choose one of the many variations, like the Jigsaw Sudoku, the Killer Sudoku, the Sudoku X, the Greater-Less than Sudoku, the Double Sudoku, etc. The American Mathematical Society published a booklet (Nacin 2019) with unusual Sudoku puzzles, such as the one in Figure 5, a so-called Far Sizedoku. An arrow points from a cell with a larger digit to a cell with a smaller digit if and only if the larger digit is two or more than the smaller digit. Figure 5 shows also a classic Sudoku which is graded as diabolic. It may take you some time to solve it.

Figure 5. A diabolic Sudoku and a Far Sizedoku

References

C.J. Colbourn (1984). The complexity of completing partial Latin squares. Discrete Applied Mathematics, Vol 8, pp 25–30.

T. Davis (2012). The Mathematics of Sudoku. Available at http://www.geometer.org/mathcircles/sudoku.pdf

J-P. Delahaye (2006). The Science Behind Sudoku. Scientific American, June issue, pp 80-87.

B. Felgenhauer, and F. Jarvis, (2006). Mathematics of Sudoku I. Mathematical Spectrum, Vol 39, No 1, pp 15-22.

E. Russell and F. Jarvis (2006). Mathematics of Sudoku II. Available at http://www.afjarvis.staff.shef.ac.uk/sudoku/russell_jarvis_spec2.pdf

M.R. Garey, D.S. Johnson, L. Stockmeyer (1974). Some Simplified NP-Complete Problems. Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp 47-63.

D. Nacin (2019). Math-Infused Sudoku. Puzzle Variants at All Levels of Difficulty. American Mathematical Society.

A. Ridder (2013). Counting the number of Sudoku’s by importance sampling simulation. Proceedings of the Recreational Mathematics Colloquium III, pp 85-92.

J. Scot Provan (2009). Sudoku: Strategy Versus Structure. American Mathematical Monthly, Vol 116, No 8, pp 702-707