MCS 275 Spring 2024 Worksheet 5¶

• Course instructor: Emily Dumas

Topics¶

The main topic of this worksheet is recursion with backtracking, building on the maze-solving example from lecture.

Resources¶

These things might be helpful while working on the problems. Remember that for worksheets, we don't strictly limit what resources you can consult, so these are only suggestions.

• Lecture 9 - Recursion vs iteration
• Lecture 10 - Recursion vs iteration II
• Lecture 11 - Recursion with backtracking
• maze.py
  • which uses plane.py , the old Point2/Vector2 module
• solvemaze.py
• Downey's book, Think Python
• MCS 260 course materials from Fall 2021:
  • Slides, homework, worksheets, and projects
  • MCS 260 Sample programs

Reminder about images¶

The maze module supports saving a maze as an image file, of type SVG or PNG. However, PNG images require the module Pillow to be installed. The following command should install it:

python3 -m pip install pillow

1. Get solvemaze.py working¶

Get plane.py, maze.py, and solvemaze.py from the course sample code repository

Test out solvemaze.py and make sure you can run it in the terminal and find/open the image files it creates.

Note that when run as a script, solvemaze.py now takes command line arguments (which are optional). If given:

• The first command line argument is the maze size (defaulting to 51x51)
• The second command line argument is the template for the output image file

For example,

python3 solvemaze.py 13 mazeimage

will create two files: mazeimage.svg (which you can open in a browser) and mazeimage.png (which you can open in VS code, a browser, or various other programs for viewing images). Each image will show a 13x13 maze and its solution.

2. Solution history¶

Add a new function depth_first_maze_solution_history() to solvemaze.py that works similarly to depth_first_maze_solution() but which returns a list of every path considered (rather than just a single path that is a solution). This means the returned value will be a list of lists of Point2 objects.

Thus the last item in the returned list will be a solution, if a solution exists.

Then, write a script that uses depth_first_maze_solution_history to do the following:

• Take a command line argument, an odd integer n
• Generate a random n by n maze
• Solve the maze, keeping track of the history of paths considered
• Save a sequence of output image files with names like dfs001.png, dfs002.png, etc., that highlight all paths considered by the solver

Run this on a maze of moderate size (e.g. 9x9) and flip through the resulting images in your platform's image viewer to make a crude animation of the recursive process.

Project questions?¶

Remember project 1 is due on Fri Feb 9 at 11:59pm central. If you have questions, this is the perfect time to discuss them with your TA. The worksheet was made a little shorter than usual to allow time for this.

Bonus round¶

Work on these if you have extra time and have no need to ask questions about the project.

A. Simple custom mazes¶

Instead of using the PrimRandomMaze class to generate a maze, write your own subclass of Maze that creates a maze in which start and goal are set, the border is fully blocked, and so that it is possible to get from start to goal. The constructor should create some obstacles between the start and goal, to make the maze more interesting.

For example, you might make a class that simply places a large rectangle of blocked squares in the middle of the maze, so that a solution must either go along the top and right, or bottom and left. Or you might make some walls coming out of the sides, so that a solution needs to turn back and forth several times. Or you could make the start at the center, and surround it by walls that force any solution to take a spiral path out to a goal on the edge.

The key characteristics you are looking for are:

• Ability to generate a maze of a given size (specified as arguments to the constructor)
• Certainty that the maze always has a solution

It's OK for the constructor to decide a size is too small or is otherwise unacceptable, and raise an exception. But to keep things interesting, it should allow arbitrarily large mazes.

Write a script that instantiates your class and then uses solvemaze to find a solution. Save the solved maze to a SVG file.

Revision history¶

• 2024-02-05 Initial publication