Rat in a Maze Problem in DSA C#

Mental Model

Find a path from start to finish in a grid by moving step-by-step through allowed cells.

Analogy: Imagine a rat trying to find cheese in a maze by walking only through open paths and avoiding walls.

S -> 0 -> 1 -> 0
1 -> 0 -> 1 -> 0
0 -> 0 -> 0 -> 0
1 -> 1 -> 1 -> E

S = Start, E = End, 0 = open path, 1 = wall

Dry Run Walkthrough

Input: maze: 4x4 grid with 0 as open path and 1 as wall start at top-left (0,0), end at bottom-right (3,3) maze = [[0, 0, 1, 0], [1, 0, 1, 0], [0, 0, 0, 0], [1, 1, 1, 0]]

Goal: Find one path from start (0,0) to end (3,3) moving only right or down through 0s

Step 1: Start at (0,0), mark path

Path: (0,0)
Maze:
S(0,0) -> 0 -> 1 -> 0
1 -> 0 -> 1 -> 0
0 -> 0 -> 0 -> 0
1 -> 1 -> 1 -> E(3,3)

Why: We begin from the start cell to explore possible paths

Step 2: Move right to (0,1), mark path

Path: (0,0) -> (0,1)
Maze:
S -> P -> 1 -> 0
1 -> 0 -> 1 -> 0
0 -> 0 -> 0 -> 0
1 -> 1 -> 1 -> E

Why: Right cell is open (0), so we move forward

Step 3: Try moving right to (0,2), blocked by wall (1), backtrack

Path: (0,0) -> (0,1)
Maze unchanged

Why: Cannot move into wall, so we try other directions

Step 4: Move down to (1,1), mark path

Path: (0,0) -> (0,1) -> (1,1)
Maze:
S -> P -> 1 -> 0
1 -> P -> 1 -> 0
0 -> 0 -> 0 -> 0
1 -> 1 -> 1 -> E

Why: Down cell is open, so we continue exploring

Step 5: Try moving right to (1,2), blocked by wall (1), backtrack

Path: (0,0) -> (0,1) -> (1,1)
Maze unchanged

Why: Wall blocks path, so try other moves

Step 6: Move down to (2,1), mark path

Path: (0,0) -> (0,1) -> (1,1) -> (2,1)
Maze:
S -> P -> 1 -> 0
1 -> P -> 1 -> 0
0 -> P -> 0 -> 0
1 -> 1 -> 1 -> E

Why: Down cell is open, continue path

Step 7: Move right to (2,2), mark path

Path: (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)
Maze:
S -> P -> 1 -> 0
1 -> P -> 1 -> 0
0 -> P -> P -> 0
1 -> 1 -> 1 -> E

Why: Right cell is open, proceed

Step 8: Move right to (2,3), mark path

Path: (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) -> (2,3)
Maze:
S -> P -> 1 -> 0
1 -> P -> 1 -> 0
0 -> P -> P -> P
1 -> 1 -> 1 -> E

Why: Right cell is open, continue

Step 9: Move down to (3,3), mark path and reach end

Path: (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) -> (2,3) -> (3,3)
Maze:
S -> P -> 1 -> 0
1 -> P -> 1 -> 0
0 -> P -> P -> P
1 -> 1 -> 1 -> E

Why: Reached destination, path found

Result:

Path found:
(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) -> (2,3) -> (3,3)

Annotated Code

DSA C#

using System;

class RatInMaze
{
    static int N = 4;

    static bool IsSafe(int[,] maze, int x, int y)
    {
        return (x >= 0 && x < N && y >= 0 && y < N && maze[x, y] == 0);
    }

    static bool SolveMazeUtil(int[,] maze, int x, int y, int[,] sol)
    {
        if (x == N - 1 && y == N - 1 && maze[x, y] == 0)
        {
            sol[x, y] = 1; // mark destination
            return true;
        }

        if (IsSafe(maze, x, y))
        {
            if (sol[x, y] == 1) // already visited
                return false;

            sol[x, y] = 1; // mark current cell

            if (SolveMazeUtil(maze, x, y + 1, sol)) // move right
                return true;

            if (SolveMazeUtil(maze, x + 1, y, sol)) // move down
                return true;

            sol[x, y] = 0; // backtrack
            return false;
        }

        return false;
    }

    static void PrintSolution(int[,] sol)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                Console.Write(sol[i, j] + " ");
            Console.WriteLine();
        }
    }

    public static void Main()
    {
        int[,] maze = {
            {0, 0, 1, 0},
            {1, 0, 1, 0},
            {0, 0, 0, 0},
            {1, 1, 1, 0}
        };

        int[,] sol = new int[N, N];

        if (SolveMazeUtil(maze, 0, 0, sol))
        {
            Console.WriteLine("Path found:");
            PrintSolution(sol);
        }
        else
        {
            Console.WriteLine("No path found");
        }
    }
}

if (x == N - 1 && y == N - 1 && maze[x, y] == 0)

check if reached destination cell

if (IsSafe(maze, x, y))

check if current cell is valid and open

if (sol[x, y] == 1) return false;

avoid revisiting same cell to prevent loops

sol[x, y] = 1;

mark current cell as part of path

if (SolveMazeUtil(maze, x, y + 1, sol)) return true;

try moving right recursively

if (SolveMazeUtil(maze, x + 1, y, sol)) return true;

try moving down recursively

sol[x, y] = 0;

backtrack if no path found from current cell

Output

Path found:

1 1 0 0 

0 1 0 0 

0 1 1 1 

0 0 0 1 

Complexity Analysis

Time: O(2^(N*N)) because in worst case each cell can lead to two moves (right and down) and we explore all paths

Space: O(N*N) for the solution matrix and recursion stack in worst case

vs Alternative: Compared to BFS which uses a queue and can find shortest path, this DFS backtracking explores all paths and may be slower but simpler to implement

Edge Cases

Empty maze (all walls)

No path found, function returns false

DSA C#

if (IsSafe(maze, x, y))

Start or end cell blocked

No path found immediately

DSA C#

if (x == N - 1 && y == N - 1 && maze[x, y] == 0)

Single cell maze open

Path found immediately

DSA C#

if (x == N - 1 && y == N - 1 && maze[x, y] == 0)

When to Use This Pattern

When you see a grid with blocked and open cells and need to find a path from start to end, use backtracking to explore possible routes step-by-step.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops
Fix: Mark cells as part of path before recursion and unmark on backtrack

Mistake: Trying to move outside grid boundaries
Fix: Check boundaries before moving using IsSafe function

Summary

Finds a path through a maze grid from start to end by moving only through open cells.

Use when you need to explore all possible paths in a grid with obstacles.

The key is to try moves step-by-step, mark path, and backtrack if stuck.

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