Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
What is Backtracking?
1.2.
There are three types of problems in backtracking
1.3.
Algorithm to solve a rat in a maze
2.
Implementation of Rat in a Maze Problem in Java
3.
Implementation of Rat in a Maze in C++
4.
Implementation of Rat Maze in Python
5.
Implementation in C
6.
Frequently Asked Questions
6.1.
What does a rat in a maze mean?
6.2.
How do you solve rat maze problems?
6.3.
What is the time complexity of rat in a maze?
6.4.
How to solve maze problem in Java?
7.
Conclusion
Last Updated: Mar 27, 2024
Hard

Rat in a Maze

Author Ravi Khorwal
1 upvote
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Rat in a Maze

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.

Rat in a Maze problem

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:

Rat in a Maze

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);  
}  
}
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation of Rat in a Maze in C++

#include <bits/stdc++.h>
using namespace std;
#define N 4

bool solve(int m[N][N], int x, int y,int s[N][N]);

bool safe(int m[N][N], int x, int y)
{
    if (x >= 0 && x < N && y >= 0 && y < N && m[x][y] == 1)
        return true;
    return false;
}
void soln(int s[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout<<" "<<s[i][j]<<" ";
        cout<<endl;
    }
}
bool solve(int m[N][N], int x, int y, int s[N][N])
{
    if (x == N - 1 && y == N - 1 && m[x][y] == 1) {
        s[x][y] = 1;
        return true;
    }
    if (safe(m, x, y) == true) {
        if (s[x][y] == 1)
            return false;
        s[x][y] = 1;
        if (solve(m, x + 1, y, s) == true)
            return true;
        if (solve(m, x - 1, y, s) == true)
            return true;
        if (solve(m, x, y + 1, s) == true)
            return true;
        if (solve(m, x, y - 1, s) == true)
            return true;
        s[x][y] = 0;
        return false;
    }
    return false;
}

bool solmaze(int m[N][N])
{
    int s[N][N] = { { 0, 0, 0, 0 },
                    { 0, 0, 0, 0 },
                    { 0, 0, 0, 0 },
                    { 0, 0, 0, 0 } };
    if (solve(m, 0, 0, s) == false) {
        cout<<"Soln not exist";
        return false;
    }
    soln(s);
    return true;
}
int main()
{
    int m[N][N] = { { 1, 0, 0, 0 },
                    { 1, 1, 0, 1 },
                    { 0, 1, 0, 0 },
                    { 1, 1, 1, 1 } };
    solmaze(m);
    return 0;
}

Implementation of Rat Maze in Python

N = 4

def checkposition(m, x, y ):
    if x >= 0 and x < N:
        if y >= 0 and y < N:
            if m[x][y] == 1:
                return True
     
    return False
 

def solvemaze(m):
    sol = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
    ]
     
    if rat_maze_sol(m, 0, 0, sol) == False:
        return False
     
    for i in sol:
        for j in i:
            print(str(j) + " ", end ="")
        print("")
    return True
     
def rat_maze_sol(m, x, y, sol):
    if x == N - 1 and y == N - 1 and m[x][y]== 1:
        sol[x][y] = 1
        return True
         
    if checkposition(m, x, y) == True:
        if sol[x][y] == 1:
            return False
           
        sol[x][y] = 1
         
        if rat_maze_sol(m, x + 1, y, sol) == True:
            return True
             
        if rat_maze_sol(m, x, y + 1, sol) == True:
            return True
           
        
        if rat_maze_sol(m, x - 1, y, sol) == True:
            return True
             
        if rat_maze_sol(m, x, y - 1, sol) == True:
            return True
         
        sol[x][y] = 0
        return False
 

m = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
    ]
            
solvemaze(m)

Implementation in C

#include <stdio.h>
#include <stdbool.h>
#define N 4

bool solve(int m[N][N], int x, int y,int s[N][N]);

bool safe(int m[N][N], int x, int y)
{
	if (x >= 0 && x < N && y >= 0 && y < N && m[x][y] == 1)
		return true;
	return false;
}
void soln(int s[N][N])
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf(" %d ", s[i][j]);
		printf("\n");
	}
}
bool solve(int m[N][N], int x, int y, int s[N][N])
{
	if (x == N - 1 && y == N - 1 && m[x][y] == 1) {
		s[x][y] = 1;
		return true;
	}
	if (safe(m, x, y) == true) {
		if (s[x][y] == 1)
			return false;
		s[x][y] = 1;
		if (solve(m, x + 1, y, s) == true)
			return true;
		if (solve(m, x, y + 1, s) == true)
			return true;
		s[x][y] = 0;
		return false;
	}
	return false;
}
bool solmaze(int m[N][N])
{
	int s[N][N] = { { 0, 0, 0, 0 },
					{ 0, 0, 0, 0 },
					{ 0, 0, 0, 0 },
					{ 0, 0, 0, 0 } };
	if (solve(m, 0, 0, s) == false) {
		printf("Soln not exist");
		return false;
	}
	soln(s);
	return true;
}

int main()
{
	int m[N][N] = { { 1, 0, 0, 0 },
					{ 1, 1, 0, 1 },
					{ 0, 1, 0, 0 },
					{ 1, 1, 1, 1 } };
	solmaze(m);
	return 0;
}

Check out this problem - 8 Queens Problem

Frequently Asked Questions

What does a rat in a maze mean?

Rat in a maze is a problem statement that can be solved with the help of backtracking, and it is one of the most common problems of recursion asked by most of the interviewers in an interview.

How do you solve rat maze problems?

The approach is to code with recursive method. The recursive method will follow a path beginning with the source cell and checking whether or not the path reaches the destination cell. If the path fails to reach the destination cell, then backtrack and try again.

What is the time complexity of rat in a maze?

The time complexity of the rat in a maze is O(2^(n^2)). The recursion can run upper bound 2^(n^2) times. The space complexity is O(n^2) because output matrix is required, so an extra space of size n*n is needed.

How to solve maze problem in Java?

The approach is to code with the recursive method as in the other programming language. In this, we'll check from the beginning whether the path reaches the destination or not. If the path fails to reach the destination cell, then backtrack and try again.

Conclusion

Backtracking is like a sort of permutation in steroids, once a pattern doesn’t match we find another one until there is no more available source, or a certain pattern matched. It can almost solve any problem, e.g. Chess(famous 8 queens problem) or Sudoku (complete solution set), due to its brute-force nature (analogy to permutation).  

Backtracking requires recursion which can be something worse because CPU stack space is limited and can be consumed quickly by recursion.

In a nutshell, we can say three things on behalf of backtracking :

  • It is typically applied to difficult combinatoric problems for which no efficient algorithm for finding, exact solutions possibly exists.
  • Backtracking solves each instance of a problem in an acceptable amount of time.
  • It generates all elements of the problem state.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

You can access the whole working code of “Rat in a Maze” from this GitHub repository. To watch more on backtracking, visit our YouTube channel.

Previous article
Check If a Number is Not a Power of 2
Next article
Word Search
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass