kkck: A solver for Kriss Kross puzzles

# - - -   P u z z l e . _ _ c l u e C h e c k

    def __clueCheck ( self, choiceList, slot, k ):
        '''Eliminate choices inconsistent with clue at position k.

          [ (choiceList is a set of Word instances) and
            (slot is a Slot instance) and
            (k is a position within slot) ->
                if the cell at slot[k] contains a clue letter ->
                    choiceList  :=  choiceList - (any word not
                        having that letter at position [k])
                    else -> I ]
        '''

First we convert the index k into a grid position using Section 56, “Slot.__getitem__(): Slot position to puzzle position”. Then we find the cell at that position using Section 32, “Puzzle.whatCell(): Is there a cell at a given coordinate?”.

        #-- 1 --
        # [ coord  :=  the Coord instance in self corresponding to
        #       index [k] in slot ]
        coord = slot[k]

        #-- 2 --
        # [ cell  :=  the Cell instance in self at coord ]
        cell = self.whatCell ( coord )

If cell has no clue, we are done. Otherwise, examine each word in choiceList, and remove those whose [k]th character doesn't match the clue.

        #-- 3 --
        if cell.text == UNK_CELL:
            return
        else:
            clueLetter = cell.text

Removing the conflicts is just a little tricky. You might think that this code would do it:

        # THIS DOES NOT WORK!
        for choice in choiceList:
            if choice[k] != clueLetter:
                choiceList.remove(choice)

Try it and you will get the message “RuntimeError: Set changed size during iteration”. The correct approach is to form a list from the set, then iterate over the list, whose size will not change in the for loop. By the way, we depend on the Cell class to uppercase the clue letter, and the Word class to uppercase the word list, so that we don't have to a case-insensitive comparison here.

        #-- 4 --
        # [ choiceList  :=  choiceList - (elements that do
        #      not have (clueLetter) in position [k]) ]
        for choice in list(choiceList):
            if choice[k] != clueLetter:
                choiceList.remove ( choice )