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.
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:
nn by n mazedfs001.png, dfs002.png, etc., that highlight all 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 script below contains the requested function and the demonstration code as well.
import maze
# Adapted from the 2023 worksheet
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.
if __name__ == "__main__":
# Run as a script, so make the images of a maze's solution
# as requested in the problem.
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
# Make a random maze
M = maze.PrimRandomMaze(n,n)
# Find solution and history
path_list, _ = depth_first_maze_solution_history(M) # `_` represents a boolean variable we don't need anymore
# Save image files (could also do SVG to avoid Pillow dependency)
for i,p in enumerate(path_list):
M.save_png("dfs{:03d}.png".format(i),scale=30,highlight=p)
print("Saved {} image files ('dfs000.png' to 'dfs{:03d}.png')".format(
len(path_list),
len(path_list)-1,
))