# Backtracking – Rat In A Maze Puzzle

Given a maze, NxN matrix. A rat has to find a path from source to destination. maze[0][0] (left top corner)is the source and maze[N-1][N-1](right bottom corner) is destination. There are a few cells that are blocked, which means the rat cannot enter those cells. The rat can move in any direction ( left, right, up, and down).

Input: A 2D matrix with 0’s and 1’s filled in it. 0 means that the cell is blocked and 1 means the rat can move to that cell.

Approach:

• Create a solution matrix of the same structure as the maze.
• Whenever the rat moves to a cell in a maze, mark that particular cell in the solution matrix.
• At the end print the solution matrix, follow that 1’s from the top left corner, it will be that path for the rat.

Algorithm:

1. If the rat reaches the destination
• print the solution matrix.
• Else
• Mark the current cell in the solution matrix as 1
• If the previous step is not in the vertical direction (upwards) then move forward in the vertical direction(downwards) and recursively check if this movement leads to the solution.
• If movement in the above step doesn’t lead to the solution and If the previous step is not in the horizontal direction (towards the left) then move forward in the horizontal direction(towards the right) and recursively check if this movement leads to the solution.
2. If movement in the above step doesn’t lead to the solution and If the previous step is not in the vertical direction (downwards) then move forward in the horizontal direction(upwards) and recursively check if this movement leads to the solution.
3. If movement in the above step doesn’t lead to the solution and If the previous step is not in the horizontal direction (towards the right) then move forward in the horizontal direction(towards the left) and recursively check if this movement leads to the solution.
4. If none of the above solutions works then BACKTRACK and mark the current cell as 0.

NOTE: It is important to check the previous direction in which the rat has moved because if the rat will move in the opposite direction w.r.t its previous direction then the rat might end up in an infinite loop. For example: if the rat has moved to its left in the previous direction then if it next moves to the right then the moving left option will be available again then the rat will move to the left again, then again right, and so on

Code:

Output:

``` 1 0 1 1 1
1 1 1 0 1
0 0 0 1 1
0 0 0 1 0
0 0 0 1 1

```

Reference: http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

### 6 thoughts on “Backtracking – Rat In A Maze Puzzle”

1. I think there is one step missed and it will not work where there is loop inside path e.g.
1 0 1 1 1
1 1 1 1 1
0 1 0 1 1
0 1 1 1 0
0 0 0 1 1
It has a loop and with above algorithm it will keep going in the inner 1’s forever. So we should also check if soln matrix is not already traversed for the next step.
if (isSafeToGo(maze, x, y, N) && soln[x][y] != 1)

• yes you are right that is why it has been ordered in particular sequence, anyways the suggestion you provided can also be implemented.

• What is the use of direction? It can work even without direction. Please explain.

2. What if there are more than 1 steps?

3. Hi, thanks for sharing

If people have an interest in backtracking Algo in C++ :

I have a complete simple example on my github with backtracking into maze.
You can explore the Core library or play directly in the term.

The game : https://github.com/benoit-b