Backtracking Using a Stack: A Rat in a Maze

Taken from Geeks for Geeks (Needs to be rewritten)

Rat in a Maze | Backtracking using Stack

A Maze is given as N*M binary matrix of blocks and there is a rat initially at (0, 0) ie. maze[0][0] and the rat wants to eat food which is present at some given block in the maze (fx, fy). In a maze matrix, 0 means that the block is a dead end and 1 means that the block can be used in the path from source to destination. The rat can move in any direction (not diagonally) to any block provided the block is not a dead end.

The task is to check if there exists any path so that the rat can reach the food or not. It is not needed to print the path.

Examples:

Input : maze[4][5] = {
            {1, 0, 1, 1, 0},
            {1, 1, 1, 0, 1},
            {0, 1, 0, 1, 1},
            {1, 1, 1, 1, 1}
        }
        fx = 2, fy=3
Output : Path Found!
The path can be: (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2)  -> (3, 3) -> (2, 3)  

This is the famous Rat in a Maze problem asked in many interviews that can be solved using Recursion and Backtracking. There are ways to solve this problem recursively. However, in this section, we will explore an iterative solution using a stack.

A node structure is used to store the (i, j) coordinates and directions explored from this node and which direction to try out next.

Structure Used:

  1. X : x coordinate of the node
  2. Y : y coordinate of the node
  3. dir : This variable will be used to tell which all directions we have tried and which to choose next. We will try all the directions in anti-clockwise manner starting from Up. Initially it will be assigned 0.
    • If dir=0 try Up direction.
    • If dir=1 try left direction.
    • If dir=2 try down direction.
    • If dir=3 try right direction.
    • Else retract back to the previous block of the maze.

Initially, we will push a node with indexes i=0, j=0 and dir=0 into the stack. We will move to all the direction of the topmost node one by one in an anti-clockwise manner and each time as we try out a new path we will push that node (block of the maze) in the stack. We will increase dir variable of the topmost node each time so that we can try a new direction each time unless all the directions are explored ie. dir=4. If dir equals to 4 we will pop that node from the stack that means we are retracting one step back to the path where we came from.

We will also maintain a visited matrix which will maintain which blocks of the maze are already used in the path or in other words present in the stack. While trying out any direction we will also check if the block of the maze is not a dead end and is not out of the maze too.

We will do this while either the topmost node coordinates become equal to the food’s coordinates that means we have reached the food or the stack becomes empty which means that there is no possible path to reach the food.