MCS 275 Spring 2023 Homework 6 (method 2)
36 lines
def depth_first_maze_solution(M,path=None,verbose=False):
def depth_first_all_maze_solutions(M,path=None,verbose=False):
"""
"""
Find solution to Maze `M` that begins with `path` (if given),
Find all solutions to Maze `M` that begin with `path` (if given),
returning either that solution as a list of Point2 objects or
returning a list where every entry is itself a sublist representing a
None if no such solution exists.
single solution to the maze.
"""
"""
if path == None:
if path == None:
# no path was specified, initialize it with [M.start]
# no path was specified, initialize it with [M.start]
path = [ M.start ]
path = [ M.start ]
if verbose:
if verbose:
print("Considering:",path)
print("Considering:",path)
if path[-1] == M.goal:
if path[-1] == M.goal:
# path ends with goal, meaning it's a solution
# path ends with goal, meaning it's a solution
return path
return [path] # Put the path into a list
possible_next_locations = M.free_neighbors(path[-1])
possible_next_locations = M.free_neighbors(path[-1])
solutions = []
for x in possible_next_locations:
for x in possible_next_locations:
if x in path:
if x in path:
# skip x
# skip x
continue # do not execute the rest of the loop body
continue # do not execute the rest of the loop body
# immediately begin the next iteration.
# immediately begin the next iteration.
# x should be considered
# x should be considered
new_path = path + [x]
new_path = path + [x]
# Ask for a solution that continues from new_path
# Ask for a solution that continues from new_path
solution = depth_first_maze_solution(M,new_path,verbose)
solution = depth_first_all_maze_solutions(M,new_path,verbose)
if solution: # None is falsy, while a nonempty list is truthy
if len(solution) > 0:
return solution
solutions.extend(solution) # Keep all solutions found from recursive call
# What now? If we end up here, it means no next step leads to a solution
# Always return our list of solutions (which may be empty)
# Hence `path` leads to only dead ends
return solutions
# We therefore BACKTRACK
if verbose:
print("GIVING UP ON:",path)
return None