A sudoku solver |  |
A sudoku solver | |
This is the meat of the class: the method that tries to solve the puzzle.
# - - - S u d o k u S o l v e r . s o l v e - - -
def solve ( self ):
"""Find all solutions to the puzzle.
"""
There are doubtless many approaches to solving the puzzle, but the author's preferences are well expressed in this quotation from a former professor in Computer Science at New Mexico Tech:
There are very few problems in computer science that are not susceptible to brute force. | ||
| --Ed Runnion | ||
So, consider the board as a list of 81 integers, some of which are nonzero (the initial clues) and some of which are zero (the empty cells). One approach to solving the problem works like this: we work from the start of the board to the end, and at each cell we do this:
If the cell already has a value in it, move one to
the right. If that takes us out of the board at the
far end, this is a solution—call the
self.solutionObserver
callback to report a solution.
If the cell doesn't have a value in it, see what values are still legal given the current state of the board. This is done by starting with a full set of all nine digits, then eliminating any that occur elsewhere in that row, elsewhere in that column, or elsewhere in that submatrix.
If the set of legal values computed in the previous step is empty, there cannot be any solution with the board in this state. Move one to the left; if that takes us before cell 0, we are done.
For each of the set of legal values, put that value in the current cell and move one to the right. When the process returns to this cell, put the next legal value in and repeat until all values are gone.
Rather than using clunky iterative techniques to handle
moving right and left on the board, this approach seems
to call for recursion. We can reframe the problem of
solving the whole puzzle as a call to a recursive method
that solves the puzzle starting at position 0. Assuming
there are any legal choices at position 0, we put each
legal choice into the cell at position 0, then recur to
solve the puzzle starting at position 1. The basis case
that stops recursion is an attempt to solve the puzzle
starting at the last-plus-one position (index BOARD_L). Recursion also stops when there
are no legal moves at the current position.
So, deferring all the ugly logic to the recursive
method, here is the body of the .solve() method. The recursive method is
described in Section 5.12, “SudokuSolver.__reSolve():
Recursive solver method”.
#-- 1 --
# [ call self.solutionObserver for all solutions of
# self.__board and call self.changeObserver (if any)
# for all state changes in finding those solutions ]
self.__reSolve ( 0 )