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;

Consider the maze given below.

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.

Click 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@@

Click here to learn more about FACE Prep PRO

Recommended Programs

• Minimum and maximum values of a given expression
• Minimum sum partition problem
• Number of ways to reach the nth stair
• Word break problem