9.5 Application: Solving A Maze

A classic example of an application that requires the use of a stack is the problem of finding a path through a maze. When viewing a maze drawn on paper such as the one illustrated in XYZ, we can quickly find a path from the starting point to the exit. This usually involves scanning the entire maze and mentally eliminating dead ends. But consider a human size maze in which you are inside the maze and only have a "rat's-eye" view. You cannot see over the walls and must travel within the maze remembering where you have been and where you need to go. In this situation, it's not as easy to find the exit as compared to viewing the maze on paper.

An algorithm that can be used to find a path through a maze is likely to employ a technique similar to what you would use if you were inside the maze. In this section, we explore the backtracking technique to solving a maze and design an algorithm to implement our technique.

\begin{figure}[htb] \vspace*{-1ex} \inputpic[0.8]{examplemaze} \Caption{fig:maze:example} {A sample maze with the indicated starting (\texttt{S}) and exit (\texttt{E}) positions.} %\vspace*{-1ex} \end{figure}