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:
Intersection test: where two slots intersect, they must have the same letter in that position.
So, if we look at each cell that is an intersection between two slots, clearly the letter at that cell must be one that is available in both the choices for the horizontal slot and the choices for the vertical slot.
Unique-word test: if there is only one word that fits in a given slot, that word may not be used in any other slot.
Unique-slot test: if there is only one slot that has a particular word in its set of choices, that slot must contain that word.
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:
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.
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.
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.