CS 201: Data Structures

Mazes, Part 2: solving a maze

Partners: you may work alone or with a partner of your choosing

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 variously as depth-first search, backtracking, etc.

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 (and your MazeSquare.java if you have one) from Mazes, Part 1 to support solving mazes and printing the solved version. Specifically:

• Your Maze class should include a method with the following signature:

  /** * Computes and returns a solution to this maze. If there are multiple solutions, * only one is returned, and getSolution() makes no guarantees about which one. However, * the returned solution will not include visits to dead ends or any backtracks, even if * backtracking occurs during the solution process. * * @return a stack of MazeSquare objects containing the sequence of squares visited * to go from the start square (bottom of the stack) to the finish square (top of the stack). */ public Stack<MazeSquare> getSolution()

• Your program's command line should follow the syntax:

  Usage: java Maze mazeFile [--showsolution]

  For example, suppose maze.txt contains:

  6 5 0 0 0 4 L-_|_- |L--|_ |-_-|_ |L|L|| L__L__

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

  +-----+-----+-----+-----+-----+-----+ | | | | S | | | | | +-----+ +-----+ +-----+ + | | | | | | | | | | | | + +-----+ + + +-----+ | | | | | | | | | + + +-----+ + +-----+ | | | | | | | | | | | | | | | | | | | | | + +-----+ +-----+ + + | | | | F | | | | | +-----+-----+-----+-----+-----+-----+

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

  +-----+-----+-----+-----+-----+-----+ | | | | S * | | | | | +-----+ +-----+ +-----+ + | | | | | | * * * | | | | | | + +-----+ + + +-----+ | | | | * * * * | | | | | + + +-----+ + +-----+ | | | | | | | | * | | | | | | | | | | | | | + +-----+ +-----+ + + | | | | F | | | | | +-----+-----+-----+-----+-----+-----+

And of course...

Start early, ask questions, and have fun!