Recent Articles

Backtracking

Backtracking is a strategy for finding solutions to constraint satisfaction problems. These are problems with a complete solution, whereby the order of elements does not matter. The problems consist of a set of variables each of which must be assigned a value, subject to the particular constraints of the problem. Backtracking attempts to try all the combinations in order to obtain a solution. Its strength is that many implementations avoid trying many partial combinations, thus speeding up the running-time.

Backtracking is closely related to combinatorial search.

Implementation

Essentially, the idea is to try each possibility until you get the right one. It is a depth-first search of the set of solutions. During the search, if you try an alternative that doesn't work, you backtrack to the choice point, the place which presented you with different alternatives, and you try the next alternative. When you have exhausted the alternatives, you return to the previous choice point and try the next alternative there. If there are no more choice points, the search fails.

This is usually achieved in a recursive function whereby each instance takes one more variable and alternatively assigns all the available values to it, keeping the one that is consistent with subsequent recursive calls. Backtracking is similar to a depth-first search but uses even less space, keeping just one current solution state and updating it.

In order to speed up the search, when a value is selected, before making the recursive call, the algorithm either deletes that value from conflicting unassigned domains (forward checking) or checks all the constraints to see what other values this newly-assinged value excludes (constraint propagation).

Heuristics

Several heuristics are common to speed up the process. Because the variables can be processed in any order, it generally makes sense to try the most constrained ones first (ie. the ones with fewest options for values) as this prunes the search tree early. When choosing which value to assign, many implementations use a form of forward checking to see which value restricts the least number of future values. The philosophy behind this is to choose values that are more likely to obtain a solution quicker.

Sophisticated backtracking implementations often use a bounding function. This is specific to the problem examined and is run at every assignment step, to check whether it is still possible to obtain a solution. Thus, a simple test that immediately detects a number of partial solutions that will certainly fail, may end up cutting down the search by 99%. Because it is run at every step in what is often an exponential search space, the bounding function needs to be quite easily computable, otherwise the algorithm is no better off. Good bounding functions are created in a similar way to other heuristic functions - by relaxing the rules of the problem slightly.

Applications

Backtracking is used in the implementation of programming languages like Prolog and other areas such as text parsing.