ASSIGNMENT #3 - Maze - Stacks and Queues

In this assignment, you will be you will be using stacks and queues to solve a maze.

Solving a Maze. Data structures can help you solve problems directly rather than trying to write brute force code. Solving a maze is one of these problems. The idea is simple. Each time you visit a location, you add that position to your data structure and mark that you have visited that location. You keep exploring the maze in this manner until you run into a dead end (you are blocked by walls and the only way to get out is to retrace your steps, that is, move to spaces that have already been visited). When you run into a dead end, you simply remove a location from the data structure and set it as your current location.

For this assignment, you have been provided with the code that generates and draws a maze, and also with a class called Position that stores, well, positions. You will need to modify the StackOfStrings.java code, available here, so that it works with Positions instead of Strings. You will also need to modify the QueueOfStrings.java code, available here, to do the same. You do not need to do anything to the Maze.java, available here, or Position.java, available here, files.

The Maze knows how to draw itself, and Positions also know how to draw themselves, so you need not write code to do the display. You will have to write code that calls the method to draw Positions, though. You will need to have StdDraw.java in your source code directory so that the display works.

The main part of your assignment is to write a program called Solve.java that solves the maze in two ways; one using the stack data structure, and the other using the queue data structure. Remember that adding and removing from stacks and queues happens in a different order, so you should see different behavior for both solutions.

Part 2: Write a program called Solve.java that creates a Maze using a command line argument for the dimension, n. Draw this maze, solve it using your StackOfPostions, drawing each new Position in StdDraw.BLUE, and each visited Position in StdDraw.GRAY.

Then clear the maze by calling tha appropriate Maze method and solve the maze using your QueueOfPositions. This time draw new Positions in StdDraw.GREEN and visited Positions in StdDraw.LIGHT_GRAY.

For each solving method, keep a count of how many nodes were added to the data structure in order to get to a solution, and print these out to the console.

Position. The Position class represents a location in the maze. It only knows its x and y position. The maze class keeps track of what has been visited or not

Here is the API you can use from the Position class. You do not need to modify this code.

public class Position
-----------------------------------------------------------------------------------------
        Position(int x, int y)  // create a position at maze coordinates x, y 
    int getX()                  // returns the x position
    int getY()                  // returns the x position
   void draw(Color color)       // draws the position as a circle of the specified color
boolean equals(Position p)      // return true if the Position is equal to the one passed
                                //     in, false otherwise

public class Maze
-----------------------------------------------------------------------------------------
         Maze(int n)           // create a maze with dimension nxn 
Position getStart()            // returns the start Position
Position getFinish()           // returns the finish Position
 boolean openNorth(Position p) // returns true if there is no wall to the north, false otherwise
 boolean openSouth(Position p) // returns true if there is no wall to the south, false otherwise
 boolean openEast(Position p)  // returns true if there is no wall to the east, false otherwise
 boolean openWest(Position p)  // returns true if there is no wall to the west, false otherwise
    void draw()                // draws the position as a circle of the specified color
    void setVisited(Position p)// sets the visited flag for that Position in the maze to true
 boolean visited(Position p)   // return true if the Position has been visited, false otherwise
    void clear()               // clears all visited flags from the maze so another solution can be started

Is there an API I need to follow for my Solve program? No, not this time. You are free to define whatever methods you want. Be sure to document them using javadoc, however. You may not, modify the Maze.java or Position.java code, though.

Can I use Java's built in Stack and Queue classes? Absolutely not!!! I want you to use code that you can look at and have modified, not Java library code.

Extra credit idea 1. Run your code several times and watch the behavior of the two solutions. Submit a write up of which one does better under what circumstances.

Extra credit idea 2. Research other "search" methods and implement one that is more intelligent. Hint: You might google A*.

Page last updated: December 27, 2018