A Su Doku Solver
The (London) Times Online have been publishing su doku puzzles over the last few months. See here for an explanation of what su doku is. Basically, it's a cute mathematical parlour game. More information is available here and, of course, Google is your friend.One naturally wonders both how one generates these puzzles, and how one solves them.
This sudoku-solver perl script can be used to solve su doku puzzles. Most Unix-like operating systems should come with perl pre-installed. On Windows, you might need perl from ActiveState or Cygwin.
There is no graphical user interface to the solver, and it itself is likely to be of interest only to geeks - like me. However, the discussion of heuristics below may be of more general interest.
Invocation
sudoku-solver reads a puzzle from either its standard input or a named file, and outputs the solved puzzle to standard output. The puzzle parser is very simple. It ignores all characters other than the digits [0-9] and underscores '_' (which are an alternative representation for '0', or an unknown value). Here's an example of a valid puzzle format. Any other layout characters including whitespace and newlines are ignored. sudoku-solver can read its own output, for example.The option '-v' causes sudoku-solver to produce verbose output describing all the possible values for all cells. This is useful for testing, and may also be useful on puzzles that sudoku-solver cannot solve. The option '-s' causes sudoku-solver to show the puzzle on standard output immediately before solving it. The option '-g' instructs the solver to try guessing values if it gets stuck. The guesser will only produce a solution if that solution appears to be unique. (Or, at least, that's how it's supposed to work; but reasoning about the recursive case is a bit tricky - there may be bugs.)
sudoku-solver prints the number of unsolved cells to standard error while it is running -- just to keep you amused. sudoku-solver exits with error status 0 if the puzzle was solved, and error status 1 otherwise.
How are puzzles solved?
The program use a process of elimination to restrict the values that may be placed into cells. It begins by assuming that any value can be placed in any cell (except those cells for which a value is specified), then repeatedly applies the heuristics below to eliminate possibilities. If only one value is possible for a cell, then that must be the value for that cell. Once this is the case for all cells, the puzzle is solved.There are many possible heuristics. The more one considers the problem, the more possible heuristics emerge. The heuristics used here are described below.
Heuristic 1
Heuristic 1 simply uses the fact that, if some value is known for some cell, then no other cell in the same row, column or box may contain the same value.This is illustrated below:
Heuristic 2
Heuristic 2 uses the following observation. Each box consists of three mini-rows and three mini-columns. If we know that some value can occur only within one of those mini-rows (or mini-columns), then that value cannot occur in any other cells within the corresponding complete row or column.This is illustrated for the case of mini-rows and rows below:
Heuristic 3
Heuristic 3 is similar to heuristic 2, only using values that can only occur in particular segments of rows or columns to infer that other cells in the corresponding boxes cannot contain those values.This is illustrated for the case of rows and row segments below:
Heuristic 4
Heuristic 4 captures the idea that, if some value cannot occur in any eight cells of some row, column or box, then that value must be the value for the remaining cell of that row, column or box.This is illustrated for the case of boxes below:
Heuristic 5
Heuristic 5 is the most computationally expensive of the heuristics, and also the most powerful: it subsumes heuristics 1 and 4.Consider any subset S (with cardinality N) of the cells of some row, column, or box. If there are only N possible values for the cells in S, then those values must appear in those cells in any solution. Therefore, those values cannot occur in the cells of the row, column or box at hand which are not members of S.
This is illustrated for a subset (of cardinality 3) of a box below:
The reason that this heuristic is so computationally intensive is that it requires all non-empty subsets of the cells of all rows, columns and boxes to be considered ... and there are a lot of such subsets.
When the set considered is a singleton, this heuristic subsumes heuristic 1. When the set considered is is of cardinality 8, this heuristic subsumes heuristic 4.
The intersection heuristic
Heuristics 2 and 3 are actually instances of a more general heuristic that might reasonably be termed the intersection heuristic. The intersection heuristic adds a kind of "round-the-corner" reasoning.Let P be the set of all of the cells in some row, box or column, and Q be the set of all of the cells in some other row, box or column such that the intersection of P and Q is non-empty. Let X be the set of cells in the intersection of P and Q. Let P' and Q' be the set of cells in P (respectively Q) that are not in X; that is, not in the intersection.
An example of this situation in which P is a box and Q is a row is:
The intersection heuristics states that the set of values that are possible in X but not possible in P' are also not possible in Q'; and similarly the other way around. In other words, if, considering P, some value must be in the part of P that is in the intersection, then that value cannot be in the part of Q that is not in the intersection. Take a look again at the examples for heuristics 2 and 3, above, thinking now in the terms described here.
For the case that P and Q are a row and a column, the intersection contains just a single cell, and this heuristic is is subsumed by heuristic 5. However, this heuristics appears to add information in the case that either P or Q is a box; hence it is described in terms of boxes as heuristics 2 and 3, above.
How effective are these heuristics?
The sudoku-solver actually implements only heuristic 5 and the intersection heuristic; these subsume all the other heuristics discussed above.It would be attractive if the heuristics above were in some sense complete. By "complete" one might mean that the algorithm based on repeated application of these heuristics solves any puzzle for which a unique solution exists.
Unfortunately, this appears not to be the case. This puzzle appears to have a unique solution, but is not solved using only the heuristics described here. Specifically, these heuristics only get this far; here are the details.
In light of this, it would be interesting to find a canonical example of a puzzle with a unique solution that cannot be solved by these heuristics. Please let me know if you know what such a puzzle looks like.
A colleague - a mathematician/statistician by trade - considers that the proof positive for any particular set of heuristics is likely to be difficult. The proof negative, of course, just requires a counter example - such as that above.
These puzzles are known to be NP-complete.
For issues or questions regarding this page, I can be reached at this email address. This server runs publicfile and FreeBSD.