Rat in a maze problem using backtracking | faceprep

Rat in a maze problem using backtracking | faceprep

Program to solve Rat in a maze problem using backtracking is discussed here.

Given a maze where 1 represent free space and 0 represented it is blocked. Print the path from 0,0 to n-1, n-1 if exists or print -1;

Rat in a maze problem using backtracking


Consider the maze given below.

Rat in a maze problem using backtracking

Gray blocks represent dead ends (value = 0) and path can be traced only using the white path (value = 1).

The binary matrix representation of the above maze (a) is given as

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

The highlighted lines in (b) show the path to reach the destination from the source.


rat in a maze using backtrack problemClick here to learn more about FACE Prep PRO


Algorithm for rat in a maze problem

1. If the destination point is reached,

  • Print the solution_matrix.

2. Else

  • Mark the current cell in the solution_matrix as 1.
  • Move forward in the horizontal direction and recursively check if this move leads to the solution.
  • If the move chosen in the above step doesn’t lead to a solution then move down and check if this move leads to the solution.
  • If none of the above solutions works then unmark this cell as 0 (backtrack) and return false.

Program for rat in a maze problem

@@coding::1@@


face prep pro ad bannerClick here to learn more about FACE Prep PRO


Recommended Programs


Rat in a maze problem using backtracking

c