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

MCS 275 Spring 2023 Homework 6 Solutions

  • Course Instructor: David Dumas
  • Contributors to this document: Johnny Joyce

Instructions:

  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work.

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 21, 2023.

Collaboration

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Content

This assignment is about recursion with backtracking. It's a little shorter than usual as I know you're working on Project 2, and this assignment and that project cover some similar ground.

Resources you may consult

Most relevant:

Less likely to be relevant, but also allowed:

Point distribution

This homework assignment has 3 problems, numbered 2, 3, and 4. The grading breakdown is:

Points Item
3 Autograder
6 Problem 2
9 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 2: Does the maze have a short solution?

Like much of worksheet 6, this problem builds on the work we did in solvemaze.py.

What the length of a solution means

Recall our convention is that the solution to a maze is a list of Point2 objects. The length of a solution to the maze is defined as the number of objects in that list. So if the start is at Point2(1,1) and the goal is at the adjacent location Point2(1,2), then the list [Point2(1,1), Point2(1,2)] would be a solution of length 2.

Your task

Write a function can_be_solved_maxlen(M,k) that takes a Maze object M, an integer k and returns a boolean value:

  • True if maze M has a solution of length k or less.
  • False is returned otherwise (i.e. if M has no solution at all, or if all solutions to M have length greater than k).

It would be reasonable to use depth_first_maze_solution from solvemaze.py as a starting point for your work, modifying it to do what is needed in this problem.

Put this function in a file called mcs275hwk6.py and upload it. You don't need to upload any other files (e.g. no need to include plane.py or maze.py).

Something to be careful about

A maze might have multiple solutions. Suppose you find a solution of length 30. There might be another solution of length 22, and so you can't necessarily determine the return value for can_be_solved_maxlen(M,25) on the basis of the length of the first solution that's found.

Solution

Method 1: Depth-limited search (best)

The code below is an example of a modified version of the depth-first search algorithm, which is called depth-limited search. The key difference here is that if we ever attempt to consider a route that is longer than k, we abandon the route.

One advantage of this method is that we're only ever considering solutions that are short enough, so we don't need a helper function (unlike in method 2). Another advantage is that this function is much faster than method 2 because there are fewer paths for our recursive function to consider, but method 2 must consider every possible path of the maze.

To see the difference between the original depth_first_maze_solution and our modified version can_be_solved_maxlen, see the following diffchecker link: https://www.diffchecker.com/5ThwZVtG

In [ ]:
def can_be_solved_maxlen(M, k, path=None,verbose=False):
    """
    Returns True if a solution to `M` can be found which is of length
    at most `k` (starting from `path`, if given). Else, returns False.
    """

    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 True
    
    # If there are no more steps to take and we haven't reached the goal,
    # then don't make another recursive call
    if k == 0:
        return False

    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 
        # Reduce `k` by 1 because we've now made another move.
        solution = can_be_solved_maxlen(M, k-1, new_path,verbose)
        if solution: # If we've found `True` at any point in our search, return True.
            return 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)
    return False

Method 2: Find all possible solutions (also works, but is slower)

We can modify depth_first_maze_solution to return every possible solution to the maze. We would use this as a helper function for can_be_solved_maxlen, which would check if any of the solutions are of length k or less.

To see the difference between the original depth_first_maze_solution and our modified version depth_first_all_maze_solutions, see the following diffchecker link: https://www.diffchecker.com/zLS2aXh6/

In [ ]:
def depth_first_all_maze_solutions(M,path=None,verbose=False):
    """
    Find all solutions to Maze `M` that begin with `path` (if given),
    returning a list where every entry is itself a sublist representing a
    single solution to the maze.
    """
    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] # Put the path into a list

    possible_next_locations = M.free_neighbors(path[-1])
    solutions = []
    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_all_maze_solutions(M,new_path,verbose)
        if len(solution) > 0:
            solutions.extend(solution) # Keep all solutions found from recursive call

    # Always return our list of solutions (which may be empty)
    return solutions

We can use the following code snippet to verify that we find all possible solutions. By creating a $2\times2$ maze with the start in the upper left corner and the goal in the bottom right, there should only be two possible solutions.

In [1]:
M = maze.Maze(2, 2, start=Point2(0,0), goal=Point2(1,1))

# We expect to see two possible solutions for this maze
solutions = depth_first_all_maze_solutions(M)
for i, solution in enumerate(solutions):
    print("Solution {}: {}".format(i+1, solution))
Solution 1: [Point2(0,0), Point2(1,0), Point2(1,1)]
Solution 2: [Point2(0,0), Point2(0,1), Point2(1,1)]

Finally, we need to make our function to check if any of the solutions are short enough:

In [ ]:
def can_be_solved_maxlen(M, k):
    """Check each solution of the maze. If any are less than length k, return True. Else, return False"""
    
    for solution in depth_first_all_maze_solutions(M):
        if len(solution) <= k:
            return True
        
    # We only reach this line when no suitable solutions are found, so return False
    return False

Revision history

  • 2023-02-16 Initial publication