Next / Previous / Contents / Shipman's homepage

5.11. SudokuSolver.solve(): Find all solutions

This is the meat of the class: the method that tries to solve the puzzle.

sudosolver.py
# - - -   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:

  1. 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.

  2. 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.

  3. 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.

  4. 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”.

sudosolver.py
        #-- 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 )