Next / Previous / Contents / Shipman's homepage

38. Puzzle.__cyclicReduction(): Eliminate choices at slot intersections

kkck
# - - -   P u z z l e . _ _ c y c l i c R e d u c t i o n

    def __cyclicReduction ( self ):
        '''Eliminate choices wherever two slots intersect.
        
          [ if cyclic reduction solves self ->
              self  :=  self in solved state
              return True
            else -> return False ]
        '''
        #-- 1 --
        while 1:

For the general outline, see Section 4.5, “Cyclic reduction”.

kkck
            #-- 1 body --
            # [ if comparison of all intersecting slots does not
            #   reduce the total set of choices in self.__wordBank ->
            #     return False
            #   else if removing those choices solves the puzzle ->
            #     return True
            #   else -> I ]

To determine whether a round of cyclic reduction has made any progress toward a solution, we rely on Section 69, “WordBank.totalChoices(): How many total choices are in the current state?”. Every choice we eliminate will decrement this count. See also Section 36, “Puzzle.nSlots(): How many slots are there?”: when the choice count equals the slot count, it's a solution.

kkck
            #-- 1.1 --
            beforeCount = self.__wordBank.totalChoices()

            #-- 1.2 --
            # [ self.__wordBank  :=  self.__wordBank - (choices
            #       eliminated at slot intersections, if any) ]
            self.__reduceCycle()
            if VERBOSE:
                print self.show()

            #-- 1.3 --
            # [ if the total number of slot choices equals the
            #   number of slots ->
            #     return True
            #   else -> I ]
            totalChoices = self.__wordBank.totalChoices()
            print ( "=== Cyclic reduction: %d choices for %d slots" %
                    (totalChoices, self.nSlots()) )
            if totalChoices == self.nSlots():
                return True

            #-- 1.4 --
            if beforeCount <= totalChoices:
                return False