For a given position
self.__board, this method
returns a list of the digits that can legally occupy that
position, given the current state of the board.
# - - - S u d o k u S o l v e r . _ _ f i n d P o s s i b l e s def __findPossibles ( self, x ): """What digits are legal at position x on the board? [ x is an integer in [0,BOARD_L) -> return a list of digits not found in the row, column, or submatrix containing position x ] """
We'll divide the work up into three pieces corresponding to the three rules of the game: elimination by row, elimination by column, and elimination by submatrix.
For each rule, we'll call a method that returns a
nine-element list describing the digits that are
eliminated because they are used elsewhere in the row,
column, or submatrix. In these lists,
the digit 1, position
 to the
digit 2, and so on. Each position's value is 1 if the
digit is used elsewher, 0 if it isn't. In the intended
functions here, we use the term “bitmap” to
signify this convention.
#-- 2 -- # [ rowElim := a bitmap of the digits that occur # elsewhere in the same row as position x ] rowElim = self.__usedInRow ( x ) #-- 3 -- # [ colElim := a bitmap of the digits that occur # elsewhere in the same column as position x ] colElim = self.__usedInColumn ( x ) #-- 4 -- # [ subElim := a bitmap of the digits that occur # elsewhere in the same submatrix as position x ] subElim = self.__usedInSubmat ( x )
For the subsidiary routines, see:
Once we have all three lists, we will use the Boolean
“or” operator (
|) to derive a master list of the
digits that are eliminated—values of 1 again
#-- 5 -- # [ elim := (rowElim | colElim | subElim) ] elim = [ rowElim[x] | colElim[x] | subElim[x] for x in range(MAT_L) ]
Then we'll use that list to build a list of the digits that are not eliminated.
#-- 6 -- # [ return a list containing digits in [1,9] # corresponding to zero elements of elim ] result = [ i+1 for i in range(0,MAT_L) if elim[i]==0 ] #-- 7 -- return result