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, “
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
x (see Section 5.18, “
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
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 )