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