CSCI 136
Fundamentals of Computer Science II
Spring 2022

Montana Tech of The University of Montana
Computer Science & Software Engineering

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

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 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 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 and so that they store and operate on Positions instead of Strings. Rename them and 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 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.

The following two classes are provided for you. You do not need to alter the code in either of them, but you will need to instantiate and use them, via their methods.

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.

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

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 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 or 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.

Grade ItemPoints PossiblePoints Earned
Program Compiles and Runs
Comments on all classes and methods
Revised StackOfPositions correctly
Revised QueueOfPositions correctly
Created and drew maze correctly
Solved with stack correctly
Solved with queue correctly
Outputs number of nodes visited for both solutions
Draws correctly during solutions

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).

Submission. Submit your code,, and, using Moodle. Be sure each submitted source file has the required header with your name and a description of the program. Remember! You must also comment all of your methods, functions, and tricky bits of code! For extra-credit, please submit a single zip file containing all your programs/graphics/sounds via the special Extra Credit drop box at the top of the Moodle page. But be sure to submit your regular lab assignment in the lab 3 drop box also.

Page last updated: January 06, 2022