Rat in a maze problem using backtracking | faceprep

Program to solve Rat in a maze problem using backtracking is discussed here. Given a maze where 1 represent free space and 0 represented it is blocked. Print the path from 0,0 to n-1,n-1 if exists or print -1;

Consider the maze given below.

rat in a maze problem

Gray blocks represent dead ends (value = 0) and path can be traced only using the white path(value = 1).

The binary matrix representation of the above maze (a) is given as

{1, 0, 0, 0}
{1, 0, 0, 0}
{1, 1, 1, 1}
{0, 0, 0, 1}

The highlighted lines in (b) show the path to reach the destination from the source.

Algorithm for rat in a maze problem

1. If the destination point is reached,

  •      Print the solution_matrix.

2. Else

  • Mark the current cell in the solution_matrix as 1.
  • Move forward in the horizontal direction and recursively check if this move leads to the solution.
  • If the move chosen in the above step doesn’t lead to a solution then move down and check if this move leads to the solution.
  • If none of the above solutions works then unmark this cell as 0 (backtrack) and return false.

Program for rat in a maze problem is given below.

/* C++ program for rat in a maze problem */
#include<iostream>
using namespace std;
bool isSafe(int r,int c,int n,int **maze)
{
   if( r < 0 || r >= n )
       return false;
   if( c < 0 || c >= n )
       return false;
   if(maze[r][c])
       return true;
   return false;
}
bool solvemaze(int ** maze,int i,int j,int ** soln,int n)
{
   if(i == n-1 && j == n-1)
   {
       soln[i][j]=1;
       return true;
   }
   if(isSafe(i,j,n,maze))
   {
       soln[i][j]=1;
       if(solvemaze(maze,i+1,j,soln,n))
           return true;
       if(solvemaze(maze,i,j+1,soln,n))
           return true;
       soln[i][j]=0;
   }
   return false;
}
int main()
{
   int n;
   cin>>n;
   int** maze = new int*[n];
   for(int i = 0; i < n; ++i)
       maze[i] = new int[n];
   int** soln = new int*[n];
   for(int i = 0; i < n; ++i)
       soln[i] = new int[n];
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<n;j++)
       {
           cin>>maze[i][j];
           soln[i][j]=0;
       }
   }
   if(solvemaze(maze,0,0,soln,n))
   {
       for(int i=0;i<n;i++)
       {
           for(int j=0;j<n;j++)
               cout<<soln[i][j]<<” “;
           cout<<endl;
       }
   }
   else
   {

       cout<<“-1”;
   }
}

Test Case 1

I/P
3
1 1 0
0 1 1
1 1 1
O/P
1 1 0
0 1 0
0 1 1

Test Case 2

I/P
5
1 1 0 0 1
0 1 1 1 0
1 1 1 0 1
1 1 1 1 1
1 1 1 1 1
O/P
1 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 1 1 1

Test Case 3

I/P
5
1 0 0 0 1
0 1 1 1 0
1 1 1 0 1
1 1 1 1 1
1 1 1 1 1
O/P
-1

Test Case 4

I/P
4
0 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1
O/P
-1

Test Case 5

I/P
4
1 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1
O/P
1 0 0 0
1 0 0 0
1 1 1 1
0 0 0 1