Maze Solver
Method used :
Backtracking Algorithm: Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally. Solving one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree) is the process of backtracking.
Approach:
Form a recursive function, which will follow a path and check if the path reaches the destination or not. If the path does not reach the destination then backtrack and try other paths.
Algorithm:
- Create a solution matrix, initially filled with 0’s.
- Create a recursive function, which takes an initial matrix, output matrix and position of rat (i, j).
- if the position is out of the matrix or the position is not valid then return.
- Mark the position output[i][j] as 1 and check if the current position is the destination or not. If the destination is reached print the output matrix and return.
- Recursively call for position (i+1, j) and (i, j+1).
- Unmark position (i, j), i.e output[i][j] = 0.
Complexity Analysis:
- Time Complexity: O(2^(n^2)). The recursion can run upperbound 2^(n^2) times.
- Space Complexity: O(n^2). Output matrix is required so an extra space of size n*n is needed.
Demo :