Introduction
Let's Consider a rat placed at (0, 0) in an N * N square matrix. It must arrive at the destination on time (N - 1, N - 1). Find all possible routes for the rat to take from source to destination. The rat can move in the following directions: 'U' (up), 'D' (down), 'L' (left), and 'R' (right) (right). A cell in the matrix with a value of 0 indicates that it is blocked and the rat cannot move to it, whereas a cell with a value of 1 indicates that the rat can travel through it.
A maze is in the form of a 2D matrix in which some cells/blocks are blocked. One of the cells is termed as a source cell, from where we have to start. And another one of them is termed a destination cell, where we have to reach. We have to find a path from the source to the destination without moving into any of the blocked cells. A picture of an unsolved maze is shown below, where grey cells denote the dead ends and white cells denote the cells which can be accessed.
To solve these types of puzzles, we first start with the source cell and move in a direction where the path is not blocked. If the path taken makes us reach the destination, then the puzzle is solved. Otherwise, we come back and change our direction of the path taken.
The solution to this maze would look like this:
If this is your very first foray into Backtracking, fear not — it’s mine, too! Let’s tackle it together — and try not to lose our sanity in the process. So many things in this world would have never come into existence if there hadn’t been an issue problem that needed solving. This truth applies to almost everything, but boy, is it obvious in the world of computer science.
So, it’s a big “YES”, but I do think that it’s unique in one way: computer science’s innovations rely and build upon its own abstractions. But what leads to the need for Backtracking algorithms?
See, Backtracking and Recursion, and Euclid GCD Algorithm
What is Backtracking?
Backtracking is a famous algorithmic technique for solving/resolving 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 in time (by time, here, is referred to as the time elapsed till reaching any level of the search tree) is the process of backtracking.
According to the wiki definition, Backtracking can be termed as a general algorithmic technique that
considers searching every possible combination in order to solve a computational problem.
There are three types of problems in backtracking
- Decision Problem: In this, we search for a feasible solution
- Optimization Problem: In this, we search for the best solution
-
Enumeration Problem: In this, we find all feasible solutions
Backtracking is a standard problem-solving technique mainly based on recursion. A backtracking algorithm makes an effort to build a solution to a computational problem incrementally. Whenever the algorithm needs to choose between multiple alternatives to the next component of the solution, it simply tries all possible options recursively step-by-step.
Depth First Search (DFS Algorithm) uses the concept of backtracking at its very core. So, in DFS, we basically try exploring all the paths from the given node recursively until we reach the goal. After we search for a particular branch of a tree in DFS, we can land up in two possible states.
- We land on the goal state in which case we simply exit.
- Or, we did not find the goal state and we hit a dead end. In this scenario, we backtrack to the last checkpoint and we then try out a different branch.
Algorithm to solve a rat in a maze
- Create a solution matrix, initially filled with 0’s.
- Create a recursive function, which takes an initial matrix (Maze), output matrix (Solution), 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.
Implementation of Rat in a Maze Problem in Java
public class ratmaze
{
static int R;
static int C;
void solution(int result[][])
{
System.out.println("matrix formed: ");
for (int r = 0; r < R; r++)
{
for (int c = 0; c < C; c++)
{
System.out.print(" " + result[r][c] + " ");
}
System.out.println();
}
}
boolean ifvalid(int m[][], int r, int c)
{
return (r >= 0 && r < R && c >= 0 && c < C && m[r][c] == 0);
}
boolean find_the_path(int m[][])
{
int maz[][] = new int[R][C];
for(int r = 0; r < R; r++)
{
for(int c = 0; c < C; c++)
{
maz[r][c] = 1;
}
}
if (maze_utility(m, 0, 0, maz) == false)
{
System.out.print("solution not exist");
return false;
}
solution(maz);
return true;
}
boolean maze_utility(int m[][], int r, int c,
int res[][])
{
if (r == R - 1 && c == C - 1 && m[r][c] == 0)
{
res[r][c] = 0;
return true;
}
if (ifvalid(m, r, c) == true)
{
if (res[r][c] == 0)
{
return false;
}
res[r][c] = 0;
if (maze_utility(m, r + 1, c, res))
{
return true;
}
if (maze_utility(m, r, c + 1, res))
{
return true;
}
if (maze_utility(m, r - 1, c, res))
{
return true;
}
if (maze_utility(m, r, c - 1, res))
{
return true;
}
res[r][c] = 1;
return false;
}
return false;
}
public static void main(String argvs[])
{
ratmaze r = new ratmaze();
int m[][] = { { 0, 1, 1, 1 },
{ 0, 0, 1, 0 },
{ 1, 0, 1, 1 },
{ 0, 0, 0, 0 } };
R = m.length;
C = m[0].length;
r.find_the_path(m);
}
}
84+ registered 