Backtracking — Rat In A Maze Puzzle

Given a maze, NxN matrix. A rat has to find a path from source to des­ti­na­tion. maze[0][0] (left top corner)is the source and maze[N-1][N-1](right bot­tom cor­ner) is des­ti­na­tion. There are few cells which are blocked, means rat can­not enter into those cells. Rat can move in any direc­tion ( left, right, up and down).

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

Rat In A Maze Puzzle

Approach:

• Cre­ate a solu­tion matrix of the same struc­ture as maze.
• When­ever rat moves to cell in a maze, mark that par­tic­u­lar cell in solu­tion matrix.
• At the end print the solu­tion matrix, fol­low that 1’s from the top left cor­ner, it will be that path for the rat.

Algo­rithm:

1. If rat reaches the des­ti­na­tion
• print the solu­tion matrix.
• Else
• Mark the cur­rent cell in solu­tion matrix as 1
• If pre­vi­ous step is not in ver­ti­cal direc­tion (upwards) then move for­ward in the ver­ti­cal direction(downwards) and recur­sively check if this move­ment leads to solution.
• If move­ment in above step doesn’t lead to the solu­tion and If pre­vi­ous step is not in hor­i­zon­tal direc­tion (towards left) then move for­ward in the hor­i­zon­tal direction(towards right) and recur­sively check if this move­ment leads to solution.
2. If move­ment in above step doesn’t lead to the solu­tion and If pre­vi­ous step is not in ver­ti­cal direc­tion (down­wards) then move for­ward in the hor­i­zon­tal direction(upwards) and recur­sively check if this move­ment leads to solution.
3. If move­ment in above step doesn’t lead to the solu­tion and If pre­vi­ous step is not in hor­i­zon­tal direc­tion (towards right) then move for­ward in the hor­i­zon­tal direction(towards left) and recur­sively check if this move­ment leads to solution.
4. If none of the above solu­tion works then BACKTRACK and mark the cur­rent cell as 0.

NOTE: It is impor­tant to check the pre­vi­ous direc­tion in which the rat has moved because if rat will move in the oppo­site direc­tion w.r.t its pre­vi­ous direc­tion then rat might end up in infi­nite loop. Exam­ple: if rat has moved to its left in the pre­vi­ous direc­tion then if in next moves to right then mov­ing left option will be avail­able again then rat will move to left again , then again right and so on

Code:

Out­put:

``` 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

```

Ref­er­ence: http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

You may also like...

• Nikhil Kumar

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 algo­rithm it will keep going in the inner 1’s for­ever. So we should also check if soln matrix is not already tra­versed for the next step.
if (isSafeToGo(maze, x, y, N) && soln[x][y] != 1)

• tuto­ri­al­hori­zon

yes you are right that is why it has been ordered in par­tic­u­lar sequence, any­ways the sug­ges­tion you pro­vided can also be implemented.

• MURHY

What is the use of direc­tion? It can work even with­out direc­tion. Please explain.

• Nikhil P

Your solu­tion will not work if the maze has loops.…
eg: https://ideone.com/WiC5KO