Maze Traversal

Using recursive backtracking, implement a maze traversal program. The grid of #s and dots (.) below is a two-dimensional array representation of a maze. The #s represent the walls of the maze, and the dots represent locations in the possible paths through the maze. Moves can only be made to a location in the array that contains a dot.

# # # # # # # # # # # #
# . . . # . . . . . . #
. . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #

Specific Instructions

Write a recursive method (mazeTraversal) to walk through the maze similar to the mazes below. The method should take as argument a N-by-N, (e.g. 12-by-12) character array representing the maze and the current location in the maze (the first time this method is called, the current location should be the entry point of the maze). As mazeTraversal attempts to locate the exit, it should place the character x in each square in the path. There is a simple algorithm for walking through a maze that guarantees finding the exit (assuming there is an exit). If there is no exit, you will arrive at the starting location again.

Traversal Algorithm:

• From the current location in the maze, try to move one space in any of the possible directions (down, right, up or left).
• If it is possible to move in at least one direction, call mazeTraversal recursively, passing the new spot on the maze as the current spot.
• If it is not possible to go in any direction, “back up” to a previous location in the maze and try a new direction for that location.

Program the method to display the maze after each move so the user can watch as the maze is solved. The final output of the maze should display only the path needed to solve the maze—if going in a particular direction results in a dead end, the x’s going in that direction should not be displayed. [Hint: To display only the final path, it may be helpful to mark off spots that result in a dead end with another character (such as '0').]

Sample Run

# # # # # # # # # # # #
# . . . # . . . . . . #
x . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# . . . # . . . . . . #
x x # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# x . . # . . . . . . #
x x # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #

run:

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x . . . # # # . . . . .
# . . . . . . . . # # #
# # . . # # # . # . . #
# . # . . # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# . . . . . . . . # # #
# # . . # # # . # . . #
# . # . . # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x . . . . . . . # # #
# # . . # # # . # . . #
# . # . . # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x . . . . . . # # #
# # . . # # # . # . . #
# . # . . # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x . . . . . . # # #
# # x . # # # . # . . #
# . # . . # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x . . . . . . # # #
# # x x # # # . # . . #
# . # . . # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x . . . . . . # # #
# # x x # # # . # . . #
# . # x . # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x . . . . . . # # #
# # x x # # # . # . . #
# . # x x # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x . . . . . # # #
# # x x # # # . # . . #
# . # 0 0 # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x . . . . # # #
# # x x # # # . # . . #
# . # 0 0 # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x . . . # # #
# # x x # # # . # . . #
# . # 0 0 # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x x . . # # #
# # x x # # # . # . . #
# . # 0 0 # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x x x . # # #
# # x x # # # . # . . #
# . # 0 0 # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x x x . # # #
# # x x # # # x # . . #
# . # 0 0 # . . # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x x x . # # #
# # x x # # # x # . . #
# . # 0 0 # . x # # # #
# # # # # # # . # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x x x . # # #
# # x x # # # x # . . #
# . # 0 0 # . x # # # #
# # # # # # # x # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x x x . # # #
# # x x # # # x # . . #
# . # 0 0 # x x # # # #
# # # # # # # 0 # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . . . . .
# x x x x x x x x # # #
# # x x # # # 0 # . . #
# . # 0 0 # 0 0 # # # #
# # # # # # # 0 # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . x . . .
# x x x x x x x x # # #
# # x x # # # 0 # . . #
# . # 0 0 # 0 0 # # # #
# # # # # # # 0 # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . x x . .
# x x x x x x x x # # #
# # x x # # # 0 # . . #
# . # 0 0 # 0 0 # # # #
# # # # # # # 0 # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . x x x .
# x x x x x x x x # # #
# # x x # # # 0 # . . #
# . # 0 0 # 0 0 # # # #
# # # # # # # 0 # # . #
# # # # # # # # # # # #

Enter 'y' to continue, 'n' to exit: y

# # # # # # # # # # # #
# # . # # # . . . # . #
# # . . # . # . # # . #
# . # . # . . . # # . #
# # # . . . # # # . # #
# . # # . . # . . # # #
x x . . # # # . x x x x
# x x x x x x x x # # #
# # x x # # # 0 # . . #
# . # 0 0 # 0 0 # # # #
# # # # # # # 0 # # . #
# # # # # # # # # # # #

Maze successfully exited!