Breadth First (FIFO) vs. Depth First (LIFO) Search

Overview

In this final part of the lab, we will create two children classes of MazeSolver that use either a queue or a stack to represent the exploration collection in order to change the order (FIFO vs. LIFO) that we explore paths through the maze to find its solution.

Implementing MazeSolverQueue

In Visual Studio Code, create a new file called MazeSolverQueue.java. Within this file, you should create a new class called MazeSolverQueue that extends MazeSolver.

As the class name suggests, we will use a queue to represent our exploration collection in our MazeSolverQueue class. Your MazeSolverQueue should have a MyQueue<Square> as its only additional instance variable (not inherited from MazeSolver). The constructor should call the parent class’s constructor (using super(maze)), then create a new empty MyQueue<Square> instance variable. Using a queue for our exploration collection will cause us to implement the popular Breadth First Search algorithm.

README

Similar to the previous labs, you should use your MyQueue class to receive full credit in this part of the lab. However, if you had difficulties completing MyQueue, you can still use one of Java’s built-in queue classes for partial credit. We recommend using Java’s LinkedList class since it also implements the Queue interface described in Part 1.

There are four abstract methods in the MazeSolver parent class that you will need to implement:

  1. public void add(Square sq) should add a given Square sq to the end of the queue.
  2. public Square next() should return the Square at the the head of the queue.
  3. public boolean isEmpty() should return whether your queue is empty or not.
  4. public void makeEmpty() should remove all of the items in the queue.

Implementing MazeSolverStack

In Visual Studio Code, create a new file called MazeSolverStack.java. Within this file, you should create a new class called MazeSolverStack that extends MazeSolver.

As the class name suggests, we will use a stack to represent our exploration collection in our MazeSolverStack class. Your MazeSolverStack should have a MyStack<Square> as its only additional instance variable (not inherited from MazeSolver). The constructor should call the parent class’s constructor (using super(maze)), then create a new empty MyStack<Square> instance variable. Using a stack for our exploration collection will cause us to implement the popular Depth First Search algorithm.

README

Similar to MazeSolverQueue above, you should use your MyStack class to receive full credit in this part of the lab. However, if you had difficulties completing MyStack, you can still use Java’s built-in Stack class for partial credit, which uses the same method names described in Part 2.

Again, we will need to implement four abstract methods from the MazeSolver parent class:

  1. public void add(Square sq) should add a given Square sq to the top of the stack.
  2. public Square next() should return the Square at the the top of the stack.
  3. public boolean isEmpty() should return whether your stack is empty or not.
  4. public void makeEmpty() should remove all of the items in the stack.

Running the MazeApp Application

If everything is working in your MazeSolver classes, you should be able to run the MazeApp program and get a GUI interface that will allow you to visualize the process of finding the solution of the maze! You do not need to modify anything in the MazeApp class.

The load and quit buttons operate as you might expect. The reset button will call the Maze’s reset() method and then create a new MazeSolver. If you click on the Stack button it will toggle between using a MazeSolverStack or MazeSolverQueue to solve the maze. The step button performs a single step() of the MazeSolver that you implemented and start will animate the entire solving process, taking one step per timer delay interval. As the animation proceeds, marked squares are painted gray. If the maze is solved, the squares on the solution path are painted yellow. The path your solution finds is displayed in the bottom panel.

If you solve the same maze with a queue and then a stack, you should see the solver explore the various squares (painted gray) in different orders. For some mazes (such as maze-7), you might even find that one solution takes fewer steps (i.e., explores fewer possible paths and locations) before finding a solution.

Committing Your Progress

Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.