Need help with finding shortest distance in a binary maze, which is a list of lists matrix, where 0 is an empty cell and 1 is a wall. The maze has x,y starting coordinates that default to 0,0 and it's end point is always bottom right corner. Shortest distance always includes the starting point (i.e., if there are four steps needed from the starting point, shortest distance will be 5)
I need to be using backtracking algorithm. So far I could come up with a function that determines if there is an escaping path at all. It works well:
def is_solution(maze, x=0, y=0):
n = len(maze)
m = len(maze[0])
if x == n - 1 and y == m - 1:
return True
maze[x][y] = 1
result = False
for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
if 0 <= a < n and 0 <= b < m and maze[a][b] == 0:
result = result or is_solution(maze, a, b)
maze[x][y] = 0
return result
maze = [
[0, 0, 1, 1],
[1, 0, 0, 0],
[1, 1, 1, 0]
]
is_solution(maze)
The above will result to True.
Now I am really struggling with finding the shortest distance. I think it should be relatively easy to update the code above so it showed distance if there is a path and inf if there isn't one. But I got stuck. In the example above shortest distance would be 6 (including the starting point) I also need to add code to be able to get a list of all shortest distances and coordinates of each step in a list of lists format like [[(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3)]] . In this case there is only one path, but if there were two of distance six, that list would include also the list of second shortest path as well.
Thank you.
Simple change to your code to track shortest path
Shortest Path
def min_solution(maze, x = 0, y = 0, path = None):
def try_next(x, y):
' Next position we can try '
return [(a, b) for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)] if 0 <= a < n and 0 <= b < m]
n = len(maze)
m = len(maze[0])
if path is None:
path = [(x, y)] # Init path to current position
# Reached destionation
if x == n - 1 and y == m - 1:
return path
maze[x][y] = 1 # Mark current position so we won't use this cell in recursion
# Recursively find shortest path
shortest_path = None
for a, b in try_next(x, y):
if not maze[a][b]:
last_path = min_solution(maze, a, b, path + [(a, b)]) # Solution going to a, b next
if not shortest_path:
shortest_path = last_path # Use since haven't found a path yet
elif last_path and len(last_path) < len(shortest_path):
shortest_path = last_path # Use since path is shorter
maze[x][y] = 0 # Unmark so we can use this cell
return shortest_path
maze = [
[0, 0, 1, 1],
[1, 0, 0, 0],
[1, 1, 1, 0]
]
t = min_solution(maze)
if t:
print(f'Shortest path {t} has length {len(t)}')
else:
print('Path not found')
Output:
Shortest path [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3)] has length 6
All Paths
def all_paths(maze, x = 0, y = 0, path = None):
'''
All paths through Maze as a generator
'''
def try_next(x, y):
' Next position we can try '
return [(a, b) for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)] if 0 <= a < n and 0 <= b < m]
n = len(maze)
m = len(maze[0])
if path is None:
path = [(x, y)]
# Reached destionation
if x == n - 1 and y == m - 1:
yield path
else:
maze[x][y] = 1 # Mark current position so we won't use this cell in recursion
# Recursively find pat
for a, b in try_next(x, y):
if not maze[a][b]:
yield from all_paths(maze, a, b, path + [(a, b)]) # Solution going to a, b next
maze[x][y] = 0 # Unmark so we can use this cell
maze = [[0, 0, 0],
[1, 0, 0],
[1, 1, 0]]
for t in all_paths(maze):
print(f'path {t} has length {len(t)}')
Output
path [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)] has length 5
path [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)] has length 5