Question

Python: Implement a grid-maze solving program that uses depth-first search to solve grids. The agent’s actions are moving in one of four directions: up, down, left, and right.

A grid is formatted like below where 1’s represent locations the agent cannot traverse:

1 1 1 1 1 1 1 1

1 0 0 0 1 1 1 1

1 0 0 0 0 0 0 1

1 1 1 0 0 1 0 1

1 0 1 0 0 1 0 1

1 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1

The final path can be displayed with ‘S’ for the initial state, ‘G’ for the goal state, and ‘*’ symbols for the path:

1 1 1 1 1 1 1 1

1 S 0 0 1 1 1 1

1 * * * 0 0 0 1

1 1 1 * 0 1 0 1

1 0 1 * G 1 0 1

1 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1

Answer 1

For given output, just copy paste it

# Check if it is possible to go to (x, y) from current position. The
# function returns false if the cell has value 0 or already visited

M = 7
N=8

def isSafe(mat, visited, x, y):
    return not (mat[x][y] == 1 or visited[x][y])


# if not a valid position, return false
def isValid(x, y):
    return M > x >= 0 and N > y >= 0


# Find Shortest Possible Route in a Matrix mat from source cell (0, 0)
# to destination cell (x, y)

# 'min_dist' stores length of longest path from source to destination
# found so far and 'dist' maintains length of path from source cell to
# the current cell (i, j)

v = [[0 for x in range(N)] for y in range(M)]


def findShortestPath(mat, visited, i, j, x, y, min_dist=float('inf'), dist=0):

    # if destination is found, update min_dist
    
    if i==x and j==y:
        # print (min_dist);
      if dist<min_dist:
         min_dist=dist;
         for i in range(M):
                for j in range(N):
                    if visited[i][j]==True:
                        v[i][j]=1;
                    else:
                        v[i][j]=0;
         return min_dist;

           
        

    # set (i, j) cell as visited
    visited[i][j] = 1

    # go to bottom cell
    if isValid(i + 1, j) and isSafe(mat, visited, i + 1, j):
        min_dist = findShortestPath(mat, visited, i + 1, j, x, y, min_dist, dist + 1)

    # go to right cell
    if isValid(i, j + 1) and isSafe(mat, visited, i, j + 1):
        min_dist = findShortestPath(mat, visited, i, j + 1, x, y, min_dist, dist + 1)

    # go to top cell
    if isValid(i - 1, j) and isSafe(mat, visited, i - 1, j):
        min_dist = findShortestPath(mat, visited, i - 1, j, x, y, min_dist, dist + 1)

    # go to left cell
    if isValid(i, j - 1) and isSafe(mat, visited, i, j - 1):
        min_dist = findShortestPath(mat, visited, i, j - 1, x, y, min_dist, dist + 1)

    # Backtrack - Remove (i, j) from visited matrix
    visited[i][j] = 0

    return min_dist


if __name__ == '__main__':

    mat = [
[1 ,1 ,1 ,1 ,1 ,1 ,1 ,1],

[1 ,0,0, 0 ,1 ,1 ,1, 1],

[1 ,0 ,0 ,0 ,0 ,0, 0 ,1],

[1 ,1, 1, 0, 0, 1, 0, 1],

[1, 0 ,1 ,0 ,0 ,1 ,0 ,1],

[1 ,0 ,0 ,0 ,0 ,0 ,0, 1],


[1, 1, 1, 1 ,1 ,1 ,1 ,1]
    ]

    


    si=1;  // starting index x -coord
    sj=1;
    
    ei=4;
    ej=4;
       # construct a matrix to keep track of visited cells
    visited = [[0 for x in range(N)] for y in range(M)]

    min_dist = findShortestPath(mat, visited, si, sj, ei, ej)
    
    for i in range(M):
        for j in range(N):
            if i==si and j==sj:
                print("S", end=" ")
            elif i==ei and j==ej:
                print("G", end=" ")
            elif v[i][j]==True:
                print("*", end=" ")
            else:
                print(mat[i][j], end=" ")
            
        print("\n")    
        

    if min_dist != float('inf'):
        print("The shortest path from source to destination has length", min_dist)
    else:
        print("Destination can't be reached from source")