kkck: A solver for Kriss Kross puzzles |  |
kkck: A solver for Kriss Kross puzzles | |
Abstract
Presents a method for solving crosspatch puzzles and a program embodying the method.
This publication is available in Web form and also as a PDF document. Please
forward any comments to tcc-doc@nmt.edu.
Table of Contents
main(): The main programusage(): Show command line argument usagefatal(): Write a message and stopshowIsV(): Display “H” or “V”perpendicular(): Return the opposite
orientationclass Puzzle: The top-level
containerPuzzle.__init__(): ConstructorPuzzle.__input(): Read the puzzle
filePuzzle.__readFile(): Partition the
input filePuzzle.__digestGrid(): Parse the
frameworkPuzzle.__gridLine(): Parse one line of
the frameworkPuzzle.__findSlots(): Locate all the
slotsPuzzle.__genSlots(): Detect slots in a
row or columnPuzzle.__addSlot(): Add a new slotPuzzle.__digestWords(): Parse the word
listPuzzle.__matchLengths(): Does the word list
match the slot set?Puzzle.__buildChoices(): Set up initial
word choicesPuzzle.__buildSlotChoices(): Build the
initial set of choices for one slotPuzzle.__clueCheck(): Eliminate initial
choices conflicting with cluesPuzzle.show(): Display the state of the
puzzlePuzzle.__showColHeads(): Column
headings for .show()Puzzle.__showRule(): Horizontal rule in
.show() outputPuzzle.__showRow(): Show one row of the
puzzlePuzzle.showAllChoices()Puzzle.whatCell(): Is there a cell at a
given coordinate?Puzzle.genCells(): Generate all the
cellsPuzzle.whatSlots(): What slots intersect
a given coordinate?Puzzle.scan(): Traverse a row or column
of the frameworkPuzzle.nSlots(): How many slots are
there?Puzzle.genSolutions(): Generate all
solutionsPuzzle.__cyclicReduction(): Eliminate
choices at slot intersectionsPuzzle.__reduceCycle(): Static
elimination of word choicesPuzzle.__reduceCell(): Eliminate choices where
two slots intersectPuzzle.__reduceSlot(): Eliminate choices
for one slotPuzzle.__uniqueWordTest(): Require that a word
be used only once in the puzzlePuzzle.__uniqueSlotTest(): Find words that are
choices for only one slotPuzzle.__recurSolver(): Recursive
solverPuzzle.__choiceFits(): Does this slot choice fit the rest of the puzzle?Puzzle.__crossingClash(): Does a perpendicular
slot conflict?Puzzle.__assumeChoice(): Try out an
assumptionclass Cell: One location for a characterCell.__init__(): ConstructorCell.addSlot(): Add an intersecting
slotCell.genSlots(): Generate the slots
intersecting this cellclass Slot: One place where a word
goesSlot.__init__(): ConstructorSlot.__str__()Slot.__len__(): Return the slot
lengthSlot.__getitem__(): Slot position to
puzzle positionSlot.__cmp__(): How to compare two slotsSlot.genCoords(): Generate all cell
coordinates of a slotSlot.findCoord(): Puzzle position to
slot positionclass WordBank: The word list and
puzzle stateWordBank.__init__(): ConstructorWordBank.addWord(): Add a word to the
word listWordBank.__len__(): How many total
words?WordBank.wordsOfLen(): How many words
have a given length?WordBank.genAllWords(): Generate all the
wordsWordBank.genCandidates(): What words have
a given length?WordBank.mayBe(): Add one word choice
to a slotWordBank.isNot(): Remove one word from
a slot's list of choicesWordBank.totalChoices(): How many total
choices are in the current state?WordBank.genSlotChoices(): What words
are choices for a slot?WordBank.slotCharChoices(): What letters
are choices at a given position?WordBank.cellChoices(): What characters
are choices at a given coordinate?WordBank.wordToSlots(): Which slots use a
given word?class Wordclass Coord: One location in the
gridCrosspatch puzzles, also known as Kriss Kross puzzles in copyrighted Dell publications, have been around for many decades. Wikipedia calls them Fill-In puzzles, but gives no history.
In this form of puzzle, the solver is given a crossword-like grid, and a list of words that must be arranged so that they all interlock.
Here is a trivial puzzle with only four words, shown after its solution:
In some puzzles, one or more words, or in rare cases single letters, will be provided initially.