CODEWITHSUNDEEP
pythonalgorithmdepth-first-searchbreadth-first-searchmaze
EddieEC
EddieEC

Reputation: 377

Maze: Finding the shortest path from start point to end point

I am currently learning some CS foundations (started a week ago) and I stumbled across this challenge. The maze is a list of lists, with '#' indicating a wall and ' ' indicating an open path. I am supposed to find the shortest possible path from the bottom left corner to the top right corner in terms of consecutive coordinates (col, row). I have to make a function without importing anything.

For example:

maze = 
       [[' ', '#', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', ' ', ' ', ' ', ' '], 
        ['#', ' ', '#', ' ', ' '], 
        [' ', ' ', '#', '#', '#']]

First I get the start point coordinates (0, 9) and the end point coordinates (4, 0). Then I need to find the shortest path. The expected result would be: [(0, 9), (1, 9), (1, 8), (1, 7), (2, 7), (3, 7), (4, 7), (4, 6), (4, 5), (4, 4), (4, 3), (4, 2), (4, 1), (4, 0)].

This is my code:

def grid(maze):
    ''' Maze Properties'''
    num_rows = len(maze)
    num_cols = len(maze[0])
    end_pt = (num_cols - 1, 0)
    start_pt = (0, num_rows - 1)
    print(start_pt, end_pt)

    '''Recursive Function'''

    def find_shortest(maze, start_point, end_point, visited, shortest_path):
        '''BASE CASE'''
        if start_point == end_point:
            return shortest_path


        adj_points = []
        '''FIND ADJACENT POINTS'''
        current_row = start_point[1]
        current_col = start_point[0]

        #UP
        if current_row > 0:
            if maze[current_row - 1][current_col] == " ":
                adj_points.append((current_col, current_row - 1))

        #RIGHT
        if current_col < (len(maze[0])-1):
            if maze[current_row][current_col] == " ":
                adj_points.append((current_col + 1, current_row))
        #DOWN
        if current_row < (len(maze) - 1):
            if maze[current_row + 1][current_col] == " ":
                adj_points.append((current_col, current_row + 1))
        #LEFT
        if current_col > 0:
            if maze[current_row][current_col - 1] == " ":
                adj_points.append((current_col - 1, current_row))

        print(adj_points)
        if all(elem in visited for elem in adj_points):
            return

        '''LOOP THROUGH ADJACENT PTS'''
        for point in adj_points:
            if point not in visited:
                visited.append(point)
                shortest_path.append(point)
                return find_shortest(maze, point, end_point, visited, shortest_path)



    path = [start_pt]
    visited = [start_pt]
    shortest_path = find_shortest(maze, start_pt, end_pt, visited, path)
    return shortest_path

I believe the problem is if I hit a dead end, it should backtrack to the last point where there is a choice, which I am not figuring out how to do.

NOTE: I believe this is DFS, but BFS solutions would also be appreciated.

Upvotes: 1

Views: 4864

Answers (2)

Ajay Dabas
Ajay Dabas

Reputation: 1444

Modifying the post given here: https://www.techiedelight.com/find-shortest-path-in-maze/

Update: Code converted from C++ to Python. Logic is still the same.

M = 10 # Rows
N = 5 # Columns
def isSafe(grid,visited,x,y):
    if grid[x][y]=='#' or visited[x][y]==True:
        return False # Unsafe
    return True # Safe

def isValid(x,y):
    if x<M and y<N and x>=0 and y>=0:
        return True # Valid
    return False # Invalid

def solve(grid,visited,i,j,dest_x,dest_y,curr_dist,min_dist,shortestPath,currentPath):
    if i==dest_x and j==dest_y: # if destination is found, update min_dist
        if curr_dist<min_dist[0]: # If a shorter distance is found
            min_dist[0] = curr_dist # Update distance
            shortestPath.clear() # Update path
            shortestPath.extend(currentPath)
            shortestPath.append((dest_y,dest_x)) # Push the destination coordinates
        return

    # set (i, j) cell as visited
    visited[i][j] = True
    currentPath.append((j,i))

    # go to bottom cell
    if isValid(i + 1, j) and isSafe(grid,visited,i + 1, j):
        solve(grid,visited,i + 1, j, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
    # go to right cell
    if isValid(i, j + 1) and isSafe(grid,visited,i, j + 1):
        solve(grid,visited,i, j + 1, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)

    # go to top cell
    if isValid(i - 1, j) and isSafe(grid,visited,i - 1, j):
        solve(grid,visited,i - 1, j, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)

    # go to left cell
    if isValid(i, j - 1) and isSafe(grid,visited,i, j - 1):
        solve(grid,visited,i, j - 1, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
    visited[i][j] = False
    currentPath.pop()

if __name__ == "__main__": 
    min_dist = [9e10] # Start from infinity
    shortestPath = [] # It will contain the path (y,x) tuples
    currentPath = [] # It will store the current path temporarily
    grid = [
        [' ', '#', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', ' ', ' ', ' ', ' '], 
        ['#', ' ', '#', ' ', ' '], 
        [' ', ' ', '#', '#', '#']
    ]
    visited = []
    for i in range(M):
        _list = list()
        for j in range(N):
            _list.append(False)
        visited.append(_list)
    solve(grid,visited,M-1,0,0,N-1,0,min_dist,shortestPath,currentPath)
    print("Minimum distance: ",min_dist[0])
    print("Path: [",end=" ")
    for path in shortestPath:
        print('('+str(path[0])+','+str(path[1])+')',end=' ')
    print("]")

Output

Minimum distance:  13
Path: [ (0,9) (1,9) (1,8) (1,7) (2,7) (3,7) (4,7) (4,6) (4,5) (4,4) (4,3) (4,2) (4,1) (4,0) ]

Upvotes: 1

trincot
trincot

Reputation: 351308

Your DFS approach returns the shortest path for that particular maze, as it happens to choose the right directions first, but it wouldn't find the shortest path for some other mazes. For instance, with this maze:

maze = [[' ', ' ', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '],
        [' ', ' ', ' ', ' ', ' ']]

Note that your code has an error for the #RIGHT case, where a + 1 is missing, so actually your code would not find a path for the above maze. Even when that mistake is corrected, it will find the longer path, going first to the top-left corner of the grid.

For finding the shortest path it is better to go for BFS because then you are sure that your first hit of the target corresponds to the shortest path.

Below is your code adapted to BFS without making more changes than necessary. Note that visited is not a list here, but a dictionary that not only tells you that a square was visited, but also from which other square you came to visit it.

With that piece of information you can construct the path.

Also, I chose here to start searching from the end to the start, as that way you can reconstruct the path in its correct order (unwinding back). Otherwise you would have to reverse the path before returning it.

def grid(maze):
    ''' Maze Properties'''
    num_rows = len(maze)
    num_cols = len(maze[0])
    end_pt = (num_cols - 1, 0)
    start_pt = (0, num_rows - 1)

    '''BFS'''
    visited = {end_pt: None}
    queue = [end_pt]
    while queue:
        current = queue.pop(0)
        if current == start_pt:
            shortest_path = []
            while current:
                shortest_path.append(current)
                current = visited[current]
            return shortest_path
        adj_points = []
        '''FIND ADJACENT POINTS'''
        current_col, current_row = current
        #UP
        if current_row > 0:
            if maze[current_row - 1][current_col] == " ":
                adj_points.append((current_col, current_row - 1))
        #RIGHT
        if current_col < (len(maze[0])-1):
            if maze[current_row][current_col + 1] == " ": ## There was an error here!
                adj_points.append((current_col + 1, current_row))
        #DOWN
        if current_row < (len(maze) - 1):
            if maze[current_row + 1][current_col] == " ":
                adj_points.append((current_col, current_row + 1))
        #LEFT
        if current_col > 0:
            if maze[current_row][current_col - 1] == " ":
                adj_points.append((current_col - 1, current_row))

        '''LOOP THROUGH ADJACENT PTS'''
        for point in adj_points:
            if point not in visited:
                visited[point] = current
                queue.append(point)

maze = [[' ', '#', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', ' ', ' ', ' ', ' '], 
        ['#', ' ', '#', ' ', ' '], 
        [' ', ' ', '#', '#', '#']]

print(grid(maze))

Upvotes: 2

Related Questions