To find the path through the maze you may proceed as follows: Begin with the entrance as your starting position.

If the present position is the exit, then you have found a path and you are done. If you are not at the exit, then block the present position (i.e., place an obstacle there) so as to prevent the search from returning here. Next see whether there is an adjacent maze position that is not blocked.

If so, move to this new adjacent position and attempt to find a path from there to the exit.

If unsuccessful, attempt to move to some other unblocked adjacent maze position and try to find a path from there.

To facilitate this move, save the current position on a Stack before advancing to a new adjacent position.

If all adjacent unblocked positions have been tried and no path is found, there is no path from entrance to exit in the maze.

A maze is a rectangular area with an entrance and an exit. The interior of the maze contains walls or obstacles that one cannot walk through. In our mazes these obstacles are placed along rows and columns that are parallel to the rectangular boundary of the maze. The entrance is at the upper-left corner, and the exit is at the lower-right corner. Suppose that the maze is to be modeled as an n by m matrix with position (1,1) of the matrix representing the entrance and position (n,m) representing the exit. n and m are, respectively, the number of rows and columns in the maze. Each maze position is described by its row and column intersection. The matrix has a 1 in position (i, j) if there is an obstacle at the corresponding maze position. Otherwise, there is a 0 at this matrix position. Below is an illustration of a sample maze and a corresponding matrix representation of that maze. Entrance Exit