kkck: A solver for Kriss Kross puzzles |  |
kkck: A solver for Kriss Kross puzzles | |
The kkck script takes as input a puzzle encoded as a text file in a straightforward form. Here is the example puzzle from Section 1, “Introduction to crosspatches” in its encoded form:
##### # # # # ###### # # idyll kriss kross solver
An input file is a sequence of lines of three types:
The framework comes first,
with each row of the puzzle encoded on a separate
line. Empty cells are denoted by the #
character, and spaces represent places where letters
will not be placed.
A blank (or empty) line follows the framework, to separate the framework from the word list.
The word list enumerates all the words (or other strings of symbols) that are to be fit into the framework. The format of this section of the file is free-field: the words may be scattered over any number of lines, and separated by any of the common whitespace characters (spaces or tab characters).
Although we call them “words,” in
practice they may contain digits and any special character
other than #. Words may not contain
internal spaces.
If initial clues are given, the letters of the clue
replace the corresponding # characters
in the framework. For example, here is a framework
section with one of the words already filled in:
##i## # d # y ##l### # l
Comments may be included anywhere in the input file by
starting each comment line with an exclamation point
(“!”) character.
To solve a puzzle, run kkck like this:
kkck filename
where the filename
The program will print out all solutions (if there are any), followed by a line giving the total number of solutions. A properly constructed puzzle will have exactly one solution.
The script uses two techniques to solve the puzzle. In the first phase, it makes one or more passes through puzzle using a technique called “cyclic reduction;”, repeating these passes until the puzzle is solved or until this technique makes no more progress. During this phase you will see messages that look like this:
=== Cyclic reduction: 135 choices for 82 slots === Cyclic reduction: 82 choices for 82 slots
These example lines came from a puzzle with 82 words; only two passes of cyclic reduction were necessary to find the solution.
Most puzzles are solved in less than a second in the cyclic reduction phase. For uncommonly difficult puzzles, the script goes into a second phase using a recursive algorithm that will, given sufficient time, find solutions to any puzzle. The only puzzle the author has tried that took more than a few seconds was a 21×21 puzzle with 56 slots, all with six letters. On a 3.6GHz 64-bit Intel processor this puzzle took over forty hours to find two solutions. The puzzle was symmetric about its main diagonal, so the two solutions are also symmetric.