Backtracking — Rat in a Maze
Let's take the “Rat in a maze” problem, which is a common example, to understand backtracking
We have given a maze that consists of 1’s & 0’s elements. Element 1 represents the empty cell while element 0 is a wall from which the rat can not pass.
A rat starts from a position (0,0) and has to reach the end of the maze which is position (n-1, m-1). A rat can move to the right cell or below cell of the current position.
Find the path from the start position to the end of the maze.
Sample Input :
[{1, 1, 1, 0},
{1, 0, 0, 0},
{1, 1, 1, 1}]
At position (0,0), there are 2 cases as mentioned below-
Case 1: Rat moves on the right cell
If rat moves on the right cell (0,1) then the rat has to move(0,2) because there is a wall at (1,1) & once it reaches at position (0, 2), the rat cannot move further since there is no element 1 on left/below cell.
Case 2: Rat moves on the below cell
If rat moves below cell than rat path will be (0, 0) → (1, 0) → (2, 0) → (2,1) →(2, 2) → (2, 3)
Position (2, 3) is the end of the grid.
The rat doesn't know which path will lead to the end of the grid so the rat will go on the right cell(case 1) which will be blocker & hence rat has to backtrack it’s own path & reaches at positon (0,0) & will move to below cell (case 2) which will eventually lead to the end of the maze.
Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time
CODE
public findPath(int maze[][], int path[][], int row, int col){
if(row≥ maze.length || col≥maze[0].length || maze[row][col] == 0)
return;
if(row == maze.length-1 && col == maze[0].length-1){
path[row][col] =1;
printMaze(path);
path[row][col] = 0;
return;
}
path[row][col] = 1; // add the current cell into solution maze
findPath(grid, path, row+1, col); // move to right cell
findPath(grid, path, row, col+1);// move to below cell
path[row][col] = 0; // rat has to backtarack hence we have to remove it
}
