A document from MCS 275 Spring 2023, instructor David Dumas. You can also get the notebook file.

MCS 275 Spring 2023 Worksheet 6 Solutions

  • Course instructor: David Dumas
  • Solutions prepared by: Jennifer Vaccaro, Johnny Joyce, Kylash Viswanathan

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.

1. Learn a little more about 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:

  • Create a Maze object (e.g. with M = maze.Maze(xsize=7,ysize=7)
  • Set some squares to blocked (using M.set_blocked for individual squares, and/or M.apply_border which makes all of the edge squares blocked)
  • Set the start and goal (M.start and M.goal) locations
  • Use a recursive backtracking function to find a path from the start to the goal

The function created in the last step can be found in solvemaze.py.

The module maze has several other features:

Saving a maze as SVG file

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.

Saving a maze as a PNG file

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 pillow

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

Random Mazes

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.

2. Arbitrary size solved maze image script

Upgrade the script part of solvemaze so it does the following:

  • If run with no command line arguments, it assumes the maze should have size 127x127
  • If one command line argument if given, convert that to an integer n and us it as both xsize and ysize
  • If two command line arguments are given, convert them to integers and use the first as xsize and the second as ysize
  • Generate a Prim-algorithm random maze of the given size
  • Solve the maze by recursive backtracking
  • Write the solved maze (with solution highlighted) to a SVG file whose name involves the size (e.g. maze127x127.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.

Solution

In [ ]:
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') 

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

Solution

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

In [ ]:
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.

Calling the script:

In [ ]:
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) 

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

Solution:

In maze.py:

In [ ]:
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)

5. Guided choice of next step

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:

  • If strategy is "fixed", it uses the order provided by Maze.free_neighbors. That's what depth_first_maze_solution developed in lecture does.
  • If 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.
  • If 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.

Solution:

In [ ]:
"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")