Next / Previous / Contents / Shipman's homepage

4.3. Overview of the solution algorithm

Note in the entity-relationship diagram in Section 4.2, “Data structures” that each word is shown as being related to exactly one slot, and vice versa. This is true for the puzzle in a solved state. The problem we have to solve is how to get the puzzle into the solved state—or states, since a poorly-constructed puzzle may have multiple solutions.

Probably the simplest algorithm to implement would be a brute force recursive algorithm. Once we have defined an order for the slots, we would try every word that fits in the first slot, and for each possible choice, recursively call a solver that tries all the options for the next slot, and so forth until we either reach a contradiction (where there are no words that will fit in some slot), or reach a solution state.

For an example of a similar puzzle solver using this technique, see A sudoku solver. For some of the hardest sudoku puzzles, the solution on relatively modern processors may take several minutes.

Although this is not an impractical interval, the author wished to try for major efficiency gains by reducing the number of candidates for each slot before starting the recursive process. For almost all published puzzles, a technique of cyclic reduction (described below) is sufficient to solve them, but the author has encountered a few expert-level puzzles that cyclic reduction would not solve the puzzle.

The next three sections describe three phases of solution. The goal of the program is to build a data structure representing a solution, that is, it shows only one word for each slot.