Consider a maze made up of a rectangular array of squares, such as the following one: X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X...

Consider a maze made up of a rectangular array of squares, such as the following one:

X X X X X X X X X X X X X

X X X X X X

X X X X X

X X X X X X X X

X X X X X

X X X X X X X

X X X X X X X X X X X X X

The Xs represent a blocked square and form the walls of the maze. Let’s consider mazes that have only one entrance and one exit on opposite sides of the maze, as in our example. Beginning at the entrance at the top left side of the maze, find a path to the exit at the bottom right side. You can move only up, down, left, or right. Each square in the maze can be in one of four states: clear, blocked, path, or visited. Initially, each square is either clear or blocked. If a square lies on a successful path, mark it with a period. If you enter a square but it does not lead to a successful path, mark the square as visited.

Let a two-dimensional array represent the maze. Use a recursive algorithm to find a path through the maze. Some mazes might have more than one successful path, while others have no path.