Rat in a Maze Problem in DSA C# - Execution Trace

Concept Flow - Rat in a Maze Problem

Start at (0,0)

↓

Check if current cell is safe

Yes↓

Mark cell as path

↓

Move Right

→Move Down

↓

If move leads to solution

Yes→Return True

No↓

Backtrack: Unmark cell

↓

Return False if no moves work

↓

End: Solution found or no path

The rat starts at the top-left cell and tries to move in four directions if the cell is safe. It marks the path and backtracks if stuck, until it finds the exit or exhausts all options.

Execution Sample

DSA C#

bool SolveMaze(int[,] maze, int x, int y, int n, int[,] sol) {
  if (x == n-1 && y == n-1) { sol[x,y] = 1; return true; }
  if (IsSafe(maze, x, y, n)) {
    sol[x,y] = 1;
    if (SolveMaze(maze, x+1, y, n, sol)) return true;
    if (SolveMaze(maze, x, y+1, n, sol)) return true;
    sol[x,y] = 0;
  }
  return false;
}

This code tries to find a path from top-left to bottom-right in a maze by moving right or down recursively, marking the path in sol.

Execution Table

Step	Position (x,y)	IsSafe?	Action	Path Marked	Next Move	Backtrack
1	(0,0)	Yes	Mark path	sol[0,0]=1	Move Right to (1,0)	No
2	(1,0)	Yes	Mark path	sol[1,0]=1	Move Right to (2,0)	No
3	(2,0)	No	Cannot move here	No	Backtrack	Yes, sol[1,0]=0
4	(1,0)	Yes	Try Move Down to (1,1)	sol[1,0]=1	Move Down to (1,1)	No
5	(1,1)	Yes	Mark path	sol[1,1]=1	Move Right to (2,1)	No
6	(2,1)	Yes	Mark path	sol[2,1]=1	Move Right to (3,1)	No
7	(3,1)	No	Cannot move here	No	Backtrack	Yes, sol[2,1]=0
8	(2,1)	Yes	Try Move Down to (2,2)	sol[2,1]=1	Move Down to (2,2)	No
9	(2,2)	Yes	Mark path	sol[2,2]=1	Reached Exit	No
10	Exit	N/A	Return True	Path found	N/A	N/A

💡 Reached bottom-right cell (2,2), path found

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
x	0	1	2	1	1	2	3	2	2	2	2
y	0	0	0	0	1	1	1	1	2	2	2
sol[0,0]	0	1	1	1	1	1	1	1	1	1	1
sol[1,0]	0	0	1	0	1	1	1	0	0	0	0
sol[1,1]	0	0	0	0	0	1	1	1	1	1	1
sol[2,1]	0	0	0	0	0	0	1	0	1	1	1
sol[2,2]	0	0	0	0	0	0	0	0	0	1	1

Key Moments - 3 Insights

Why do we backtrack and unmark a cell in the path?

When a move leads to a dead end (see Step 3 and Step 7 in execution_table), we unmark the cell to try other paths. This prevents wrong paths from being considered part of the solution.

Why do we check if the cell is safe before moving?

Checking if the cell is safe (Step 1, Step 2, etc.) ensures we only move to cells inside the maze and not blocked by obstacles. This avoids invalid moves and infinite loops.

Why does the algorithm only move right or down in this example?

To keep it simple, this example tries right and down moves first. The concept can be extended to all four directions, but right/down is enough to find a path in many mazes.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of sol[1,0] after Step 3?

A 1

B 0

C Undefined

D 2

💡 Hint

Check the Backtrack column at Step 3 where sol[1,0] is unmarked.

At which step does the rat reach the exit cell?

A Step 9

B Step 7

C Step 5

D Step 10

💡 Hint

Look at the Position and Action columns for when the exit is reached.

If the maze had no obstacles, how would the path marking change?

A More backtracking steps would appear

B The rat would never mark any cell

C The rat would mark a direct path without backtracking

D The rat would move randomly

💡 Hint

Refer to variable_tracker and execution_table to see how obstacles cause backtracking.

Concept Snapshot

Rat in a Maze Problem:
- Start at top-left cell (0,0)
- Move to safe adjacent cells (right/down or all 4 directions)
- Mark path in solution matrix
- Backtrack if stuck by unmarking
- Stop when bottom-right cell is reached
- Recursive DFS approach with 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 grid. The rat can move only to safe cells that are inside the maze and not blocked. The algorithm marks the current cell as part of the path and tries moving right or down recursively. If a move leads to a dead end, it backtracks by unmarking the cell and tries other directions. This continues until the rat reaches the exit or all paths are exhausted. The execution table shows each step with position, safety check, action, path marking, next move, and backtracking. The variable tracker shows how the position and solution matrix change over time. Key moments clarify why backtracking and safety checks are important. The visual quiz tests understanding of path marking and exit detection. This approach uses recursion and backtracking to explore all possible paths systematically.

Practice

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

easy

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

B. Count the number of walls in the maze

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

D. Fill the maze with obstacles

Solution

1. Step 1: Understand the problem statement

   The Rat in a Maze problem requires finding a path from the start point (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 as 1) avoiding blocked cells (marked as 0).

3. Final Answer:

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

4. Quick Check:

   Goal = Find path [OK]

Hint: Focus on pathfinding from start to end in the maze [OK]

Common Mistakes:

• Thinking it's about counting walls
• Confusing with shortest path calculation
• Assuming the maze needs to be filled

2. Which of the following C# method signatures is correct for a recursive function solving the Rat in a Maze problem?

easy

A. bool SolveMaze(int[,] maze, int x, int y, int[,] solution)

B. void SolveMaze(int maze[][], int x, int y, int solution[][])

C. int SolveMaze(List<int> maze, int x, int y, List<int> solution)

D. bool SolveMaze(int maze[], int x, int y, int solution[])

Solution

1. Step 1: Check parameter types for maze and solution

   In C#, 2D arrays are declared as int[,]. Options A, B, and D use incorrect types like jagged arrays or lists without proper syntax.

2. Step 2: Check return type and parameters

   The recursive function should return bool to indicate success or failure, matching bool SolveMaze(int[,] maze, int x, int y, int[,] solution).

3. Final Answer:

   bool SolveMaze(int[,] maze, int x, int y, int[,] solution) -> Option A

4. Quick Check:

   Correct signature uses int[,] and bool return [OK]

Hint: Use int[,] for 2D arrays and bool return for success [OK]

Common Mistakes:

• Using jagged arrays without proper syntax
• Using List<int> instead of arrays
• Wrong return type for recursion

3. What will be the output of the following code snippet for a 2x2 maze where all cells are open (1)?

int[,] maze = { {1, 1}, {1, 1} };
int[,] solution = new int[2,2];
bool result = SolveMaze(maze, 0, 0, solution);
if (result) {
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      Console.Write(solution[i,j] + " ");
    }
    Console.WriteLine();
  }
} else {
  Console.WriteLine("No path found");
}

medium

A. 1 0
1 1

B. 1 1
0 1

C. No path found

D. 1 1
1 1

Solution

1. Step 1: Understand the maze and solution initialization

   The maze is 2x2 with all cells open (1). The solution array is initially all zeros.

2. Step 2: Trace the SolveMaze function

   The rat starts at (0,0), marks it as 1 in solution, moves right to (0,1), marks it as 1, then moves down to (1,1) which is the destination. The path is (0,0) -> (0,1) -> (1,1). The cell (1,0) remains 0.

3. Final Answer:

   1 1 0 1 -> Option B

4. Quick Check:

   Path marks correct cells as 1 [OK]

Hint: Trace path step-by-step marking solution cells [OK]

Common Mistakes:

• Assuming all cells in solution become 1
• Confusing row and column indices
• Printing 'No path found' incorrectly

4. Identify the error in this snippet of the Rat in a Maze recursive function:

bool SolveMaze(int[,] maze, int x, int y, int[,] solution) {
  if (x == maze.GetLength(0) || y == maze.GetLength(1)) return false;
  if (maze[x, y] == 0) return false;
  solution[x, y] = 1;
  if (x == maze.GetLength(0) - 1 && y == maze.GetLength(1) - 1) return true;
  if (SolveMaze(maze, x + 1, y, solution)) return true;
  if (SolveMaze(maze, x, y + 1, solution)) return true;
  solution[x, y] = 0;
  return false;
}

medium

A. Base case for destination is missing

B. Solution array is not updated correctly

C. Boundary check uses '==' instead of '>=' causing out-of-bounds error

D. Recursive calls do not explore all directions

Solution

1. Step 1: Analyze boundary condition

   The condition if (x == maze.GetLength(0) || y == maze.GetLength(1)) only checks equality, but if x or y exceed bounds, it causes out-of-range errors. It should use '>=' to prevent this.

2. Step 2: Check other parts

   Solution array updates and base case are correct. Recursive calls explore right and down directions properly.

3. Final Answer:

   Boundary check uses '==' instead of '>=' causing out-of-bounds error -> Option C

4. Quick Check:

   Boundary check must prevent index overflow [OK]

Hint: Use '>=' for boundary checks to avoid index errors [OK]

Common Mistakes:

• Using '==' instead of '>=' in boundary checks
• Forgetting to reset solution cell on backtrack
• Missing base case for destination

5. Given a 4x4 maze represented as below, which path will the rat take if it always tries to move right first, then down?

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

Choose the correct solution matrix after the rat finds a path.

hard

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

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

C. 1 0 0 0
1 1 0 0
0 0 0 0
1 1 1 1

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

Solution

1. Step 1: Trace the rat's moves trying right first, then down

   Start at (0,0), mark 1, right (0,1)=0 blocked, down (1,0)=1 mark 1. From (1,0), right (1,1)=1 mark 1. From (1,1), right (1,2)=0 blocked, down (2,1)=1 mark 1. From (2,1), right (2,2)=0 blocked, down (3,1)=1 mark 1. From (3,1), right (3,2)=1 mark 1. From (3,2), right (3,3)=1 mark 1, destination.

2. Step 2: Mark the path in solution matrix

   Cells marked 1 are (0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3). Others remain 0.

3. Final Answer:

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

4. Quick Check:

   Right-first path marks correct cells [OK]

Hint: Simulate moves right then down marking path [OK]

Common Mistakes:

• Marking blocked cells as path
• Incorrect backtracking
• Confusing row and column indices