This chapter describes another important recursive strategy called backtracking.
A backtracking algorithm tries to construct a solution to a computational problem incrementally, one small piece at a time. Whenever the algorithm needs to decide between multiple alternatives to the next component of the solution, it recursively evaluates every alternative and then chooses the best one.
Problem Solving Using Backtracking
Backtracking is an algorithm paradigm that can be used for finding one or more solutions to certain types of computational problems. It works by incrementally building partial solutions, checking if a partial solution can be extended to a complete solution, and discarding a partial solution if it determines that it cannot be so extended. It is best understood through examples. We begin with a practical, non-computational, example. Imagine that you are in a forest without a map. The forest consists of thick brush and trees with many paths through them. You are at a point that we will call point A. You are trying to get to point B. There are many forks along the path you are on, sometimes it forks into over a dozen paths. Without a map that lets you know which paths to take, you need a methodical way to get to point B. It may even be possible that there is no path from A to B. The only thing you are guaranteed is that none of these paths are cyclical, so you will never return to a place you already visited by going straight on any path from that point. Backtracking is a method that can organize your search for B. Suppose you use the following rules:
- Walk straight until you come to a fork in the road (the end of the current partial solution) or you reach B. If you reach B, you are done (a complete solution.)
- At every fork in the road, always choose the rightmost path that you have not yet tried (a systematic way to extend a partial solution.) If, when you come to a fork, you have tried all of the paths possible at that fork already, then turn around and walk back to the closest fork you just left (this is the backtrack part), mark the branch on which you traveled back as “tried already” (a discarded partial solution), and then repeat this step.
- If walking back to the nearest fork (backtracking) brings you back to point A because all branches of the first fork failed to reach B, and there are no other branches to try at A, then there is no path to B.
This algorithm will allow you to reach B if there is a path to it. The aspects of it that make it an example of backtracking are that it methodically tries all solutions by tracing backwards when a search leads to failure and choosing the next possible search. This is an example of a problem that is considered to be solved if you find a single solution. Usually if you are lost in a forest you just want to find the way out, rather than finding all possible ways out. If we wanted to find all possible paths from A to B, then in step 1 , we would not terminate if we reached B. In addition, in step 2, we would not consider paths as being discarded unless they failed to reach B. For backtracking to be a useful technique, the problem to be solved must admit to two conditions:
- There has to be a concept of a partial candidate solution.
- There must be an efficient (fast) test to determine whether a partial solution can be completed to a valid solution.
Backtracking and Recursion
Recursion is a useful tool for writing backtracking algorithms because it implicitly traces back to the last guess for you. When a recursive function returns to the point immediately after it was called, it has traced backwards. By putting the recursive calls into either a loop or a set of cascading if-statements, you can organize the function to systematically check all possible guesses. Let’s look at some examples in the next chapters.