Next / Previous / Contents / Shipman's homepage

5.15. SudokuSolver.__usedInRow(): Eliminate digits by row

The purpose of this method is to scan the row that contains a given board position x, look for digits used in that row at other positions, and return a “bitmap”: a nine-element list whose elements correspond to the nine digits in [1,9], such that each element is 1 if that digit is used elsewhere in the row, and 0 otherwise.

sudosolver.py
# - - -   S u d o k u S o l v e r . _ _ u s e d I n R o w   - - -

    def __usedInRow ( self, x ):
        """What digits are used elsewhere in the row containing x?

          [ x is an integer in [0,BOARD_L) ->
              return a 9-element bitmap whose elements are true
              iff the corresponding digit is used elsewhere in
              the row containing board position x ]
        """

First we figure out which row contains board index x. Then we set up the initial bitmap as a list of zeroes.

sudosolver.py
        #-- 1 --
        # [ rx      :=  the row index of board position x
        #   cx      :=  the column index of board position x
        #   result  :=  a list of MAT_L zeroes ]
        rx, cx  =  self.__xToRowCol ( x )
        result  =  [0] * MAT_L

As we scan the row, it is important to skip over the column containing x. The process of eliminating possibilities for a given cell must not depend on the state of the cell under consideration.

sudosolver.py
        #-- 2 --
        # [ result  :=  result with elements corresponding to
        #       digits found in row rx (except for column cx) ]
        for  col in range(MAT_L):
            #-- 2 body --
            # [ if (col != cx) and
            #   (self has a nonzero value D in cell (rx, col) ->
            #     result[D-1]  :=  1
            #   else ->
            #     I ]
            if  col != cx:
                cell  =  self.get(rx, col)
                if  cell != EMPTY:
                    result[cell-1]  =  1

        #-- 3 --
        return result