Sudoku Solver Method
Have a look at the full PHP source code of the Langabi.name automatic Sudoku (Soduku) solver. The first half of the code is the actual solver; the second half handles the display of the board, the solution, and all the accompanying HTML to make it look pretty (well, at least reasonably pretty).
In summary, the algorithm works in the following steps:
- For each of the 9x9=81 squares, there are three "groups" of squares that are significant: its row, its column, and its 3x3 subsection of the board. The algorithm sets up an array of these 27 groups of squares, and tracks what numbers have been used in each one so far (in the $check array). This allows the algorithm to try different values for each square without needing to scan all the other squares with which the current square mustn't share a value.
- Next, the algorithm does a number of passes through the board. For each square, if there is only one possible value it can take, then that value is chosen. The arrays created in the previous step are updated as well. Also, if a square has no available options, the problem is flagged as impossible. This step continues as long as new squares are being succesfully worked out.
- The remaining squares all have multiple possible values. They are sorted by increasing number of possible values, so that we still assign values to the most constrained squares first.
- The remaining squares are solved recursively (that is, starting at the one with smallest number of possible values, a value is assigned. Then the process repeats, for the remainder of the squares. If this leads to a solution, then the algorithm exits. Otherwise, the next possible value for the first square is attempted).
A few notes on the development of the algorithm:
- Only steps 1 and 4 are really required, for well-formed problems. However, certain well-constructed but impossible problems required a complete recursion of the entire solution space. Step 2 was introduced mainly to find these sorts of impossible problems quickly.
- Step 3 is purely a performance booster; though it's not clear it really makes that much difference. I've not played around enough to be sure.
Comments? Feel free to leave a comment on my Sudoku solver blog post.
And in case you missed it, a link to the full source code.