Next / Previous / Contents / Shipman's homepage

37. Puzzle.genSolutions(): Generate all solutions

# - - -   P u z z l e . g e n S o l u t i o n s

    def genSolutions ( self ):
        '''Generate the solution(s) to self, if any.

For the general features of the solution process, see Section 4.3, “Overview of the solution algorithm”. The first order of business is to run the cyclic reduction algorithm, Section 38, “Puzzle.__cyclicReduction(): Eliminate choices at slot intersections”. This method returns True if the current state is a solution; if not, it removes whatever choices it can from the WordBank instance and then returns False.

        #-- 1 --
        # [ if cyclic reduction solves self ->
        #     self  :=  self in solved state
        #     yield self in solved state
        #     raise StopIteration
        #   else -> I ]
        if VERBOSE: print "=== Cyclic reduction phase"
        if self.__cyclicReduction():
            yield self
            raise StopIteration

At this point, cyclic reduction can eliminate no other choices, so we proceed to the recursive solver, which is a generator. Each value generated by Section 39, “Puzzle.__reduceCycle(): Static elimination of word choices” is yielded to our caller.

        #-- 2 --
        # [ generate solutions to self starting with self's
        #   current state ]
        if VERBOSE: print "=== Recursive solution phase"
        for solution in self.__recurSolver ( self.__firstSlot ):
            yield solution

        #-- 3 --
        raise StopIteration