The main topic of this worksheet is recursion with backtracking, building on the maze-solving example from lecture.
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.
maze.py¶This problem involves reading and learning more about the module maze we discussed in Lecture 15. You'll use the things you learn about here in subsequent problems.
In Lecture 11 we discussed a minimal way of using the module:
Maze object (e.g. with M = maze.Maze(xsize=7,ysize=7)M.set_blocked for individual squares, and/or M.apply_border which makes all of the edge squares blocked)M.start and M.goal) locationsThe module maze has several other features:
Maze objects have a method save_svg(filename) that writes a graphical representation of the maze to a file in the SVG format. This is a vector graphics format (scalable, not pixel-based) that can be viewed in most web browsers.
This method also accepts an optional argument highlight, which if given should be a list of (x,y) pairs that indicate squares in the maze that should be higlighted in light blue. For example,
mymaze.save_svg("cool.svg",highlight=[ Point2(2,1), Point2(3,1), Point2(4,1) ])will save the maze to cool.svg, and highlight three squares in blue. (This assumes you've already run from plane import Point2 to get the Point2 class.)
The highlight argument is provided as a way to indicate the solution of a maze, or any other feature you might choose to display.
For this feature, you need to install a module that isn't in Python's standard library. The module PIL is from a package called Pillow, and is used to work with image files. The following command should install it:
python3 -m pip install pillowAfter installing Pillow, you can save a maze object as a PNG file (a bitmap graphics format supported by nearly every program that deals with images) using the save_png method. Its arguments are:
save_png(filename,scale=1,highlight=[])The argument scale is a positive integer controlling the width of each maze square in pixels. The default, scale=1, will result in a tiny image file where each pixel is a maze square. To get a reasonable size output image, try scale=10 or scale=30.
The class PrimRandomMaze inherits from Maze and automatically generates a random maze that has exactly one path from the start to the goal. Its constructor takes only two arguments
PrimRandomMaze(xsize,ysize)and both xsize and ysize must be odd numbers. This random maze generator uses Prim's algorithm, which is known for producing mazes of moderate difficulty, with many short dead ends.
Upgrade the script part of solvemaze so it does the following:
127x127n and us it as both xsize and ysizexsize and the second as ysizemaze127x127.svg)Test the program, loading the SVG file it produces in a web browser.
Also try the same but with a PNG file as the output image type. You may need to adjust the scale keyword argument of save_png to make an image large enough to easily see.
If everything works, your images should look a bit like this.
import maze
import solvemaze
import sys
if len(sys.argv) == 2:
n = int(sys.argv[1])
xsize = n
ysize = n
if xsize % 2 != 1:
print("Integers xsize, ysize must be odd.")
exit()
elif len(sys.argv) >= 3:
xsize = int(sys.argv[1])
ysize = int(sys.argv[2])
if xsize % 2 != 1 or ysize % 2 != 1:
print("Integers xsize, ysize must be odd.")
exit()
else:
print("No command line argument(s) detected. Defaulting to 127.")
xsize = 127
ysize = 127
M = maze.PrimRandomMaze(xsize,ysize)
path = solvemaze.solvemaze(M)
M.save_svg("prob2.svg",highlight=path)
M.save_png("prob2.png",scale=30,highlight=path)
# Code below displays an image in a notebook cell.
# Uncomment if you want to see the image in the notebook itself
#from IPython.display import Image
#Image(filename='prob2.png')
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). 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:
nn by n mazedfs001.png, dfs002.png, etc., that highlight the paths considered by the solverRun 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.
The code below is a modified version of solvemaze() and has relatively few changes. To directly view the changes between the original and modified versions, see the following link: https://www.diffchecker.com/LbrKWcSL
def depth_first_maze_solution_history(M,path_list=None,verbose=False):
"""
Functions similarly to `solvemaze`, but returns a list of all paths
considered throughout solving process.
"""
if path_list == None:
# no path was specified, initialize it with [M.start]
path_list = [[M.start]] # Use a list of lists for path_list - one list for each path.
else:
print("Called with path={}".format(path_list[-1]))
path = path_list[-1]
if verbose:
print("Considering:",path)
if path[-1] == M.goal:
# path ends with goal, meaning it's a solution
return path_list, True # Set the "solved" variable to True
path = path_list[-1]
possible_next_locations = M.free_neighbors(path[-1])
for x in possible_next_locations:
if x in path:
# skip x
continue # do not execute the rest of the loop body
# immediately begin the next iteration.
# x should be considered
new_path = path + [x]
# Ask for a solution that continues from new_path
path_list.append(new_path)
soln, solved = depth_first_maze_solution_history(M,path_list)
if solved:
return soln, True
# What now? If we end up here, it means no next step leads to a solution
# Hence `path` leads to only dead ends
# We therefore BACKTRACK
if verbose:
print("GIVING UP ON:",path)
# Still need to return path_list so we can visualize it later
return path_list, False # Keep the "solved" variable as False.
import maze
import solvemaze
import sys
if len(sys.argv) > 1:
n = int(sys.argv[1])
if n % 2 != 1:
print("Integer n must be odd.")
exit()
else:
print("No command line argument detected. Defaulting to 11.")
n = 11
M = maze.PrimRandomMaze(n,n)
path_list, _ = solvemaze.solvemaze_history(M) # `_` represents a boolean variable we don't need anymore
for i,p in enumerate(path_list):
M.save_png("dfs{:03d}.png".format(i),scale=30,highlight=p)
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:
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.
class BlockMaze(Maze): # Create a new class that subclasses maze.maze
"""Maze that blocks out the center and border, so the solution is going around the perimeter."""
def __init__(self, n=5):
"""Creates an nxn maze with the border and center blocked out, and start/goal in opposite corners."""
if n<5:
raise ValueError("The maze must have size 5 at a minimum")
super().__init__(n,n,start=(1,1),goal=(n-2,n-2))
# block out the border using apply_border. No need to call super, since we don't override the base class function
self.apply_border()
# block out the center square using set_blocked
for x in range(2,n-2):
for y in range(2,n-2):
self.set_blocked(x,y)
class CustomMaze(Maze): # Create a new class that subclasses maze.maze
"""Maze with obstacles specifically defined by user."""
def __init__(self, n=5, obstacles = []):
"""
Takes arg `obstacles` as list of 2-tuples of the form (x,y) for integers `x` and `y`
Each entry (x,y) of `obstacles` specifies an obstacle at coordinates (x,y)
"""
if n<5:
raise ValueError("The maze must have size 5 at a minimum")
super().__init__(n,n,start=(1,1),goal=(n-2,n-2))
self.obstacles = obstacles
# block out the border using apply_border. No need to call super, since we don't override the base class function
self.apply_border()
# Block out any obstacles
for x in range(2,n-2):
for y in range(2,n-2):
if (x,y) in self.obstacles:
self.set_blocked(x,y)
The version of depth_first_maze_solution we developed always considers its next possible steps in the order returned by Maze.free_neighbors, which in turn is dictated by the class attribute neighbor_disps of class Maze. This always tries movement vectors in the following order: [Vector2(-1, 0), Vector2(0, -1), Vector2(1, 0), Vector2(0, 1)]
This means that for mazes with multiple solutions, depth_first_maze_solution will always find the same solution and will do so by exhibiting a preference for moving in direction Vector(-1,0) whenever it is possible to do so, reverting to Vector2(0,-1) only when a dead end is reached, and so on.
Modify depth_first_maze_solution so that it has an additional keyword argument called strategy which defaults to the string "fixed". Depending on the value of strategy it will consider possible next steps in a different order:
strategy is "fixed", it uses the order provided by Maze.free_neighbors. That's what depth_first_maze_solution developed in lecture does.strategy is "random", it considers the possible next steps provided by Maze.free_neighbors in a random order (see e.g. random.shuffle in Python's random module). Thus, the solution found may vary from one call to the next, if the maze has multiple solutions.strategy is "closest", then among all possible next steps, it tries them in order of increasing Euclidean distance to the goal. That is, the first step it tries is the one that has the smallest distance to the goal among available steps. Then it moves to the second-smallest distance, etc.Try these strategies on a maze that is wide open, having only walls on the edges, to compare their behavior.
"Depth first recursive maze solution with additional options for exploring adjacent neighbors randomly, by closest distance"
from plane import Point2, Vector2
import maze
import random
def depth_first_maze_solution(M,path=None,verbose=False, strategy = "fixed"):
"""
Find solution to Maze `M` that begins with `path` (if given),
returning either that solution as a list of Point2 objects or
None if no such solution exists.
"""
if path == None:
# no path was specified, initialize it with [M.start]
path = [ M.start ]
if verbose:
print("Considering:",path)
if path[-1] == M.goal:
# path ends with goal, meaning it's a solution
return path
# possible_next_locations is modified based on strategy
if strategy == "fixed":
possible_next_locations = M.free_neighbors(path[-1])
elif strategy == "random":
possible_next_locations = random.shuffle(M.free_neighbors(path[-1]))
elif strategy == "closest":
possible_next_locations = []
next_locations = M.free_neighbors(path[-1])
closest_distance = []
# sort distances to the goal, and append as a tuple to the above list
for x in next_locations:
dist = x.distance_to(M.goal)
closest_distance.append((x,dist))
closest_distance.sort(key = lambda x: x[1])
#extract the points in the sorted list and append to possible_nest_locations
for x in closest_distance:
possible_next_locations.append(x[0])
#default to fixed locations
else:
possible_next_locations = M.free_neighbors(path[-1])
for x in possible_next_locations:
if x in path:
# skip x
continue # do not execute the rest of the loop body
# immediately begin the next iteration.
# x should be considered
new_path = path + [x]
# Ask for a solution that continues from new_path
solution = depth_first_maze_solution(M,new_path,verbose)
if solution: # None is falsy, while a nonempty list is truthy
return solution
# What now? If we end up here, it means no next step leads to a solution
# Hence `path` leads to only dead ends
# We therefore BACKTRACK
if verbose:
print("GIVING UP ON:",path)
return None
if __name__=="__main__":
# this code runs when solvemaze.py is run as a script
# demo code goes here
M = maze.PrimRandomMaze(127,127)
soln = depth_first_maze_solution(M)
M.save_svg("maze.svg")
M.save_svg("maze_solved.svg",highlight=soln)
print("Saved to maze.svg and maze_solved.svg")