Backtracking. The Concept

Backtracking is a problem solving technique that involves examining all possibilities in the search for a solution. An example of backtracking can be seen in the process of finding the solution to a maze. During the exploration of a maze, we have to make decisions involving which path to explore. When faced with a choice of paths to explore, we decide whether to go north, south, east, or west. A backtracking approach to find our way through a maze involves considering all possible paths until we find a solution.

Figure 1 A maze

Backtracking involves pursuing one possible solution until the algorithm determines that it is or is not a solution. If a backtracking algorithm discovers a chosen possibility is not a solution, the algorithm "backs up" and chooses to pursue another possibility from the set of possible solutions. For example, the mouse needs to find the solution to the maze in order to get to the cheese in Figure 1. Let's place ourselves in the mouse's situation and see how we can use backtracking to find the solution. Immediately, at position A, we have a choice between moving north or south. For the sake of the example, we will choose north, but we will remember that there is another path leading south that we have not explored. Going north, we find out quickly that the path leads to a dead end. In this situation, we must backtrack to position A and visit the path we did not choose. Moving south from position A, another choice appears at position B where we can continue to move south or change direction and explore the path to the east. If we choose to go east, we will surely have to make many other decisions on which paths to take as we continue to explore. If one of these paths leads to the solution, our search is complete. If all paths branching off to the east lead to dead ends, we must backtrack to position B and explore the path that leads south. This process is guaranteed to find a solution to the maze since it considers all possible paths.

Backtracking algorithms that use recursion operate basically the same way as other recursive algorithms. Similar to any other recursive algorithm, programmers design backtracking algorithms around base cases that are solved without recursion. In the maze example, the base case exists when the mouse is adjacent to the exit of the maze (at position C). In this situation, the choice to go east is obvious and a recursive search is not needed. Recursive backtracking algorithms also reduce a problem to a smaller sub-problem. The recursion, applied in the maze example, effectively makes the maze smaller and smaller until it reaches the base case.

An Example: Eight Queens