Sudoku Solver

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.

The “first” Sudoku puzzle.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s