9.6 Backtracking

The most basic problem-solving technique in computer science is the \Term{brute-force} method. It involves searching for a solution to a given problem by systematically trying all possible candidates until either a solution is found or it can be determined there is no solution. Brute-force is time-consuming and is generally chosen as a last resort. But some problems can only be solved using this technique.

If applied to the maze problem, the brute-force method would require we start at the beginning and follow a path until we either find the exit or encounter a blocked passage. If we hit a wall instead of the exit, we would start over from the beginning and try a different path. But this would be time consuming since we would likely follow part of the same path from the beginning to some point before we encountered the blocked passage. Instead of going all the way back to the beginning, we could back up along the path we originally took until we find a passage going in a different direction. We could then follow the new passage in hopes of finding the exit. If we again encounter a blocked passage before the exit, we can back up one or more steps and try a different passage.

This process of eliminating possible contenders from the solution and partially backing up to try others is known as \Term{backtracking} and is a refinement of the basic brute-force method. There is a broad class of algorithms that employ this technique and are known as \Term[backtracking]{backtracking algorithms}. All of these algorithms attempt to find a solution to a problem by extending a partial solution one step at a time. If a ``dead end'' is encountered during this process, the algorithm backtracks one or more steps in an attempt to try other possibilities without having to start over from the beginning.

Designing a Solution

he solution to the maze problem is a classic example of backtracking. In this section, we explore the technique and design a solution to the maze problem.

Problem Details

Given a maze with indicated starting and exit positions, the objectives are (1) determine if there is a path from the starting position to the exit, and (2) specify the path with no circles or loopbacks. In designing an algorithm to solve a maze, it will be easier if we think of the maze as a collection of equal-sized cells laid out in rows and columns, as illustrated in \xref{fig:maze:cells}. The cells will either be filled representing walls of the maze or empty to represent open spaces. In addition, one cell will be indicated as the starting position and another as the exit.

\begin{figure}[htb] \vspace*{-1ex} \inputpic[0.8]{mazecells} \Caption{fig:maze:cells} {Sample maze from \xref{fig:maze:example} divided into equal-sized cells.} \end{figure}

To further aide in the algorithm development, we place certain restrictions on movement within the maze. First, we can only move one cell at a time and only to open positions, those not blocked by a wall or previously used along the current path. The latter prevents us from reusing a cell as part of the solution since we want to find a path from the start to the exit without ever having to go in circles. Finally, we limit movement between opens cells to the horizontal and vertical directions---up, down, left, and right---as illustrated in \xref{fig:maze:moves}.

\begin{figure}[htb] \vspace*{-1ex} \inputpic[0.8]{mazemoves} \Caption{fig:maze:moves} {The legal moves allowed from a given cell in the maze.} \end{figure}

During our search for the exit, we need to remember which cells have been visited. Some will be part of the final path to the exit while others will have led us to dead ends. At the end, we need to know which cells form the path from the start to the exit. But during the search for the exit, we also need to avoid cells that previously led to a dead end. To assist in remembering the cells, we can place a token in each cell visited and distinguish between the two. In our example, we will use an \texttt{x} to represent cells along the path and an \texttt{o} to represent those that led to a dead end.

Describing the Algorithm

We begin at the starting position and attempt to move from cell to cell until we find the exit. As we move between cells, we must consider what actions are available at each cell. Consider the smaller maze in \xref{fig:maze:small} in which the rows and columns have been numbered to aide in identifying the cells.

\begin{figure}[htb] \inputpic{smallmaze} \Caption{fig:maze:small} {A small maze with the rows and columns labeled for easy reference.} \vspace*{-1ex} \end{figure}

Finding the Exit.From the starting position $(4,1)$, we can examine our surroundings or more specifically the four neighboring cells and determine if we can move from this position. We want to use a systematic or well-ordered approach in finding the path. Thus, we always examine the neighboring cells in the same order: up, down, left, and right. In the sample maze, we find the cell above, $(3,1)$, is open and prepare to move up one step. Before moving from the current position, however, we need to lay down a token to indicate the current cell is part of our path. As indicated earlier, we place a lowercase \texttt{x} in the cell to indicate it comprises part of the path. The complete set of steps taken to solve our sample maze are illustrated in \xref{fig:maze:path}.

\begin{figure}[htb!] \inputpic*[0.8]{2.5em}{mazepath} \vspace*{1ex} \Caption{fig:maze:path} {The sequence of steps taken through a sample maze from the starting position (\texttt{S}) to the exit (\texttt{E}). The path is marked using an \texttt{x}, while the current cell is marked with \texttt{X}. Visited cells from which we had to backtrack are marked with \texttt{o}. } \end{figure}

After placing the token, we move to the open cell above the starting position. The current position in the maze is marked in the illustration using an uppercase \texttt{X}. We repeat the process and find the cell above our current position is open. A token is laid in the current cell and we move up one position to cell $(2,1)$. From our vantage point above the matrix, we easily see the solution to the problem, which requires that we move to the right. But from the point of view of a mouse searching for cheese, that specific move would be unknown.

Using our systematic approach, we examine the cell above our current position. We find it open, and move up one position to cell $(1,1)$. From this position, we soon discover there are no legal moves since we are blocked by a wall on three sides and a cell comprising part of our path. Since we can go no further from this cell, we have no choice but to go back to our previous position in cell $(2,1)$. When hitting a dead end, we don't simply turn around and go back over a cell previously visited as if it were part of the path since this would cause a circle. Instead, we mark the cell with a different token indicating a dead end and move back to the previous position. In our example, we use a lowercase \texttt{o} to represent a cell leading to a dead end.