HW5: Mazes, Part II

25 points; due Fri 4/18 @ 11am.

Goals

To use the Stack ADT to solve a maze.

Setup and Requirements

The code that you write for this assignment will build on top of two ADTs (List and Stack) and their implementations. You must use the ADT interfaces and implementations I provide, not the Java Standard Library ones. The five files you will need are:

Do not modify the provided .java files (or the .class files, for that matter). None of these five files should be part of your submission for this assignment, either; only turn in the code you wrote.

Every source-code file you turn in must have your name in a comment at the top.

This is optionally a partner assignment. If you worked alone on the last assignment, you must work alone on this one too; if you work with a partner on this assignment, it must be the same partner as last time. Make sure to put both people's names at the top of each file. Write your code by pair-programming: code together, at the same computer, and switch off who's at the keyboard. Only one of you should ultimately submit your team's code via Moodle.

Specification

In this assignment, you will build on your work from the previous assignment to write a program that solves mazes. I'm giving you the algorithm to use to solve a maze; you just have to implement it.

The algorithm, in prose

  1. Read in the maze description from a file.
  2. Mark every square in the maze as unvisited.
  3. Create an empty stack of maze squares.
  4. Push the start square onto the stack, and mark the start square as visited.
  5. If the stack is empty, you're done and the maze is unsolvable. Otherwise, let $T$ be the top item on the stack.
  6. If $T$ is the finish square, you're done and the stack contains a solution to the maze.
  7. 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 5.
  8. Otherwise, select a square $S$ that is adjacent to $T$, unvisited, and accessible from $T$ (no wall between them). Mark $S$ as visited and push it on the stack. Go to step 5.

Your job

Supplement your Maze.java from the last assignment to support solving mazes and printing the solved version.

Specifically:

Submission and Grading

Submit your Maze.java file on Moodle. (Only one submission per pair!)

Start early, ask lots of questions, and have fun!

Grading

This assignment originally designed by Jeff Ondich. Thanks for sharing, Jeff!