Rat inside a maze (Using Backtracking Algorithm)

05 min read

Consider a situation where a rat is dropped at the source and the rat has to reach the destination node in the best path possible. The black nodes in the figure mean to block the way for the rat and hence rat has to reach destination following the path in white nodes. Write a program such that the rat reaches the destination with the best possible route in the given maze.

Solution:

Step 1: Convert the given maze into a readable matrix where the black nodes are represented by zero's and white nodes are represented by one. Now a program has to be written to traverse on the ones to reach the destination node. 

This problem can typically be solved by two methods. 

One is by the native method of finding out all possible paths and then finding the minimum distance or minimum hops path that needs to be taken by the rat to reach the destination. This procedure is complex in nature and a lot of memory is being used to store all possible paths and later check the best possible route in it.

Instead of the above method, we could use backtracking algorithm:

Backtracking algorithm can be defined as an algorithm used to find all possible solutions in a problem. This algorithm traverses one node at a time and incrementally builds the solutions. In each step, if the algorithm recognises any block that might not be used to find the best path that block is cancelled, i.e in this case that block is also marked as '0'. This reduces the number of trails and avoids the system from storing all possible path traversals till the last step of the program.

Following is an example maze.

 Gray blocks are dead ends (value = 0). 

 Binary representation of the matrix is given below:

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

The best path solution is marked.

 solution matrix /output of program for the above input matrix.

                {1, 0, 0, 0}
                {1, 1, 0, 0}
                {0, 1, 0, 0}
                {0, 1, 1, 1}
 All enteries in solution path are marked as 1.

 

 

 

C/C++ Implementation of Backtracking solution

/* C/C++ program to solve Rat in a Maze problem using
   backtracking */
#include<stdio.h>

// Maze size
#define N 4 

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            printf(" %d ", sol[i][j]);
        printf("\n");
    }
}

/* A utility function to check if x,y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
    // if (x,y outside maze) return false
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;

    return false;
}

/* This function solves the Maze problem using Backtracking.  It mainly
   uses solveMazeUtil() to solve the problem. It returns false if no 
   path is possible, otherwise return true and prints the path in the
   form of 1s. Please note that there may be more than one solutions, 
   this function prints one of the feasible solutions.*/
bool solveMaze(int maze[N][N])
{
    int sol[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    if(solveMazeUtil(maze, 0, 0, sol) == false)
    {
        printf("Solution doesn't exist");
        return false;
    }

    printSolution(sol);
    return true;
}

/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
    // if (x,y is goal) return true
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }

    // Check if maze[x][y] is valid
    if(isSafe(maze, x, y) == true)
    {
        // mark x,y as part of solution path
        sol[x][y] = 1;

        /* Move forward in x direction */
        if (solveMazeUtil(maze, x+1, y, sol) == true)
            return true;

        /* If moving in x direction doesn't give solution then
           Move down in y direction  */
        if (solveMazeUtil(maze, x, y+1, sol) == true)
            return true;

        /* If none of the above movements work then BACKTRACK: 
            unmark x,y as part of solution path */
        sol[x][y] = 0;
        return false;
    }   

    return false;
}

// driver program to test above function
int main()
{
    int maze[N][N]  =  { {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1}
    };

    solveMaze(maze);
    return 0;
}

Java Implementation of Backtracking solution

/* Java program to solve Rat in a Maze problem using
   backtracking */

public class RatMaze
{
    final int N = 4;

    /* A utility function to print solution matrix
       sol[N][N] */
    void printSolution(int sol[][])
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                System.out.print(" " + sol[i][j] +
                                 " ");
            System.out.println();
        }
    }

    /* A utility function to check if x,y is valid
        index for N*N maze */
    boolean isSafe(int maze[][], int x, int y)
    {
        // if (x,y outside maze) return false
        return (x >= 0 && x < N && y >= 0 &&
                y < N && maze[x][y] == 1);
    }

    /* This function solves the Maze problem using
       Backtracking. It mainly uses solveMazeUtil()
       to solve the problem. It returns false if no
       path is possible, otherwise return true and
       prints the path in the form of 1s. Please note
       that there may be more than one solutions, this
       function prints one of the feasible solutions.*/
    boolean solveMaze(int maze[][])
    {
        int sol[][] = {{0, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 0}
        };

        if (solveMazeUtil(maze, 0, 0, sol) == false)
        {
            System.out.print("Solution doesn't exist");
            return false;
        }

        printSolution(sol);
        return true;
    }

    /* A recursive utility function to solve Maze
       problem */
    boolean solveMazeUtil(int maze[][], int x, int y,
                          int sol[][])
    {
        // if (x,y is goal) return true
        if (x == N - 1 && y == N - 1)
        {
            sol[x][y] = 1;
            return true;
        }

        // Check if maze[x][y] is valid
        if (isSafe(maze, x, y) == true)
        {
            // mark x,y as part of solution path
            sol[x][y] = 1;

            /* Move forward in x direction */
            if (solveMazeUtil(maze, x + 1, y, sol))
                return true;

            /* If moving in x direction doesn't give
               solution then  Move down in y direction */
            if (solveMazeUtil(maze, x, y + 1, sol))
                return true;

            /* If none of the above movements work then
               BACKTRACK: unmark x,y as part of solution
               path */
            sol[x][y] = 0;
            return false;
        }

        return false;
    }

    public static void main(String args[])
    {
        RatMaze rat = new RatMaze();
        int maze[][] = {{1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };
        rat.solveMaze(maze);
    }
}

Python3 Implementation of Backtracking solution

# Python3 program to solve Rat in a Maze 
# problem using backracking 

# Maze size
N = 4

# A utility function to print solution matrix sol
def printSolution( sol ):
    
    for i in sol:
        for j in i:
            print(str(j) + " ", end="")
        print("")

# A utility function to check if x,y is valid
# index for N*N Maze
def isSafe( maze, x, y ):
    
    if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1:
        return True
    
    return False

""" This function solves the Maze problem using Backtracking. 
    It mainly uses solveMazeUtil() to solve the problem. It 
    returns false if no path is possible, otherwise return 
    true and prints the path in the form of 1s. Please note
    that there may be more than one solutions, this function
    prints one of the feasable solutions. """
def solveMaze( maze ):
    
    # Creating a 4 * 4 2-D list
    sol = [ [ 0 for j in range(4) ] for i in range(4) ]
    
    if solveMazeUtil(maze, 0, 0, sol) == False:
        print("Solution doesn't exist");
        return False
    
    printSolution(sol)
    return True
    
# A recursive utility function to solve Maze problem
def solveMazeUtil(maze, x, y, sol):
    
    #if (x,y is goal) return True
    if x == N - 1 and y == N - 1:
        sol[x][y] = 1
        return True
        
    # Check if maze[x][y] is valid
    if isSafe(maze, x, y) == True:
        # mark x, y as part of solution path
        sol[x][y] = 1
        
        # Move forward in x direction
        if solveMazeUtil(maze, x + 1, y, sol) == True:
            return True
            
        # If moving in x direction doesn't give solution 
        # then Move down in y direction
        if solveMazeUtil(maze, x, y + 1, sol) == True:
            return True
        
        # If none of the above movements work then 
        # BACKTRACK: unmark x,y as part of solution path
        sol[x][y] = 0
        return False

# Driver program to test above function
if __name__ == "__main__":
    # Initialising the maze
    maze = [ [1, 0, 0, 0],
             [1, 1, 0, 1],
             [0, 1, 0, 0],
             [1, 1, 1, 1] ]
             
    solveMaze(maze)


Output: The 1 values show the path for rat

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

 

 

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error