A sudoku solver

For a given position x in 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, position [0] corresponds the digit 1, position [1] 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 signifying elimination.

        #-- 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