.py files containing your work.This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 21, 2023.
Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.
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.
Most relevant:
Less likely to be relevant, but also allowed:
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.
Ask your instructor or TA a question by email, in office hours, or on discord.
Like much of worksheet 6, this problem builds on the work we did in solvemaze.py.
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.
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).
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.
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
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
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/
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.
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))
Finally, we need to make our function to check if any of the solutions are short enough:
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