MCS 275 Spring 2023 Homework 6
36 lines
def depth_first_maze_solution(M,path=None,verbose=False):
def can_be_solved_maxlen(M, k, path=None,verbose=False):
"""
"""
Find solution to Maze `M` that begins with `path` (if given),
Returns True if a solution to `M` can be found which is of length
returning either that solution as a list of Point2 objects or
at most `k` (starting from `path`, if given). Else, returns False.
None if no such solution exists.
"""
"""
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 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])
possible_next_locations = M.free_neighbors(path[-1])
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)
# Reduce `k` by 1 because we've now made another move.
if solution: # None is falsy, while a nonempty list is truthy
solution = can_be_solved_maxlen(M, k-1, new_path,verbose)
return solution
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
# What now? If we end up here, it means no next step leads to a solution
# Hence `path` leads to only dead ends
# Hence `path` leads to only dead ends
# We therefore BACKTRACK
# We therefore BACKTRACK
if verbose:
if verbose:
print("GIVING UP ON:",path)
print("GIVING UP ON:",path)
return None
return False