A sudoku solver

This method is the recursive part of the solution mechanism. It is given a starting position on the board, and tries to find digits that will work at that position. If there are any such digits, it places each at the current position, and then recurs to solve the board starting at the next position.

# - - -   S u d o k u S o l v e r . _ _ r e S o l v e   - - -

    def __reSolve ( self, x ):
        """Recursively solve the puzzle.

          [ (self.__board has no blank cells before position x) and
            (x is an integer) ->
              if x >= BOARD_L ->
                call self.solutionObserver for the current state
                of self.__board
              else if x is in [0,BOARD_L) ->
                call self.solutionObserver for all solutions of
                self.__board starting at position x, and call
                self.changeObserver (if any) for all state changes
                in finding those solutions ]
        """

As with any good recursive function, we check for the basis case first. If the index x is past the end of the board, then the current state of the board is a solution. See Section 5.13, “SudokuSolver.__solution(): Signal a solution” for the actions taken on detecting a solution.

        #-- 1 --
        # [ if x >= BOARD_L ->
        #     call self.solutionObserver
        #     return
        #   else -> I ]
        if  x >= BOARD_L:
            self.__solution()
            return

If this position on the board is one of the original clues (that is, if self.__given[x] is nonzero), we recur to solve the rest of the board, and then return.

        #-- 2 --
        # [ if self.__given[x] != EMPTY ->
        #     call self.solutionObserver for all solutions of
        #     self.__board starting at position x+1, and call
        #     self.changeObserver (if any) for all state changes
        #     in finding those solutions
        #     return
        #   else -> I ]
        if  self.__given[x] != EMPTY:
          self.__reSolve ( x + 1 )
          return

At this point, we know that position x is currently empty. We look around the board to see what digits are still legal here, if any. For that logic, see Section 5.14, “SudokuSolver.__findPossibles(): What digits are legal at a given position?”.

        #-- 3 --
        # [ possibles  :=  list of all digits that are not
        #       duplicate in the same row, column, or submatrix
        #       as cell x ]
        possibles  =  self.__findPossibles ( x )

Our caller may have left us with a board in which there is no possible digit that fits at position x. In that case, the possibles list will be empty. If there are one or more possible digits, though, we must try solving the puzzle for each possibility. So, for each element of possibles, we store that element in cell x (see Section 5.18, “SudokuSolver.__set(): Store a value in a cell”), and recursively try to solve the rest of the puzzle.

One very important part of this step is that we must set cell x back to empty before returning to the caller. We wouldn't want to set it empty if the cell is one of the original clues, but that case was eliminated above.

        #-- 4 --
        # [ call self.solutionObserver for all solutions of
        #   self.__board starting at position x+1 with cell x
        #   set to each member of possibles, and call
        #   self.changeObserver (if any) for all state changes
        #   in finding those solutions ]
        for  trial in possibles:
            #-- 4 body --
            # [ call self.solutionObserver for all solutions of
            #   self.__board starting at position x+1 with cell
            #   x set to trial, and call self.changeObserver
            #   (if any) for all state changes in finding those
            #   solutions ]
            self.__set ( x, trial )
            self.__reSolve ( x + 1 )

        #-- 5 --
        self.__set ( x, EMPTY )