Project 3 - Recursive Backtrace Mazes

Due by 11:59pm on November 12, 2025

Warning
This project will be a bit of a transition from previous ones, we will not walk you through every step of the implementation. Instead, we will give you all the implementation requirements and an outline of how to structure your program with any necessary algorithms and leave the actual design of the code up to you.

This means you will want to read this write-up very closely and throughly before you begin writing code. If you don’t, you will likely miss things and get frustrated.

Don’t say we didn’t warn you!

Objectives

Practice using recursion.
Utilize file I/O to read and write a file in a specific format.
Utilize and manipulate data structures.
Practice thinking critically to solve a problem in a generic case.

Outline

We want to build a program to help us create and solve mazes. Luckily for us, recursion is a super useful tool for doing this!

Solving Mazes

Essentially, given a .txt file that has a maze that looks like this:

#######
#S    #
# ### #
# #   #
#   #E#
#######

We want to make a program to read in the maze and solve it. For consistency, we will have the computer try and to make a move in each of the four cardinal directions. It should follow the following order, attempting each until it can continue, or it runs out of directions to try:

East (right)
West (left)
South (down)
North (up)

If the program is successful, it should continue along that path attempting to find the E representing the end of the maze.

If the program runs into a wall (#) it should try moving in all the other directions, and then if that still fails, it should trace its steps backwards and try going other directions in the path it’s been taking (this is where the recursion comes in, but more on that later).

Eventually, when the program is successful, it should print out the path it found from S to E and that is the solution to the maze. It is important to note that the path it finds may not be the only valid solution or even the shortest solution.

Keeping with the example above, the program should print the following when run in solving mode:

Success! The path is as follows:
#######
#S....#
# ###.#
# #  .#
#   #E#
#######

Example Solving Inputs

Command Format

python3 maze_solver.py -s <filename>

Example 1

Command:

python3 maze_solver.py -s test_files/maze0.txt

`test_files/maze0.txt`	Prints
`####### #S # # ### # # # # # #E# #######`	`Success! The path is as follows: ####### #S....# # ###.# # # .# # #E# #######`

Example 2

Command:

python3 maze_solver.py -s test_files/maze2.txt

test_files/maze2.txt Prints

`test_files/maze2.txt`	Prints
######################### #S# # # # # ### ####### # # ### # # # # # # # # # # ######### ### ### # ### # # # # # # # # # # ### # # ### ### # # # # # # # # # # # # # # # ### # ### ### # # ### # # # # # # # # ##### ####### ### # # # # # # # # # # # # # ######### # # # ### # # # # # # # # # # ##### # # # # ### ### # # # # # # # # ##### # # ########### ### # # # # # # # # # ### ### ### ####### # # # # # # # # # # ### ####### # # # # ### # # # # # # # # ########### ##### # # # # # E# #########################	Success! The path is as follows: ######################### #S# .........# .....# # #.###.#######.# #.###.# # #.....# #.# #.#...# # ######### ###.###.#.### # # #..... #...#...#.# # # #.###.# #.###.###.# # # #...# #.# #.# .# #.# # # #.### #.###.###.# #.### # #.....#.....#...# #.#...# #####.#######.### #.#.#.# # #.......#.# #...#.#.# # #########.#.# #.###.#.# # #.#.#...#...#.# # ##### # #.#.#.###.###.# # # # #...#.....#...# ##### # # ###########.### # # # # # #...# # # ### ### ### #######.# # # # # # # #...# # ### ####### # # # #.### # # # # #.# # # ########### ##### #.# # # # ..E# #########################

#########################
#S#           #       # #
# ### ####### # # ### # #
#     #     # # # #   # #
######### ### ### # ### #
# #       #   #   # #   #
# # ### # # ### ### # # #
#   # # # # #   # # # # #
# ### # ### ### # # ### #
#     #     #   # # #   #
##### ####### ### # # # #
#   #       # # #   # # #
# ######### # # # ### # #
#         # # #   #   # #
# ##### # # # # ### ### #
#     # # #   #     #   #
##### # # ########### ###
# #   # # #         #   #
# # ### ### ### ####### #
# #   #     # # #   #   #
# ### ####### # # # # ###
#   #         #   # # # #
# ########### ##### # # #
#                 #    E#
#########################

Success! The path is as follows:
#########################
#S#  .........#  .....# #
#.###.#######.# #.###.# #
#.....#     #.# #.#...# #
######### ###.###.#.### #
# #.....  #...#...#.#   #
# #.###.# #.###.###.# # #
#...# #.# #.#  .# #.# # #
#.### #.###.###.# #.### #
#.....#.....#...# #.#...#
#####.#######.### #.#.#.#
#   #.......#.# #...#.#.#
# #########.#.# #.###.#.#
#         #.#.#...#...#.#
# ##### # #.#.#.###.###.#
#     # # #...#.....#...#
##### # # ###########.###
# #   # # #         #...#
# # ### ### ### #######.#
# #   #     # # #   #...#
# ### ####### # # # #.###
#   #         #   # #.# #
# ########### ##### #.# #
#                 #  ..E#
#########################

Representing A Maze File In Python

Hopefully you’ve been thinking about how you could represent the data of a maze file in memory. There are many ways to do it, but one of the easiest is to look at the code that we have already written for this class and see if there is a Python class we’ve written that could be extended to work well for a maze.

Hint
This is a 2D structure, what could you use that you’ve already written for a 2D structure to save you a lot of time?

Additionally, if you are having a hard time thinking about how you might read the maze file in and turn it into a structure you can work with, consider reviewing those topics in previous labs:

Recursive Backtrace Algorithm

Note
This algorithm operates on the same concept as the one you used in Lab 17 but has simply been extended in its complexity see if you can pick out how we have changed it from there to the way we use it here.

The first step in the algorithm is to find the start of your maze. In our case the start is represented by the S character at some point in the maze. It would probably make sense to write a function to search the maze, find the S and return its coordinates.

Once you have the start coordinates, we want to find the path from that point that leads us to the end (E) without crossing any walls.

We want a recursive function that should be able to find our path given the coordinates of S. It will need to do a few things to make sure that it ends up going in the right directions to find the end:

Check the value at the x and y coordinates.
- E (End): Stop searching! You’ve found the end, you can break the recursive loop and return a successful value to propagate the result.
- # (Wall) or . (Marked): Path is blocked, return a value that will indicate that your current path cannot be followed any further.
- (Blank) and not S: mark as visited by using a ..
Recursively call this function in each of the directions in the order specified above.
- If you get a successful value from a direction, that means you found a solution. Return a success value to propagate the result upward in your recursive call stack.
If none of the directions are successful, backtrack by unmarking your cell (set it back to ), so that only the correct path is ultimately marked.
- Return a failure value so your caller can try another route.

If you make it all the way to the top of your recursive call stack with a status that indicates you were not successful, no possible solutions exist. You should report that to the user. See No Solution to Maze below for exactly what to report to the user.

Generating Mazes

The other main functionality of the program is using recursion to generate a new maze. The program should take in the width and height of the maze as well as the filename that the end maze will be written to. Your program will carve a path starting just inside the top left at 1,1. The program must slightly edit the input width and height to ensure that they are rounded up to be an odd value if the input is even. This is necessary to ensure that we can easily generate a maze with walls on all of the outside bounds with the algorithm we have given you. This means that if you were given an input width of 20 × 20, it would become 21 × 21.

Note
When generating a maze, the minimum size is a 3 × 5 maze. Any smaller than that will be too small to meet the maze file standard we have defined for this project and should be reported to the user. See Invalid Maze Size below for exactly what to report to the user. Because of the rounding we have instructed you to perform, this means that you have an edge case with the input of 2 × 4.

It is up to you to determine if this is a valid input or not for your implementation. We won’t test you on it, but it is important to note that these sorts of edge case issues often come up in the real world. It’s important to think about them and determine how you will treat them so they don’t come back to bite you when the end user finds them and gets frustrated, or even worse, they end up becoming bugs.

Example Generating Inputs

Note
Please note that for these examples it will be different when you run them because we are using a random function.

When running your tests in the autograder, we set a constant seed value so that if you have implemented your code correctly, it will generate the same results as the test files.

Command format

python3 maze_solver.py -g <width> <height> <filename>

Example 1

Command	Creates `example1.txt`
`python3 maze_solver.py -g 5 4 example1.txt`	`##### #S# # # # # # E# #####`

Example 2

Command	Creates `example2.txt`
`python3 maze_solver.py -g 8 10 example2.txt`	`######### #S # ####### # # # # # ### # # # # # # # ##### # # # # # # # ### # # E# #########`

Recursive Generation Algorithm

You’ll want to create a structure full of walls that we will then carve a maze in. Once you have the walls everywhere, we want to start carving a path from the top left corner.

Note
We want an outer wall everywhere, so you’ll need to shift your starting point for carving in by one unit in both directions to accommodate for that.

The recursive algorithm for carving a path in the maze is defined as follows:

Set the value at your x and y coordinates to be a part of the path ( ).
Define a list of possible directions in the same order defined above.

Important
It is essential that you define them in this order so that the autograder can accurately test your random generation. If your code is able to generate a properly formatted maze, but it does not pass the autograder, this is likely the issue.

Hint
How could you create a list of directions with only four items (one for each direction), yet still containing both an x and a y value for each direction? Is there a native python structure that could be used to accomplish that?

Unlike in solving mazes, we want to ensure our movement in each direction is two units.
Use random.shuffle() to shuffle the list of directions.
For each direction in your directions list:
- Calculate the new coordinates two units away in the given direction.
- If the new position is within bounds and unvisited (still #):
  - Identify the intermediate position between the current and new location.
  - Mark the intermediate position as a part of the path ( ).
  - Recursively apply the same process from the new position.

Once we carve our path, we still need to insert our start and end. Our start should be set at the same location we started carving our path from (i.e. the top left corner). Our end should be set in the bottom right corner. For both of these, remember to take into account the outer wall and set them inside of that boundary.

Implementation Requirements

The maze_solver.py program should accept arguments indicating what operation it should perform. The two operations for this project are defined by flags that will be passed as arguments to the program:

-s will start solving a maze
- maze_file is the only other argument taken in this mode and should be a .txt file containing the maze to solve
-g will start generating a maze
- width width of the maze to generate
- height height of the maze to generate
- maze_file the output .txt file to save the generated maze to

Example Inputs

Solve Mode: see above.

Generate Mode: see above.

Handling Errors

When maze_solver.py is passed invalid input arguments, or encounters an exception while performing any operations, it should print a user friendly message indicating an error has occurred and why.

Error Examples

No Solution to Maze

If there is no solution to an input maze file, your program should report that condition to the user. For grading purposes, your program should print a message starting with Error and then containing the words no solution somewhere in the full message

python3 maze_solver.py -s bad_maze.txt
Error! Solver could find no solution to maze!

Invalid or Missing Arguments

python3 maze_solver.py -s
Usage: python3 maze_solver.py [-s maze_file] [-g width height maze_file]

Your implementation can change the names representing the inputs, but your help message should contain Usage: and then each of the operation flags with their corresponding inputs.

Invalid Maze Size for Generation

python3 maze_solver.py -g 3 3 maze.txt
Error! Minimum maze size is 3x5!

Your implementation should contain Error and then indicate to the user that the minimum maze size is 3×5.

Generic Errors

Any other errors encountered should be caught instead of having the program crash. Instead, follow the pattern of printing Error followed by a brief description of the issue that was encountered.

Hint
You should use the string representation of any exceptions that you catch as the description of the issue when possible.

Implementation

Download the starter files from project03.zip, unzip, open up the maze_solver.py file in your editor, and write your code in there.

You are welcome to write additional code in other files and import them into your maze_solver.py file and use them as a part of your maze solver, but make sure that you also submit those files when you submit for grading, or you won’t be able to pass the tests.

You are welcome to implement the project in whatever order you think makes the most sense, just make sure you understand what is expected and then get started!

Submission / Grading

Once you have implemented this project as specified, you can run the pytests to test it:

pytest test_maze_solver.py

Once you pass all the tests, submit your code to Gradescope through Canvas. In addition to the tests, you will be graded by a TA on your implementation. The TA’s will be looking for the following:

Did you use code written elsewhere in the class where applicable? (5pts)
Did you follow the general course coding guidelines? (5pts)
Did you refactor your code to reduce duplication and reuse methods where applicable? (5pts)
Does your program give helpful error messages when applicable? (5pts)
Does your code accurately meet all implementation requirements? (5pts)

Implementation grading will be worth 25 points of the overall project grade.