Rat in a maze problem in C++

In this blog, we will discuss the Rat in a maze Problem in C++ and see how we can use Backtracking to get the solution.

PROBLEM STATEMENT:

A maze is given as an N*N binary matrix of blocks, where the start position is the top left block (i.e. maze[0][0]) and the destination position is the bottom right block(i.e. maze[n-1][n-1]). A rat wants to move from the start to the destination position. The rat can move in any of the following four directions:

  • Up
  • Down
  • Left
  • Right

In the maze matrix, 0 means that the rat can not go any further than this block and 1 means that this block is free and can be utilized to build a path from source to destination. Here we aim to find all the possible paths on which the rat can travel and reach the destination.

Following is an example maze,

Rat in a maze problem in C++

solve Rat in a maze problem in C++

so the solutions for the above example come out to be, 
       1 0 0 0                1 0 0 0 
       1 1 0 0     and        1 0 0 0 
       0 1 0 0                1 1 0 0 
       0 1 1 1                0 1 1 1 
All entries in solution path are marked as 1.

SOLUTION:

Here the Naive solution would be to generate all the paths from the starting to destination block and check if any of the paths satisfy the given constraints.

while(paths left from source to destination)
{
    if(all the values in this path are 1 and within the matrix)
    {
         print the path
    }  
    generate new path
}

Another solution to this problem is to use backtracking.
For this, we’ll maintain a solution matrix in which we keep a dynamic state of different solutions.
We’ll also create a helper function for a specific point in the matrix; make that point as 1 in our solution matrix and recursively find all the paths towards its left, up, right and down. When we have traversed all the paths from that point we make its value in the solution matrix as 0.This ensures that we have considered all the possible paths from that point.
If we reach the destination position via any of the recursions we print the matrix.

#include<bits/stdc++.h>

using namespace std;

void printSolution(int** solution,int n)
{
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      cout<<solution[i][j] << " ";
    }
    cout<<endl;
  }
}
void MazeUtil(int maze[][20],int** solution,int x,int y,int n)
{
  /*
  If the blocks are outside of he maze or it is a dead end or it has already been travelled
  then we don't need to traverse in that direction and we'll return
  */
  if(x==n-1 && y == n-1)
  {
    solution[x][y] = 1;
    printSolution(solution,n);
    cout<<endl;
  }
  
  if(x >=n || y >= n || x < 0 || y < 0 || maze[x][y] == 0 || solution[x][y] == 1)
  {
    return;
  }
  
  solution[x][y] = 1;
  MazeUtil(maze,solution,x+1,y,n);
  MazeUtil(maze,solution,x,y+1,n);
  MazeUtil(maze,solution,x-1,y,n);
  MazeUtil(maze,solution,x,y-1,n);
  solution[x][y] = 0;
  
}

void RatInAMaze(int maze[][20] , int n)
{
  /*
  Making a N*N dynamic solution matrix
  */
  
  int** solution = new int*[n];
  for(int i=0;i<n;i++)
  {
    solution[i] = new int[n]; 
  }
  int *flag = new int(9);
  
  // The helper function
  MazeUtil(maze,solution,0,0,n);
  
}

int main() {
  int maze[][20] = {{1,0,0,0},
                    {1,1,0,1},
                    {1,1,0,0},
                    {0,1,1,1}};
  RatInAMaze(maze,4);
  
  return 0;
}

Output:

1 0 0 0 
1 0 0 0 
1 1 0 0 
0 1 1 1 

1 0 0 0 
1 1 0 0 
0 1 0 0 
0 1 1 1 

Leave a Reply

Your email address will not be published. Required fields are marked *