Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

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.