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, according to its removal strategy, 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.py code so that it works with Positions instead of Strings. You will also need to modify the QueueOfStrings.py code to do the same. You do not need to do anything to the Maze.py or Position.py, files. All the files you will need to complete the assignment can be found in Lab3Student.zip

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 import StdDraw.py in your code and have it and its associated python files in the same folder as your code so that the display works.

The main part of your assignment is to write a program called Solve.py 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 1: Modify the files StackOfStrings.py and QueueOfStrings.py so that they store and operate on Positions instead of Strings. Rename them StackOfPositions.py and QueueOfPositions.py. Don't forget to update the documentation to indicate the changes and add your name as an author. You should add comments for the class and all methods.

Part 2: Write a program called Solve.py 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.RED, and each visited Position in StdDraw.BOOK_LIGHT_BLUE.

Then clear the maze (though not necessarily the drawing of the maze) by calling the appropriate Maze method and solve the maze using your QueueOfPositions. This time draw new Positions in StdDraw.DARK_RED 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.

class Position
-----------------------------------------------------------------------------------------
        __init__(int x, int y)  # create a position at maze coordinates x, y 
    int getX()                  # returns the x position
    int getY()                  # returns the y 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
 string toString()              # returns a string representation of a Position

Maze. The Maze class represents the 2D grid of positions that make up a maze. Fo reach position in the maze, it keeps track of whether there are walls to the north, east, south or west, and whether that position has already been visited.

class Maze
-----------------------------------------------------------------------------------------
         __init__(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 maze
    void setVisited(Position p)# sets the visited flag for that Position in the maze to true
 boolean isVisited(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 Autograder.py program for this code? No, not this time. Since 1), the mazes are generated at random, and 2) there is no required API (see below), there is no way to write code that can compare your answers to known answers in advance. Sorry - next time?

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, however. You may not, modify the Maze.py or Position.py code.

Can I use Python's built in Stack and Queue classes? Absolutely not!!! I want you to use the provided code that you can look at and can modify, not Python 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 and why you think that is.

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

Page last updated: January 06, 2022