This is in competition for my most uninteresting post. But it’s hopefully a useful snippet for those few with whom I’ve had recent discussion about Sudoku, and algorithms for solving– and more interestingly, in my opinion, *generating*— instances of the puzzle.

Writing a program to solve Sudoku puzzles seems to have become a standard programming exercise, whether as an experienced developer learning a new language, or as a beginner learning about, say, recursion and depth-first search. (In my day it was the Eight Queens Puzzle.) It’s a nice problem; the backtracking part is relatively straightforward, but the test for whether a candidate solution is valid is slightly more complex, or at least potentially awkward, depending on the language at your disposal.

Following is my implementation in Mathematica, that attempts to combine “short” with “still readable”:

ValidSudokuQ[s_, n_, {i_, j_}] :=
And @@ Map[
Count[#, n] <= 1 &,
{
s[[i, All]],
s[[All, j]],
Partition[s, {3, 3}][[Ceiling[i/3], Ceiling[j/3]]] // Flatten
}
]
$RecursionLimit = Infinity;
SolveSudoku[s_] :=
Module[
{p, r, n},
p = Position[s, 0];
If[p === {},
Print[s],
p = First[p];
Do[
r = ReplacePart[s, n, p];
If[ValidSudokuQ[r, n, p], SolveSudoku[r]],
{n, 9}
]
]
]

We can clean this up a bit with some typesetting, to print the solutions in their usual form:

ShowSudoku[s_] :=
GridBox[s,
GridFrame -> True,
ColumnLines -> {True, True, 2, True, True, 2, True},
RowLines -> {True, True, 2, True, True, 2, True}
] // DisplayForm

For example, starting with a completely empty grid, the above algorithm yields the “first” (i.e., lexicographically least) Sudoku instance:

The “first” Sudoku puzzle.

### Like this:

Like Loading...

*Related*