Explore
Placement Prep

Edit

Edit

# Rat in a maze problem using backtracking | FACE Prep

Published on 11 Mar 2020

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}
{1, 0, 0, 0}
{1, 1, 1, 1}
{0, 0, 0, 1}


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

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

C++

Output
Input - 3
1 1 0
0 1 1
1 1 1
Output -
1 1 0
0 1 0
0 1 1

Test Case 1

I/P

3

1 1 0

0 1 1

1 1 1

O/P

1 1 0

0 1 0

0 1 1

Test Case 2

I/P

5

1 1 0 0 1

0 1 1 1 0

1 1 1 0 1

1 1 1 1 1

1 1 1 1 1

O/P

1 1 0 0 0

0 1 0 0 0

0 1 0 0 0

0 1 0 0 0

0 1 1 1 1

Test Case 3

I/P

5

1 0 0 0 1

0 1 1 1 0

1 1 1 0 1

1 1 1 1 1

1 1 1 1 1

O/P

-1

Test Case 4

I/P

4

0 0 0 0

1 0 0 1

1 1 1 1

1 0 0 1

O/P

-1

Test Case 5

I/P

4

1 0 0 0

1 0 0 1

1 1 1 1

1 0 0 1

O/P

1 0 0 0

1 0 0 0

1 1 1 1

0 0 0 1

Recommended Programs