We simultaneously introduce effective techniques for solving Sudoku puzzles and explain how to implement them in Mathematica. The hardest puzzles require some guessing, and we include a simple backtracking technique that solves even the hardest puzzles. The programming skills required are kept at a minimum.

Introduction to Sudoku

Sudoku, for those unfamiliar with this puzzle, consists of a square grid with nine subgrids. The 81 entries are to be filled with the integers 1 to 9 in such a way that each row, column and subgrid contains all the nine integers. Some of the entries are already chosen, and the final puzzle solution must contain these initial choices. Here is a sample puzzle.

First Steps to Solving Sudoku

The input for this puzzle is a list of nine lists consisting of blanks (shown as □) or integers between 1 and 9. A list of lists of the same length is regarded as a matrix in Mathematica, so we input for the puzzle and then show it in matrix form.

We can also display this in Sudoku format by drawing column and row lines and a frame.

In attempting a solution, a blank gets replaced with a list of candidate entries shown compactly without braces or commas.

Each element of a Sudoku matrix is obtainable as , where and are the row and column of the element in the matrix.

To obtain the entire row in X that contains the entry , we evaluate ; so, for example, this gives row 3, which contains element .

To obtain the column in X that contains is a little trickier. One could first “transpose” the matrix , that is, interchange rows and columns and then find row of the transposed matrix; the command for transposing a matrix is . However, Mathematica has a faster way using the option . We just enter to get column of X. For example, the column that contains , that is, column 5 of , can be obtained by entering .

The function displays that list vertically.

It is more difficult to obtain the block to which belongs. To do this we define a function that gives a list of the entries that comprise the block of in X.

For example, this is the block containing , the sixth entry in row 1, □.

To get a single list of these entries by removing the inner parentheses, we use .

Our first step is to replace each □ in (using ) by the list of the nine numbers, , which are possible candidates to occupy that position in .

Our next task is to start eliminating candidate values in the entries that are lists of numbers in X, proceeding one entry at a time. We start with in order to be able to redefine entries.

Since no entry can appear more than once in any row, column or block, we let be the set of integers in the row, column and block containing .

If the entry is a list rather than an integer, we redefine by removing the entries that also belong to .

Finally, if is a list of one element, we redefine it to be that element.

To apply again and again to until the result no longer changes, we use . The puzzle simplifies, but we see that we are still not done!

However, the first block has three entries (colored red) that are all sublists of .

While we do not know the exact value of any of the red entries, we know that the three numbers 5, 6 and 8 will be used up filling them; thus we can remove 5, 6 and 8 from the other entries in this block (colored green).

Similarly, in the first row, there are three entries that are sublists of , so we remove 5, 6 and 8 from at the end of row 1; this defines .

Then we use again and display the result. We are done! We explore this technique further in the next section.

Sudoku Twins and Multiples

If any row, column or block contains the pair twice, both and must be used up in the two entries containing , even though we do not know which pair contains and which contains . Hence, no other entry in that row, column or block can contain either or . This obvious fact is surprisingly useful in solving Sudoku puzzles.

To use it, we define the function .

1. We select the set of pairs (the lists of length two).

2. The twins are the identical pairs.

3. The numbers in the twins are the numbers to prune.

4. The lists are pruned.

5. Any singleton list is changed to its element.

Here are some examples using , which was defined before. The twins in this row are and .

Hence 5 and 8 are removed from the other lists in the row.

The twins in row 3 are and .

We can map over all the rows of a matrix.

We now use starting with until the result does not change.

We are done. It was only necessary to use on the rows.

It is easy to apply on the columns: transpose, apply to the rows, and transpose back.

The blocks are more complicated. We make use of a general theorem: transform an matrix by taking the elements of each block in order as the rows of a new matrix ; then (i.e. is an involution). Here stands for block transpose.

This verifies the theorem in the case.

To construct the new kind of transposed matrix, we define the function .

Here is the transformed matrix .

Finally, we look at the matrix .

It is the same as the original matrix ; here is a direct check that they are equal.

It is a common technique in problem solving to first transform the problem, solve the transformed problem and then transform back. As an example, we apply , followed by , followed by , to the matrix defined earlier; blocks , and change.

This makes a function out of that line of code.

The function puts together the discussion so far.

We apply it to the matrix and get a solution as before.

We generalize the function to to deal with triples and quadruplets as well as twins.

Just as with , we want to use on rows, columns and blocks of a matrix and then combine them in .

We had already solved with , but let us apply for triples as a check.

combines the three solvers into one.

Consider the puzzle .

Unfortunately, does not solve the puzzle.

However, there are entries that are pairs.

We propose to replace the pair by 1 and to try to solve the modified puzzle; if that leads to a contradiction, then .

We introduce the functions and via the helper function . If there are any pairs in X, replaces the first such pair with its left entry and applies ; the function replaces with its right entry .

The two blank entries indicate a contradiction.

Therefore, the alternative must solve the puzzle, and it does.

Backtracking

We have just seen that guessing between two alternatives quickly led us to a solution. However, if a solution was not obtained with the first alternative, it might be necessary to again guess between two alternatives, and so on. If there are always just two alternatives, this leads to a binary tree with the root at the top.

It is not clear how many levels or guesses are needed before reaching a solution. Also, it may not be necessary to generate the entire tree before a solution is reached. There is a systematic and efficient way to search such a tree, usually referred to as backtracking.

Here is the method: start at the root and go left as long as there is no contradiction. If there is a contradiction, go back one level and go right. Then resume going left as far as possible. If there is a contradiction after going right, go back through all the right branches traversed so far; then go back through an additional left branch and go right.

For example, assume that contradictions exist at all nodes on level 4 except for the last one, node 15. The labels in the following tree indicate how to backtrack to the solution at node 15.

The binary choice in the Sudoku situation is to go either left or right. A path through the tree corresponds to a sequence of such choices; for example, the path (1, 2, 6, 8) generates the sequence: , from which a composition of functions can be built.

Here is how the built-in function works with undefined functions.

This example shows a clear contradiction, since there are two blank entries.

The function , when given a nonempty sequence of and functions, drops the last in the sequence (if any) until there are none, drops the last , and finally appends a .

Here is an example.

In the next two functions, this kind of code tests for a list of lists of integers, a necessary condition for a Sudoku solution.

The function goes left if applying the sequence (a global variable with entries and ) to the matrix with does not contain an empty list ; otherwise it backtracks using . If the new sequence applied to the matrix contains only numbers, throws the matrix to the nearest containing .

We now use inside the function , which initializes the global variable .

Consider the following Sudoku puzzle.

We have failed so far to solve the puzzle using ; so we try the backtracking technique.

To see what sequence solved this puzzle, we only have to enter .

We next try on defined in the previous section.

If we now enter , we can see what sequence solved this puzzle.

Next is Evil Puzzle 8,076,199,743 from Web Sudoku [1].

Again, the solving sequence is given by .

This final puzzle was created by Arto Inkala, a mathematician based in Finland; it is claimed to be the world’s hardest Sudoku puzzle [2].

Here is how this puzzle was solved.

There are many other techniques known to experienced Sudoku solvers that could be added to our programs; also backtracking could obviously be extended to triples, and so on.

Conclusion

Sudoku provides a superb opportunity to introduce useful programming techniques to students of Mathematica. Backtracking is one such technique that is largely absent from standard discussions of Mathematica programming but, as we have shown, is easily implemented in Mathematica when needed.

References

[1]	Web Sudoku. (Jan 18, 2018) www.websudoku.com.
[2]	Efamol. “Introducing the World’s Hardest Sudoku.” (Jan 18, 2018) www.efamol.com/efamol-news/news-item.php?id=43.
R. Cowen, “A Beginner’s Guide to Solving Sudoku Puzzles by Computer,” The Mathematica Journal, 2018. dx.doi.org/doi:10.3888/tmj.20-1.

About the Author

Robert Cowen is Professor Emeritus in Mathematics, Queens College, CUNY. He does research in logic, combinatorics and set theory. He taught a course in Mathematica programming for many years, emphasizing discovery of mathematics, and is currently working on a text on learning Mathematica through discovery with John Kennedy. His website is sites.google.com/site/robertcowen.

Robert Cowen
16422 75th Avenue
Fresh Meadows, NY 11366
robert.cowen@gmail.com