CS 201: Data Structures

Mazes, Part 1: solving a maze

Hand in via Moodle as Maze.java

Please continue to work with your partner from Mazes, Part 1.

Goals

• Use a stack to solve a non-trivial problem.
• Implement a classic example of a backtracking algorithm.
• More Java practice.

For this assignment, you will use a stack to solve mazes stored in text files as described in Mazes, Part 1. Though there are many maze-solving algorithms, we'll use a stack-based algorithm known both as backtracking and depth-first search.

The algorithm, in prose

1. Mark every square in the maze as unvisited.
2. Create an empty stack of maze squares.
3. Push the start square onto the stack, and mark the start square as visited.
4. If the stack is empty, you're done and the maze is unsolvable.
5. Let T be the top item on the stack. If T is equal to the finish square, you're done and the stack contains a solution to the maze.
6. If all squares adjacent to T (i.e. the squares up, down, right, or left from T--no diagonal adjacency) are either blocked from T by a wall or are marked visited already, pop T off the stack and go to step 4.
7. Otherwise, select a square S that is adjacent to T, unvisited, and accessible from S (no wall between them). Mark S as visited and push it on the stack. Go to step 4.

Your job

Supplement your Maze.java from Mazes, Part 1 to support solving mazes and printing the solved version. Specifically:

Your program's command line should follow the syntax:

For example, suppose maze.txt contains:

then "java Maze maze.txt" should print the maze with no solution, like so:

On the other hand, "java Maze maze.txt --showsolution" should print the maze with the path of the solution marked, like so:

Some mazes may have multiple solutions. For example, the maze shown above displays a solution that's two steps longer than necessary. This happened because my algorithm explored squares moving to the right before exploring squares moving down. Your program need not find the shortest path; any path that crosses no walls is acceptable.

Important note

It is possible to abandon the stack-based algorithm outlined above and write your maze-solving code recursively. Don't do that for this assignment. The main thing we'll do to follow up on this assignment is to discuss the very close relationship between recursion and stacks. I want you to solve a significant problem with a stack before we go back and compare your stack-based solution to a recursive solution.

Also, there's a powerful algorithm called Dijkstra's algorithm that can be adapted to solve a maze, with the additional benefit of guaranteeing you a shortest possible solution. Don't try to do that, either. We'll get to Dijkstra's algorithm in March. Right now, just use the algorithm above.

And of course...

Start early, ask questions, and have fun!