Next / Previous / Contents / Shipman's homepage

5.17. SudokuSolver.__usedInSubmat(): Eliminate digits by submatrix

This method inspects the submatrix containing board location x and returns a bitmap with 1 elements corresponding to digits used elsewhere in that submatrix.

sudosolver.py
# - - -   S u d o k u S o l v e r . _ _ u s e d I n S u b m a t r i x

    def __usedInSubmat ( self, x ):
        """What digits are used in the submatrix 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 submatrix containing board position x ]
        """

The result bitmap is initialized to nine zeroes. Then we set rx and cx to the row and column index corresponding to board position x. Then we set rSub and cSub to the coordinates of the upper left cell of the submatrix.

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

        #-- 2 --
        # [ rSub  :=  index of the row containing the upper left
        #             cell of the submatrix containing row rx
        #   cSub  :=  index of the column containing the upper left
        #             cell of the submatrix containing column cx ]
        rSub  =  (rx / 3) * 3
        cSub  =  (cx / 3) * 3

We iterate over the elements of the submatrix, setting elements of the result bitmap to 1 wherever we find digits. Again, it is important not to look at the cell at (rx, cx), so we don't have to depend on that cell being in any known state.

sudosolver.py
        #-- 3 --
        # [ result  :=  result with its elements set to 1 at
        #       each position corresponding to a digit that
        #       occurs in the submatrix whose upper left corner
        #       is at row rSub, column cSub, ignoring the cell at
        #       row rx, column cx ]
        for  rowx in range(rSub, rSub+SUBMAT_L):
            for  colx in range(cSub, cSub+SUBMAT_L):
                #-- 3 body --
                # [ if (rowx != rx) or (colx != cx) and
                #   self's cell value V at row rowx, column colx is
                #   not EMPTY ->
                #     result[V-1]  :=  1
                #   else -> I ]
                if  ( ( rowx != rx ) or ( colx != cx ) ):
                    cell  =  self.get(rowx, colx)
                    if  cell != EMPTY:
                        result [ cell-1 ]  =  1

        #-- 4 --
        return result