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.

Practice

1. What is the main goal of the Rat in a Maze problem?

easy

A. Calculate the shortest distance between two points in a maze

B. Count the number of walls in the maze

C. Find a path from the start to the destination in a maze

D. Fill the maze with numbers

Solution

1. Step 1: Understand the problem statement

   The Rat in a Maze problem asks to find a path from the start (usually top-left) to the destination (usually bottom-right) in a maze represented by a grid.

2. Step 2: Identify the goal

   The goal is to find any valid path through open cells (usually marked 1) avoiding blocked cells (usually marked 0).

3. Final Answer:

   Find a path from the start to the destination in a maze -> Option C

4. Quick Check:

   Goal = Find path [OK]

Hint: Look for pathfinding from start to end in the maze [OK]

Common Mistakes:

• Thinking it's about counting walls
• Confusing with shortest path calculation
• Assuming maze filling is required

2. Which of the following is the correct way to declare the maze matrix in C for a 4x4 maze?

easy

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

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

C. int maze[][] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}};

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

Solution

1. Step 1: Understand C array declaration syntax

   In C, a 2D array must have both dimensions specified except for the first dimension if initialized immediately. Here, both dimensions are specified as 4.

2. Step 2: Check initialization format

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; correctly declares a 4x4 int array with nested braces for each row.

3. Final Answer:

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; -> Option A

4. Quick Check:

   Correct 2D array syntax = int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; [OK]

Hint: Use nested braces for each row in 2D array initialization [OK]

Common Mistakes:

• Omitting second dimension size
• Using single braces for all elements
• Declaring incomplete array sizes

3. What will be the output of the following code snippet for the Rat in a Maze problem?

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

int solution[4][4] = {0};

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    solution[x][y] = 0;
    return 0;
  }
  return 0;
}

int main() {
  if (solveMaze(maze, 0, 0, solution)) {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        printf("%d ", solution[i][j]);
      }
      printf("\n");
    }
  } else {
    printf("No path found\n");
  }
  return 0;
}

medium

A. 1 0 0 0
0 1 0 0
0 1 0 0
0 1 1 1

B. 1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

C. No path found

D. 1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

Solution

1. Step 1: Trace the recursive calls

   The function tries to move right (x+1, y) first, then down (x, y+1). It marks path cells in solution matrix if maze cell is 1.

2. Step 2: Follow the path found

   Starting at (0,0), path moves down to (1,0), then right to (1,1), down to (2,1), down to (3,1), right to (3,2), right to (3,3). This path is marked with 1s in solution.

3. Final Answer:

   1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 -> Option D

4. Quick Check:

   Path marked in solution matrix = 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 [OK]

Hint: Trace recursion path marking 1s in solution matrix [OK]

Common Mistakes:

• Confusing row and column indices
• Assuming path includes blocked cells
• Ignoring backtracking step

4. Identify the bug in the following solveMaze function and select the correct fix.

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    return 0;
  }
  return 0;
}

medium

A. Change base case to check (x == 4 && y == 4)

B. Add backtracking step: set solution[x][y] = 0 before returning 0

C. Remove the check maze[x][y] == 1

D. Change recursive calls order to (x, y + 1) then (x + 1, y)

Solution

1. Step 1: Identify missing backtracking

   The function marks solution[x][y] = 1 but does not reset it to 0 if path fails, causing incorrect path marking.

2. Step 2: Fix by adding backtracking

   Before returning 0, set solution[x][y] = 0 to unmark the cell and allow other paths to be explored.

3. Final Answer:

   Add backtracking step: set solution[x][y] = 0 before returning 0 -> Option B

4. Quick Check:

   Backtracking needed to unmark path [OK]

Hint: Always unmark path cell if dead end found [OK]

Common Mistakes:

• Forgetting to unmark solution cell
• Incorrect base case coordinates
• Changing recursion order without reason

5. Given a 5x5 maze where 0 represents blocked cells and 1 represents open cells, how would you modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to end (4,4)?

hard

A. Modify the function to explore all directions and store each valid path in a list

B. Stop recursion after finding the first path and return immediately

C. Use a queue instead of recursion to find one path only

D. Change maze values from 1 to 2 to mark visited cells permanently

Solution

1. Step 1: Understand requirement to find all paths

   Finding all paths means exploring every possible route from start to end without stopping at first success.

2. Step 2: Modify algorithm to explore all directions and store paths

   Change recursion to continue after finding a path, store each valid path in a list or array, and backtrack properly to explore other routes.

3. Final Answer:

   Modify the function to explore all directions and store each valid path in a list -> Option A

4. Quick Check:

   All paths require full exploration [OK]

Hint: Explore all routes and save paths, don't stop at first success [OK]

Common Mistakes:

• Stopping after first path found
• Marking visited cells permanently blocking other paths
• Using BFS without path storage