Please continue to work with your partner from Mazes, Part 1.
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.
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.
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.
Start early, ask questions, and have fun!