Rat in a Maze Problem (Backtracking)

Problem Statement

The problem is a rat in a maze problem. Consider a rat placed at (0, 0) in a square matrix of order N*N. It has to reach the destination at (n-1, n-1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line contains an integer N denoting the size of the square matrix. The next line contains N*N space-separated values of the matrix m where 0’s represents blocked paths and 1 represents valid paths.

Output:
For each test, case output will be space-separated sorted strings denoting all directions, which the rat could take to reach the destination. Print -1 if no such path exists.

User Task:
Your task is to complete the function printPath() which returns a sorted array of strings denoting all the possible paths which the rat can take to reach the destination at (n-1, n-1). If no such path exists the function should return an empty array.

Constraints:
1 <= T <= 100
2 <= N <= 5
0 <= matrix[i][j] <= 1


Example
Input:

3
4
1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1
4
1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1
2
1 0 1 0 

Output:
DRDDRR
DDRDRR DRDDRR
-1
Explanation:
Testcase 2: The given input is in the form
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
For the above matrix the rat can reach the destination at (3, 3) from (0, 0) by two paths ie DRDDRR and DDRDRR when printed in sorted order we get DDRDRR DRDDRR.

Analysis of Problem Statement

You are given 2-D matrix of size N*N and you have to find all paths so that rat can reach the maze. In N*N matrix ‘1’ signifies that you can move to that block and ‘0’ signifies that you cannot move to that block.

Rat is initially at (0,0) cell and maze is present at (N-1,N-1) cell. Now you have to find all paths if present for the rat to reach its maze.

rat in a maze problem
rat in a maze problem

In the above example, there is one path present. Your task is to print the direction in which rat should move to reach it’s destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).

Output : DRRURRDDLDDR

If multiple paths are present you should print all the paths separated by a space.

Hope Problem Statement is clear.

Approach to the Rat in a maze problem

This is clearly a backtracking Problem, where we have to find the path from source to destination.

To solve this puzzle, we first start from the source and move in a direction where the path is not blocked. If taken path makes us reach to the destination then the puzzle is solved else, we come back and change our direction of the path taken.

Here we will write a recursive Algorithm which will search it’s path by it’s own, we just need to specify some of the conditions and rest work will be done by recursion itself.

Let’s move step by step so that we can understand the algorithm clearly.

Recursive Function

It’s clear that we will solve this problem by using recursion. So, let’s discuss the approach to write the recursive function.

Base Condition for the Recursion

The base condition will be simple, we cannot go out of the square matrix, and also we cannot move to the block with integer ‘0’ because ‘0’ means path is blocked.

Also, we will keep track of a visited array, to insure that we are not visiting the same block which we crossed earlier. So if the block is already visited, we will simply return it.

So, these are the base condition required for our algorithm.

Let see the code for base condition,

if(i < 0 || i >= n || j < 0 || j >= n)
{
    return;                // For not going out of the square matrix
}
if(m[i][j] == 0){
    return;                // For not going to the blocked area
}
if(vis[i][j] == 1){
    return;                // For not going to the visited block 
}

Hope above base condition is clear to you, these are very simple conditions. So, let’s move ahead.

Main body of the Recursion

For the sake of simplicity, let’s first find the path for the rat to reach the maze or let us first check whether there is any path present or not for the rat to reach the maze.

Later, we will modify the recursion to also find the direction of the path.

The body of the recursion will be simple, the rat can move only in four directions. So if the current position of the rat is M[x][y], then it can move to M[x-1][y], M[x+1][y], M[x][y-1], M[x][y+1]. Isn’t it?

It is as simple as that and this is the information we need to specify in the body of the recursion and rest work will be tackled by our base condition.

So, let’s see the code and we will then understand it by an example.

Code

int cnt = 0;
void dfs(int m[MAX][MAX],int i,int j,int n,int vis[MAX][MAX])
{
    if(i < 0 || i >= n || j < 0 || j >= n) return;                
    if(m[i][j] == 0 || vis[i][j] == 1) return;        
    
    if(i == n-1 && j == n-1)
    {
        cnt++;
        vis[i][j] = 0;
        return;
    }
    
    vis[i][j] = 1;
  
    dfs(m,i-1,j,n,vis);
    dfs(m,i+1,j,n,vis);
    dfs(m,i,j-1,n,vis);
    dfs(m,i,j+1,n,vis);
    
    vis[i][j] = 0;
    return; 
}

If we reach the coordinate M[n-1][n-1] then count will get updated from that we will know if there is any path present or not.

Let us understand the code step by step and also with an help of a example.

The parameters of the recursive function are simple, the matrix M[][], the coordinates [i][j], the size of the array N and the visited array for keeping the track of the path.

rat in a maze problem

This is the 2-D Matrix given to us and we are currently at the source M[0][0] and we have to reach the maze present at M[3][3].

Now let us analyse the recursion by the help of below diagram.

rat in a maze problem

Hope, the above diagram is clear. The recursion tree is incomplete but the process will go on like this.

Note the recursive call which are returning is actually going to our base condition.

dfs(-1, 0) is actually going out of the square matrix.
dfs(0, 0) is actually visited before, so it is returned.

By going this way, this Algorithm will find it’s own path. Hope the recursion body is clear to you. If not clear then try to draw a recursion diagram by taking a small example and try to follow the steps which I have mentioned above.

What if a path is found ??

Now suppose the above algorithm finds a path by the above recursion but this is not the end of our solution.

We need to find all the path from source to destination. So for this we will again return back and we will unvisit the visited block, so that it can find more ways to reach the destination.

We will try to understand this part by taking an small example,

rat in a maze problem

In the above example, there are two paths to reach destination. We will see it’s recursion tree to understand how we will find both the paths.

rat in a maze problem

The first path is found, now our task is to find the second path, for this we will unvisit the remaining nodes and we will try to find the other path.

rat in a maze problem

This is how, recursion will find the second path, first it will unvisit the visited node (marked by grey) and then recursion will continue. This way it will find the second path.

Hope recursion is clear and now I hope you can visualize the bigger picture that how rat is finding it’s own way to reach the maze.

Solution to the Rat in a maze Problem

We have discussed the main logic of the problem and now we need to wrap up all the above discussion to solve the actual problem.

In the actual Problem, we have to find the way as well as we have to specify the direction in which rat has to travel to reach the maze.

We will use string to store the directions and when we reach the destination, we will store that string to the vector and at last we will return that vector.

Let’s see the code for it,

Complete Code for C/C++

vector<string> s;

void dfs(int m[][MAX],int i,int j,int n,string st,int vis[][MAX])
{
    if(i < 0 || i >= n || j < 0 || j >= n) return;
    if(m[i][j] == 0 || vis[i][j] == 1) return;
    
    if(i == n-1 && j == n-1)
    {
        s.push_back(st);
        vis[i][j] = 0;
        return;
    }
    
    vis[i][j] = 1;
    
    st.push_back('U');
    dfs(m,i-1,j,n,st,vis);
    st.pop_back();
    
    st.push_back('D');
    dfs(m,i+1,j,n,st,vis);
    st.pop_back();
    
    st.push_back('L');
    dfs(m,i,j-1,n,st,vis);
    st.pop_back();
    
    st.push_back('R');
    dfs(m,i,j+1,n,st,vis);
    st.pop_back();
    
    vis[i][j] = 0;
    
    return;
    
}
vector<string> printPath(int m[MAX][MAX], int n)
{
    string st = "";
    s.clear();
    
    int vis[MAX][MAX];
    for(int i = 0;i<n;i++){
        for(int j=0;j<n;j++){
            vis[i][j] = 0;
        }
    }
    
    dfs(m,0,0,n,st,vis);
    sort(s.begin(),s.end());
    return s;
}

Note if no such path exists the function should return an empty vector. Don’t print (-1) for that case as it is clearly mentioned in the Problem Statement. The (-1) case will be handled by GFG.

I hope this explanation of rat in maze problem and working of Recursion are
clear to you all.

That’s all folks..!!!

Similar Problem : Find whether path exist

Tagged : /

N Queen Problem Using Backtracking

N Queen Problem

In N Queen Problem, Given a square of size N*N. You have to place 1 Queen in each row, such that no queen can attack any other Queen placed in Square, we use backtracking for this

N Queen Problem

Above Square is of 4*4 size and we show the places where I placed the Queen’s so no Two queen Attack Each other.

N Queen Problem Algorithm –

Read this algorithm by making 4*4 Chess Board

The first thing we think is, we place our first Queen on (0,0) i.e first row and first column now,

Step – 1

We place second Queen on (1,0) i.e second row and first column and if it is clashing with our previous placed queen then we move next column of same row, i.e (1,1) and if this position is also clashing we move our second queen to (1,2) and we keep incrementing until we found safe position

Step – 2

Now, If we can not find any Place in the row to place our queen, what should I do then. Yes, you think right, we move our previous placed queen to one steps further in same row, this is where I use BackTracking. I go to our back stage and increment 1 then I procced further

In 4*4 Square

If we follow above algorithm from start

Position of first Queen – (0,0)

Position of second Queen – (1,2)

Hence, we see that there is no any place where we placed our third queen, so we move our second Queen to one step further in same row,

Now,

Position of First Queen – (0,0)

Position of Second Queen – (1,3) [We move our second queen to +1 in same row]

Now, we see that again there is no any place where we placed our third queen, so we move our second Queen to one step further but there is also no any place where we move our second queen,

So we move our first Queen to (0,1) and start again as we start above.

From following above steps final position is

Position of First Queen – (0,1)

Position of Second Queen – (1,3)

Position of Third Queen – (2,0)

Position of Fourth Queen – (3,2)

Now, We know algorithm, we only need is code. Try Yourself and then Come Back

  1. We placed our Queen in (0,0) and mark the cell to -1,
  2. By placing second Queen we check where value of column of same row, diagonal’s cell is not -1 and if we not find any place where -1 is not present we placed our queen there and then go for third queen
  3. If we did not find any place to place our queen , we increase our position and then again check for same row and it’s  column
  4. If we did not find any position, we mark our previous placed queen to 0 and increase position of our previous placed queen
  5. Finally repeat until we can’t find our position and exit;

#include<iostream>
using namespace std;

void print(int a[10][10],int n){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cout<<a[i][j]<<” “;
cout<<endl;
}
bool check(int a[10][10],int x,int y,int n){
for(int i=x-1;i>=0;i–)

{
if(a[i][y]==1)

return false;
}
for(int i=x-1,j=y-1;i>=0 && j>=0;i–,j–){
if(a[i][j]==1)

return false;
}
for(int i=x-1,j=y+1;i>=0 && j<n;i–,j++){
if(a[i][j]==1)

return false;
}
return true;
}
void PlacedNQUeend(int a[10][10],int n,int i)
{
if(i==n){
print(a,n);
return;
}
for(int j=0;j<n;j++)

{
if(check(a,i,j,n))

{
a[i][j]=1;
PlacedNQUeend(a,n,i+1);
a[i][j]=0;
}
}
return;
}

void placeNQueens(int n)
{
int a[10][10];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j]=0;
}
}
PlacedNQUeend(a,n,0);
}

int main(){
int n;
cin >> n ;
placeNQueens(n);

}

Tagged : /

BackTracking| Complete Overview of BackTracking

Prerequisite for BackTracking

Backtracking is very useful Concept in Competitive Programming. Beginner’s Found Backtracking difficult to understand. Beginner’s  don’t feel confident on Recursion and that is the reason why this concept is difficult for them. Hence for learning Bactracking, it is must that you know what the recursion is.

What is Backtracking

As word Back Tracking is made up of two word’s – Back and Tracking, Hence Tracking from Back. Don’t need to confuse Here! We introduce everything in very easy manner.

First, It is an algorithm Technique which uses recursion to solve problem.

BackTracking - geekstocode

Simple Example of BackTracking

Suppose, You are standing in roundabout and only one direction of roundabout is way to Hospital. Here, You only know is that There are 4 direction of roundabout and one of them leads to your destination and it is also confirms that one of direction must lead to your destination.

So You start going from each direction of roundabout and if you did not find Your destination and you come back to roundabout.

Now you  go to second direction, Here What you do is come back and track to next direction, Hence Here you use this concept.

Professional Definition

Algorithm Technique – Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.

It is an important tool for solving constraint satisfaction problem such as crosswords, verbal arithmetic, Sudoku and many other puzzles.

It is often the most convenient (if not the most efficient) technique for parsing for the knapsack problem and other combinational problems.

This is also the basis of the so-called logic programming. American mathematician D.H Lehmer  was first person who introduce term “backtrack ” in the 1950s

Learn BackTracking by Practise

Easy One –

Example 1 – N Queen Problem

Example 2(Problem Link) – Binary Watch (LeetCode)

Example 3(Problem Link) – Letter Case Permutation (LeetCode)

Example 4 – Rat in a Maze Problem

Tagged : /