Next / Previous / Contents / Shipman's homepage

4.6. The recursive algorithm

As discussed in Section 4.3, “Overview of the solution algorithm”, recursive solution relies on organizing the set of slots into an ordered set. Once we know which slot is considered the first slot, we try all the different choices for the first slot, then try all the different choices for the second slot, and so forth until we either reach a solution, or we reach a contradiction—where there are no remaining candidates for a given slot.

The recursive method for a given slot assumes that all previous slots have been solved (that is, that each has exactly one word choice remaining). The recursive method is a generator: it generates all the solutions that start at the current state of the puzzle, if there are any solutions based on the current state.

The basis case for recursion is when we reach the last slot and there is only word that fits that slot. This means that the current state is a solution to the puzzle, so the method yields self, which is yielded back through all the recursive layers and finally yielded by the first-level method of the recursive algorithm.

If we reach a slot and there are no choices left for the slot, the recursive method raises a StopIteration exception to signify that there are no solutions based on the current state.

The general case is when the current slot has multiple choices remaining. This case is easy to describe in general: we try each of the remaining choices for the current slot, and for each choice, try recursively to solve the remaining slots.

This is tricky because we may have to backtrack some of the actions that occur during recursive solution.

For example, suppose we only have three unsolved slots: call them A, B, and C, in order.

So we pick one of the words that is still a choice for slot A, and recur until we reach the recursion for slot B. At that point we pick the first choice for slot B and recur. But then suppose later we find that with those choices for slots A and B, none of the choices for slot C work anymore.

At that point, the choices that we removed from slot C must be put back. This is where the backtracking comes in.

So the backtracking is handled in the recursive algorithm in this way. At this point, we are assuming that the current slot is not the last slot, and that there are two or more choices for that slot.

  1. Remember the current set of choices for the slot.

  2. Temporarily remove all those choices from the slot.

  3. For each of the original choices:

    1. Reinstate that choice for this slot.

    2. Recursively call the solver method starting at the following slot.

    3. Remove that same choice from the slot's choices.

  4. Reinstate all the original choices for this slot.