A backtracking algorithm begins in a predefined starting state and then moves fr

Question

A backtracking algorithm begins in a predefined starting state and then moves from state to state in search of a desired ending state. At any point along the way, when there is a choice between several alternative states, the algorithm picks one, possibly at random, and continues. If the algorithm reaches a state that represents an undesirable outcome, it backs up to the last point at which there was an unexplored alternative and tries it. In this way, the algorithm either exhaustively searches all states, or it reaches the desired ending state. Assume you have a maze represented as 2d list, such as in attachment. Write an algorithm that calculates a path from P to T.

Explanation / Answer

# This program finds out whether a path exists betwee a given source and destination cell using backtracking algorithm. If you want me to also print the path, let me know.

# offsets to get the neigbours for a given cell
neighX = [0, -1, 1, 0];
neighY = [-1, 0, 0, 1];

#Checks whether the given move is valid
def isSafe(matrix, m, n, visited, row, col):
    return (row>=0) and (row<m) and (col>=0) and (col<n) and (matrix[row][col]==1 and visited[row][col]==False);

#Recursively finds the path
def doesPathExists(matrix, m, n, visited, curRow, curCol, destX, destY):
    if curRow==destX and curCol==destY:
        return True;

    visited[curRow][curCol] = True;
    for i in range(0, 4):
        newX = curRow + neighX[i];
        newY = curCol + neighY[i];
        if isSafe(matrix, m, n, visited, newX, newY):
                if (doesPathExists(matrix, m, n, visited, newX, newY, destX, destY)):
                    return True;
    return False;

# Declare a matrix, 1 indicates path, 0 indicates no path
m = 5; n = 5;
matrix= [[1, 1, 0, 0, 0],
         [0, 1, 0, 0, 1],
         [1, 1, 1, 1, 1],
         [0, 0, 0, 0, 1],
         [1, 0, 1, 1, 1]];

# boolean array to keep track of visted cells
visited = [[0 for x in range(m)] for y in range(n)];
for i in range(0, m):
    for j in range(0, n):
        visited[i][j] = False;

# Defining source and destination cells and finding out if there exists a path
sourceX = 0; sourceY = 0; destX = 2; destY = 4;
result = doesPathExists(matrix, m, n, visited, sourceX, sourceY, destX, destY);
print "Does Path Exists : ", result;

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.