Rat in a Maze Problem in DSA C - Execution Trace

Concept Flow - Rat in a Maze Problem

Start at maze[0

↓

Check if current cell is safe

↓

Mark cell as path

↓

Try move Right

→Try move Down

↓

If move leads to exit

→Backtrack

↓

Exit found

The rat starts at the top-left cell and tries to move right or down if the cell is safe. If stuck, it backtracks until it finds the exit or no path exists.

Execution Sample

DSA C

int maze[4][4] = {
  {1, 0, 0, 0},
  {1, 1, 0, 1},
  {0, 1, 0, 0},
  {1, 1, 1, 1}
};

solveMaze(maze, 0, 0);

This code tries to find a path from top-left to bottom-right in a 4x4 maze using backtracking.

Execution Table

Step	Current Position (row,col)	Is Safe?	Action	Path Matrix State
1	(0,0)	Yes	Mark path, try Right	[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
2	(0,1)	No	Backtrack	[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
3	(1,0)	Yes	Mark path, try Right	[[1,0,0,0],[1,0,0,0],[0,0,0,0],[0,0,0,0]]
4	(1,1)	Yes	Mark path, try Right	[[1,0,0,0],[1,1,0,0],[0,0,0,0],[0,0,0,0]]
5	(1,2)	No	Backtrack	[[1,0,0,0],[1,1,0,0],[0,0,0,0],[0,0,0,0]]
6	(2,1)	Yes	Mark path, try Right	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,0,0,0]]
7	(2,2)	No	Backtrack	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,0,0,0]]
8	(3,1)	Yes	Mark path, try Right	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,0,0]]
9	(3,2)	Yes	Mark path, try Right	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,1,0]]
10	(3,3)	Yes	Mark path, Exit found	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,1,1]]

💡 Reached bottom-right cell (3,3), path found.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 6	After Step 8	After Step 9	Final
row	0	0	1	1	2	3	3	3
col	0	0	0	1	1	1	2	3
path matrix	[all 0]	[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[1,0,0,0],[1,0,0,0],[0,0,0,0],[0,0,0,0]]	[[1,0,0,0],[1,1,0,0],[0,0,0,0],[0,0,0,0]]	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,0,0,0]]	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,0,0]]	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,1,0]]	[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,1,1]]

Key Moments - 3 Insights

Why do we backtrack when the cell is not safe?

When the cell is not safe (like (0,1) at step 2), we cannot move there, so we undo the last move and try another path. This is shown in execution_table rows 2 and 5.

How do we know when the exit is found?

The exit is the bottom-right cell (3,3). When we mark it as path (step 10), we stop searching. See execution_table row 10.

Why do we mark the path matrix at each safe cell?

Marking the path matrix helps us remember the route taken. It shows the current path and helps avoid revisiting cells. This is visible in variable_tracker for path matrix.

Visual Quiz - 3 Questions

Look at the execution_table, what is the path matrix state after step 4?

A [[1,0,0,0],[1,0,0,0],[0,0,0,0],[0,0,0,0]]

B [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

C [[1,0,0,0],[1,1,0,0],[0,0,0,0],[0,0,0,0]]

D [[1,1,0,0],[1,1,0,0],[0,0,0,0],[0,0,0,0]]

💡 Hint

Check execution_table row 4 under 'Path Matrix State'

At which step does the rat first backtrack due to an unsafe cell?

A Step 2

B Step 5

C Step 7

D Step 3

💡 Hint

Look for the first 'Backtrack' action in execution_table

If the cell (1,1) was blocked (0), how would the path matrix after step 4 change?

A It would mark (1,1) as 1 anyway

B It would be same as step 3: [[1,0,0,0],[1,0,0,0],[0,0,0,0],[0,0,0,0]]

C It would mark (0,1) as 1

D It would mark (2,1) as 1

💡 Hint

Check variable_tracker and execution_table for step 4 path marking

Concept Snapshot

Rat in a Maze Problem:
- Start at maze[0][0], try moves Right and Down
- Move only if cell is safe (value 1)
- Mark path in a separate matrix
- Backtrack if stuck
- Stop when bottom-right cell is reached
- Uses recursion and backtracking

Full Transcript

The Rat in a Maze problem involves finding a path from the top-left corner to the bottom-right corner of a maze represented by a 2D grid. The rat can move only to cells that are safe (marked 1). Starting at (0,0), the rat tries to move right or down. If a move leads to an unsafe cell or dead end, it backtracks to try other paths. The path is recorded in a separate matrix marking the route taken. The process continues until the exit cell is reached or no path exists. The execution table shows each step with the current position, safety check, action taken, and the path matrix state. Variable tracking shows how row, column, and path matrix change over time. Key moments clarify why backtracking happens, how exit is detected, and why path marking is important. The visual quiz tests understanding of path states and backtracking steps. This problem is a classic example of recursion and backtracking in algorithms.