Solving Sudoku Problems in Mathematica

Jon McLoone
Wolfram Research

June 2005

Summary

Sudoku is a popular number puzzle.  Its rules are easily stated: 
A 9×9 grid is presented, containing some pre-defined numbers. The players task is to fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. 

For example

({{ ,  , 8, 1, 7, 6,  , 2,  }, { , 4,  ,  ,  , 9, 7,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { , 7, 1, 8,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  , 6, 7, 9}, { ,  ,  , 5, 9, 7,  , 8, 1}, { ,  ,  ,  , 2,  ,  ,  ,  }, { , 5, 9,  ,  ,  ,  , 1,  }, { , 1, 4, 6, 5,  , 3,  ,  }})

has a solution

({{5, 3, 8, 1, 7, 6, 9, 2, 4}, {1, 4, 2, 3, 8, 9, 7, 5, 6}, {7, 9, 6, 2, 4, 5, 1, 3, 8}, {9, 7, 1, 8, 6, 2, 5, 4, 3}, {8, 2, 5, 4, 1, 3, 6, 7, 9}, {4, 6, 3, 5, 9, 7, 2, 8, 1}, {3, 8, 7, 9, 2, 1, 4, 6, 5}, {6, 5, 9, 7, 3, 4, 8, 1, 2}, {2, 1, 4, 6, 5, 8, 3, 9, 7}})

Easy and moderate Sudoku puzzles can typically be solved with just two rules:
If a value is known for a particular square, then it can be eliminated as a possible value for each of the other squares in the dimension.
If only one square in a dimension has a particular number as a possibility, then it is known to be that squares value.

These two rules must be applied repeatedly in each of three dimensions: rows, columns and 3×3 sub-grids until nothing changes.

In under specified problems, or problems where these rules are insufficient, you can also do a systematic search. Pick the first value out of the remaining possible and solve from there. If a contradiction is reached, go back and try the next possible value. The existing logic is applied wherever possible to limit the size of search required. This search must be recursively applied as the problem may still be underspecified after a guess, whether or not that guess is correct.

This notebook presents a short program for applying those rules using the following template:

Solution

A function to apply all logic currently supported for a single line in isolation. 
1) Eliminate values that are known from other positions 
2) Search for numbers that occur only once and set them as known

Apply the line simplification function to all rows, columns and sub-grids (rearranged into lines and back again).

Tools

A test to see if we have completed the problem. If all 9×9 positions are of length 1, it is solved.

Commands to convert the 3×3 sub-grids into a matrix of 9 element rows and back again. This allows us to use the same code for cleaning and deducing from rows on the sub-grids. It can also be used on columns by using Transpose and then Transposing back again.

A command to initialize all the unspecified positions with a list of all possible values. Called only once at the start of the solver.

A formatting command for printing the problem out as a grid with the sub-grids highlighted

Work to do

Higher level logic:

LineSimplify uses a "level 1" logic, in that it can eliminate values once a value is found to be one value in one place.
LineSimplify could be extended to eliminate when two values are known in two places eg {1,2},{1,2} allows us to  remove 1 and 2 from other entries.
And {1,2,3},{1,2,3},{1,2,3}, eliminates 1,2,3 from others. etc

Cross dimensional logic

The logic used in this code considers each row, column and sub-grid in isolation. The more interesting rules to apply, as a human solving the problems, combine information between these three dimensions.
Consider the following, part-solved, example. In the 1,2 sub-grid, there are only two places for "2" to appear. So it must appear in one them, but since they are both in the same line in another dimension (column in this case), we can eliminate all other "2"s in the column such as the one at 5,4 (in the 2,2 sub-grid).

Generalizing,-if within a particular dimension, all possible positions for a value lie in the same (other) dimension, then you can eliminate all occurrences in the rest of that other dimension. 
This is true for a single value case too and would replace the current LineEliminate which is just a special case of this.

Super Sudoku

The code could easily be extended to cover the hexadecimal version of the problem with 16×16 grid and 4×4 sub-grids  or even higher order puzzles.

Examples

Intermediate

SudokuSolve[({{ , 6,  , 1,  , 4,  , 5,  }, { ,  , 8, 3,  , 5, 6,  ,  }, {2,  ,  ,  ,  ,  ,  ,  , 1}, {8,  ,  , 4,  , 7,  ,  , 6}, { ,  , 6,  ,  ,  , 3,  ,  }, {7,  ,  , 9,  , 1,  ,  , 4}, {5,  ,  ,  ,  ,  ,  ,  , 2}, { ,  , 7, 2,  , 6, 9,  ,  }, { , 4,  , 5,  , 8,  , 7,  }})]

SudokuSolve[({{ ,  , 6,  , 1, 3,  ,  ,  }, {3, 9,  ,  ,  ,  ,  , 1,  }, {2, 1, 8,  ,  ,  , 4,  ,  }, {8, 7,  , 2,  ,  ,  ,  ,  }, { ,  ,  , 8, 6, 1,  ,  ,  }, { ,  ,  ,  ,  , 7,  , 4, 9}, { ,  , 3,  ,  ,  , 7,  , 8}, { , 4,  ,  ,  ,  ,  , 2, 5}, { ,  ,  , 9, 2,  , 3,  ,  }})]

SudokuSolve[({{ , 3,  ,  ,  ,  ,  , 7,  }, { , 1,  , 8,  , 6,  , 2,  }, { ,  , 9, 1, 7, 5, 4,  ,  }, { ,  , 7,  ,  ,  , 6,  ,  }, {2,  ,  , 4,  , 9,  ,  , 3}, { ,  , 3,  ,  ,  , 1,  ,  }, { ,  , 1, 5, 4, 8, 2,  ,  }, { , 6,  , 3,  , 2,  , 1,  }, { , 5,  ,  ,  ,  ,  , 4,  }})]

Expert

SudokuSolve[({{ ,  , 8, 1, 7, 6,  , 2,  }, { , 4,  ,  ,  , 9, 7,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { , 7, 1, 8,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  , 6, 7, 9}, { ,  ,  , 5, 9, 7,  , 8, 1}, { ,  ,  ,  , 2,  ,  ,  ,  }, { , 5, 9,  ,  ,  ,  , 1,  }, { , 1, 4, 6, 5,  , 3,  ,  }})]

SudokuSolve[({{5, 3, 8, 1, 7, 6,  , 2,  }, { ,  ,  ,  ,  , 9, 7,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { , 7, 1, 8,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  , 6, 7, 9}, { ,  ,  , 5, 9, 7,  , 8, 1}, { ,  ,  ,  , 2,  ,  ,  ,  }, { , 5, 9,  ,  ,  ,  , 1,  }, { , 1, 4, 6, 5,  , 3,  ,  }}),ShowSteps -> True]

SudokuSolve[({{\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], 6, 8, 4, \[Placeholder], 1, \[Placeholder], 7, \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], 8, 5, \[Placeholder], 3, \[Placeholder]}, {\[Placeholder], 2, 6, 8, \[Placeholder], 9, \[Placeholder], 4, \[Placeholder]}, {\[Placeholder], \[Placeholder], 7, \[Placeholder], \[Placeholder], \[Placeholder], 9, \[Placeholder], \[Placeholder]}, {\[Placeholder], 5, \[Placeholder], 1, \[Placeholder], 6, 3, 2, \[Placeholder]}, {\[Placeholder], 4, \[Placeholder], 6, 1, \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], 3, \[Placeholder], 2, \[Placeholder], 7, 6, 9, \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}}),ShowSteps -> True]

({{, , 3, , 6, 2, , , }, {, 6, 8, 4, 3, 1, , 7, }, {, , , , 8, 5, , 3, 6}, {3, 2, 6, 8, , 9, , 4, }, {, , 7, , 2, , 9, 6, }, {, 5, , 1, 7, 6, 3, 2, }, {, 4, , 6, 1, , , , }, {, 3, , 2, , 7, 6, 9, }, {6, , , , 9, , , , }})//SudokuSolve

Seventeen hints

Seventeen hints seems to be the minimum to produce a unique solution. The Minimal Sudoku page maintains the known progress for this problem.

Unsolvable problems

Some problems are contradictory and have no solution

({{4, , 3, 7, 6, 2, 8, , }, {, 6, 8, 4, 3, 1, , 7, }, {, , , , 8, 5, , 3, 6}, {3, 2, 6, 8, , 9, , 4, }, {, , 7, , 2, , 9, 6, }, {, 5, , 1, , 6, 3, 2, }, {, 4, , 6, 1, , , , }, {, 3, , 2, , 7, 6, 9, }, {6, , , , 9, , , , }})//SudokuSolve

Highly under specified problems

Some problems have more than one solution as they are under-specified. An extreme example of this is the empty problem. A solution is found, but it is only one of a vast number of solutions

SudokuSolve[({{ ,  ,  ,  ,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  ,  ,  ,  }, { ,  ,  ,  ,  ,  ,   ,  ,  }, { ,   ,  ,  ,   ,  ,  ,  ,  }}),ShowSteps -> True]//Timing