MCS 275 2022 worksheet 7 question 3
15 removals
34 lines
20 additions
39 lines
def solvemaze(M,path=None):
def solvemaze_history(M,path_list=None, solved=False):
"""
"""
Find a solution to maze `M`
Functions similarly to `solvemaze`, but returns a list of all paths
using a depth-first recursive
considered throughout solving process. Uses additional arg `solved`
search.
to track whether solution has been found.
"""
"""
print("Called with path={}".format(path))
if path_list==None:
if path==None:
# no path specified, so start
# no path specified, so start
# at M.start
# at M.start
path = [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 path[-1]==M.goal:
if path[-1]==M.goal:
# We've found a solution
# We've found a solution
print("SOLVED!")
print("SOLVED!")
return path
return path_list, True # Set the "solved" variable to True
# next steps to consider
# next steps to consider
# (may include retracing our steps)
# (may include retracing our steps)
steps = M.free_neighbors(*path[-1])
steps = M.free_neighbors(*path[-1])
for s in steps:
for s in steps:
if len(path)>=2 and s == path[-2]:
if len(path)>=2 and s == path[-2]:
print("Not considering {}, as it would retrace our steps".format(s))
print("Not considering {}, as it would retrace our steps".format(s))
continue
continue
# Consider whether next step `s` leads to a solution
# Consider whether next step `s` leads to a solution
print("Considering next step {}".format(s))
print("Considering next step {}".format(s))
soln = solvemaze(M,path + [s])
next_path = path + [s]
if soln != None:
path_list.append(next_path)
soln, solved = solvemaze_history(M,path_list)
if solved:
# Some recursive call yielded a solution!
# Some recursive call yielded a solution!
print("Hooray, considering {} worked!".format(s))
print("Hooray, considering {} worked!".format(s))
return soln
return soln, True # # Set the "solved" variable to True
# if we reach this line, step `s` only led to dead ends
# if we reach this line, step `s` only led to dead ends
# if we reach this line, then no continuation of `path`
# if we reach this line, then no continuation of `path`
# leads to a solution, only dead ends.
# leads to a solution, only dead ends.
# Still need to return path_list so we can visualize it later
print("Path {} leads only to dead ends".format(path))
print("Path {} leads only to dead ends".format(path))
return None
return path_list, False # Keep the "solved" variable as False.