kkck: A solver for Kriss Kross puzzles

# - - -   P u z z l e . _ _ r e c u r S o l v e r

    def __recurSolver ( self, slot ):
        '''Recursively solve the puzzle, starting at slot.

          [ slot is a Slot in self ->
              generate solutions to self starting with self's
              current state ]
        '''

See Section 4.6, “The recursive algorithm” for design notes. The first order of business is to check the basis case: are we at the last slot? If we are, then every previous slot is down to one choice, and if our invariants are true, there should be only one choice for this slot. In any case, if there are no choices for the current slot, there are no solutions for the current state, and we can terminate back to the caller.

        #-- 1 --
        # [ choiceList  :=  choices for slot in self.__wordBank,
        #       sorted
        #   nextSlot  :=  successor to slot in self, or None if
        #       slot is the last in self ]
        choiceList = [ choice
                       for choice in
                       self.__wordBank.genSlotChoices ( slot ) ]
        choiceList.sort()
        nextSlot = self.__slotSuccessor[slot]

        #-- 2 --
        # [ if nextSlot is None ->
        #       if len(choiceList) == 1 ->
        #           yield self
        #           raiseStopIteration
        #       else ->
        #           sys.stderr  +:=  error message
        #           stop execution
        #   else if len(choiceList) is 0 ->
        #       raise StopIteration
        #   else -> I ]
        if nextSlot is None:
            if len(choiceList) == 1:
                yield self
            raise StopIteration
        elif len(choiceList) == 0:
            raise StopIteration

We have eliminated the basis case, and the case where there is one choice, so we know we have to recur once for each of the current choices. First, temporarily remove all the current choices.

        #-- 3 --
        # [ self.__wordBank  :=  self.__wordBank - (choices for slot
        #       from choiceList ]
        for choice in choiceList:
            self.__wordBank.isNot ( slot, choice )

Then, for each of the original choices that fits into the rest of the puzzle, recursively generate all solutions that use that choice; see Section 45, “Puzzle.__choiceFits(): Does this slot choice fit the rest of the puzzle?” and Section 47, “Puzzle.__assumeChoice(): Try out an assumption”.

        #-- 4 --
        # [ generate solutions for slot containing each choice
        #   from choiceList that fits the current choices in
        #   self.__wordBank, starting with nextSlot ]
        for choice in choiceList:
            #-- 4 body --
            # [ if choice in slot fits the rest of the puzzle
            #   according to self.__wordBank ->
            #     generate solutions to self assuming slot==choice
            #   else -> I ]
            if self.__choiceFits ( slot, choice ):
                #-- 4.1 --
                # [generate solutions to self assuming slot==choice ]
                for solution in self.__assumeChoice ( slot,
                    choice, nextSlot ):
                    yield solution

Finally, reinstate all the original choices, and terminate to the caller.

        #-- 5 --
        # [ self.__wordBank  :=  self.__wordBank + (choices for slot
        #       from choiceList ]
        for choice in choiceList:
            self.__wordBank.mayBe ( slot, choice )

        #-- 6 --
        raise StopIteration