Type: Individual Assignment

Due: by 9:30 PM on Tuesday, October 9, 2018

Introduction

This assignment is a continuation of the Maze assignment, i.e., Assignment 3. Whereas before, we were just concerned with printing the maze, this time we will be using a stack to actually solve the maze! There are many maze-solving algorithms out there, but in particular you’ll be implementing a stack-based algorithm generally known as depth-first search and a description of the algorithm is included later in the assignment description.

Starter Code

Below is a zip file containing the starter code for the assignment.

You will need a working solution to Assignment 3 before starting the assignment. If you were pleased with your solution to that assignment, feel free to modify it directly! We have also included a sample solution in the zip above, which you are welcome to use as a starting point or for inspiration.

Note: A key piece of the sample solution is the ability to track the presence of all four walls surrounding each MazeSquare. If you only included the left and bottom walls in your implementation (or if you only included the associated string character), then you may want to use the sample solution (or at least read through it and see how that extra information is retrieved).

In this assignment, you are not required to implement a stack—instead we provide you with a working implementation named LLStack. We also include a summary of the Stack ADT it implements in the The LLStack Class section below.

For your convenience, below is a summary of all of the files included in the zip file:

  • Maze.java - This is the sample solution to the original maze assignment.
    • The MazeSquare class is implemented as a private inner class rather than a public external class.
  • LLStack.java - This is the stack class that you will use to carry out the above stack algorithm. You should not need to edit this code at all. Rather, you should be able to simply rely on the methods described in the ADT.
  • maze1.txt, maze2.txt, maze3.txt, maze4.txt - These are sample maze files that you can use to test. You may want to make some of your own, as these aren’t the only files I’ll be testing on. Note that not all of these mazes are guaranteed to be solvable.

Below we give a description of the depth-first search algorithm you will be implementing in prose.

  1. Mark every square in the maze as “unvisited.”
  2. Create an empty stack of MazeSquare objects.
  3. Push the start square onto the stack, and mark the start square as visited.
  4. Loop:
    1. If the stack is empty, then you are done and the maze is unsolvable.
    2. Otherwise, peek at the top of the stack–let’s call it T.
    3. If T is the finish square, then you are done and the stack contains a solution to the maze (with the start square at the bottom of the stack and the finish square at the top).
    4. If all of the squares that are adjacent to T in the maze (i.e., the squares up, down, left, or right from T–no diagonals) are either blocked by a wall or have already been marked as visited, pop T off of the stack and continue on.
    5. Else, select a square that is adjacent to T, unvisited, and not blocked by a wall. Mark it as visited and push it on to the stack.

The LLStack Class

The stack implementation you’ll be using for this assignment is given to you in the zip file. It is called LLStack (for “linked list stack”), and allows you to create stacks with the following methods:

Method Return Type Description
push(E item) void Add a given item to top of stack
peek() E Return the item at the top of the stack (without removing it).
pop() E Return and remove the item at the top of the stack.
size() int Return the number of items in the queue.
isEmpty() boolean Return whether or not the queue has no items.
contains(E item) boolean Return whether or not the stack contains the given item.

Note: the contains() method will be particularly useful when you want to decide whether or not to print a * character for a given MazeSquare.

Your Assignment

Your assignment is to modify Maze.java to support solving mazes using the above algorithm, and printing the solved version. Specifically, you need to add a method to Maze.java 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 LLStack 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 LLStack<MazeSquare> getSolution()

This method should then be called by the print() method so that each square in the maze that is part of the solution is marked with *. For example, if the following is input as maze.txt:

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

Then the following should be print out to the console:

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

Apart from these constraints, and the requirement that you use the algorithm specified above, how you implement this is up to you! However, here are the steps I might consider taking:

  • Add a visited instance variable to the MazeSquare class. This should be initialized to false by the MazeSquare constructor.
  • Add associated methods isVisited() (which checks to see if the MazeSquare is visited) and visit() (which changes the visited instance variable to true) to the MazeSquare class.
  • Write a helper method to the Maze class called getNeighbor(MazeSquare s, String direction) which takes in a given MazeSquare and a direction (“left”, “right”, “top”, “bottom”), and returns a reference to the MazeSquare in that direction in the maze. This will be helpful to have when writing getSolution().
  • Implement the getSolution() method, following the algorithm written above.
  • Call getSolution() in the beginning of the print() method, storing the stack it returns in a variable.
  • For each MazeSquare that you print out in the print() method, check to see if it is contained in the solution (using the LLStack’s contains() method). If it is, then write a * character in the middle.

There are other ways to go about solving this problem, but I believe that the above steps will be a good way of approaching it.

Submission and Grading

You’ll submit all your files to your Hand-in directory under a folder named assignment5.

This assignment is worth 16 points. Below is a partial list of the things that we’ll look for when evaluating your work.

  • Does your program print out a correct solution to a given maze?
  • Are you able to handle mazes that have no solution (by drawing them without a solution marked)?
  • Do you properly implement the stack algorithm to return a solution to the maze?
  • How efficient is your code? Are you looping unnecessarily through the stack data structure, or are you making good use of its constant-time operations?
  • Do your classes exhibit good organization and commenting? Don’t forget to follow the Style Guidelines!
  • Start early, ask lots of questions, and have fun! The instructor, the lab assistants, and the prefect are all here to help you succeed—don’t hesitate to ask for help!
Acknowledgments
This assignment was originally written by Jeff Ondich, with modifications by Eric Alexander and Titus Klinge.