Next / Previous / Contents / Shipman's homepage

4.5. Cyclic reduction

Once we have a tentative set of the word choices for each slot, we can reduce the number of choices for each slot by three processes of elimination:

The “cyclic reduction” phase of solution, then, consists of walking through all the intersection cells and trimming the lists of choices for slots by these three mechanisms.

Each time we eliminate some choices from a slots, there is a ripple effect—changes propagate to other slots, allowing us to eliminate more choices, which propagates to other slots, and so on.

Therefore, whatever we do to eliminate choices, we must repeat this process until we either solve the puzzle, or until another pass through the puzzle does not eliminate any more choices.

If we reach a solution, all we need to do is display the current of the puzzle and terminate execution.

If instead we reach a point where some slots still have multiple words that may fit, and cyclic reduction does not eliminate any choices, then we'll have to proceed to Section 4.6, “The recursive algorithm”.

One design question remains: how do we sequence the three kinds of tests that we use to eliminate choices? For example, while we are reducing choices with the intersection test, whenever the count of the word choices for a given slot goes down to one, we can immediately remove that word from all other slots. However, these further removals will affect other intersection tests, and so on, with the potential for changes that ripple through the entire puzzle.

Just to keep things conceptually simple, the approach will be to define a reduction cycle that applies all three tests at least once to every component of the puzzle. This cycle will be repeated until we either solve the puzzle or stop making progress.

Here's an outline of the reduction cycle:

  1. Step through all the cells in the puzzle. For every cell that is related to both a horizontal and vertical slot, reduce the choices for both slots by applying the intersection test.

  2. Step through every slot in the puzzle. If any slot has only one choice, remove that choice from all other slots: this is the unique-word test.

  3. Step through every word in the puzzle. If any word is a choice for only one slot, remove all other choices from that slot, and remove that choice from all other slots.

Note that this steps need to know three things: what slots intersect a given cell; what word choices remain for a given slot; and which slots have a given word as a choice. See Section 4.7, “The WordBank class” for the data structures that support these features.