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 part of path

↓

Try move Down

→If path found

↓

Try move Right

→If path found

↓

Backtrack: Unmark cell

↓

Return False

↓

End: Path found or no path

The rat starts at the top-left cell and tries to move right or down 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[N][N], int x, int y, int sol[N][N]) {
  if (x == N-1 && y == N-1) {
    sol[x][y] = 1;
    return true;
  }
  if (isSafe(maze, x, y)) {
    sol[x][y] = 1;
    if (solveMaze(maze, x+1, y, sol)) return true;
    if (solveMaze(maze, x, y+1, 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 and backtracking if needed.

Execution Table

Step	Position (x,y)	Is Safe?	Action	Path Matrix State
1	(0,0)	Yes	Mark (0,0) and move down	[[1,0,0],[0,0,0],[0,0,0]]
2	(1,0)	Yes	Mark (1,0) and move down	[[1,0,0],[1,0,0],[0,0,0]]
3	(2,0)	No	Backtrack from (2,0)	[[1,0,0],[1,0,0],[0,0,0]]
4	(1,0)	Yes	Try move right	[[1,0,0],[1,0,0],[0,0,0]]
5	(1,1)	Yes	Mark (1,1) and move down	[[1,0,0],[1,1,0],[0,0,0]]
6	(2,1)	Yes	Mark (2,1) and move down	[[1,0,0],[1,1,0],[0,1,0]]
7	(3,1)	Out of bounds	Backtrack from (3,1)	[[1,0,0],[1,1,0],[0,1,0]]
8	(2,1)	Yes	Try move right	[[1,0,0],[1,1,0],[0,1,0]]
9	(2,2)	Yes	Mark (2,2) - Exit found	[[1,0,0],[1,1,0],[0,1,1]]
10	Return True	-	Path found	[[1,0,0],[1,1,0],[0,1,1]]

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

Variable Tracker

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

Key Moments - 3 Insights

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

When both moving right and down from a cell fail to find the exit, we unmark that cell to indicate it is not part of the correct path. This is shown in Step 3 and Step 7 where the path matrix remains unchanged after backtracking.

Why do we check if the cell is safe before marking it?

We only mark cells that are within bounds and not blocked. This prevents invalid moves. For example, at Step 3, (2,0) is not safe, so we backtrack without marking.

How does the recursion know when the exit is found?

When the current position is the bottom-right cell, the function returns true immediately, marking the exit. This happens at Step 9, ending the recursion.

Visual Quiz - 3 Questions

Look at the execution table, what is the path matrix state after Step 5?

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

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

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

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

💡 Hint

Check the 'Path Matrix State' column at Step 5 in the execution_table.

At which step does the algorithm backtrack from an unsafe cell?

A Step 2

B Step 3

C Step 5

D Step 9

💡 Hint

Look for 'Backtrack from (2,0)' and 'Is Safe?' marked as No in the execution_table.

If the maze had a blocked cell at (1,1), how would the path matrix change at Step 5?

A It would backtrack and not mark (1,1)

B It would mark (1,1) anyway

C It would skip Step 5 and move directly to Step 6

D It would mark (2,1) instead

💡 Hint

Refer to the 'Is Safe?' check before marking cells in the execution_table.

Concept Snapshot

Rat in a Maze Problem:
- Start at (0,0), try moving right or down.
- Mark safe cells as part of path.
- Backtrack if no path forward.
- Stop when bottom-right cell is reached.
- Uses recursion and backtracking to find path.

Full Transcript

The Rat in a Maze problem involves finding a path from the top-left corner to the bottom-right corner of a grid maze. The rat can move only right or down. The algorithm checks if the current cell is safe (inside maze and not blocked). If safe, it marks the cell as part of the path and tries moving right or down recursively. If both moves fail, it backtracks by unmarking the cell. The process continues until the exit is found or all paths are exhausted. The execution table shows each step with position, safety check, action taken, and the current path matrix state. Key moments include understanding backtracking, safety checks, and recognizing the exit condition. The visual quiz tests understanding of path marking, backtracking steps, and how blocked cells affect the path. The concept snapshot summarizes the approach in simple steps.

Practice

1. What is the main goal of the Rat in a Maze Problem in Data Structures & Algorithms?

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 graph

D. Sort the maze cells in ascending order

Solution

1. Step 1: Understand the problem context

   The Rat in a Maze problem involves navigating a maze represented by a grid to find a path from the start cell to the destination cell.

2. Step 2: Identify the main objective

   The main objective is to find a valid path through open cells (usually marked as 1) from the start to the end point.

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, not counting or sorting [OK]

Common Mistakes:

• Confusing pathfinding with counting walls
• Thinking it's about sorting cells
• Assuming it's about shortest distance always

2. Which of the following is the correct way to declare a 2D maze array of size 4x4 in C++?

easy

A. int maze[4][4];

B. int maze(4,4);

C. int maze[4,4];

D. int maze{4,4};

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, a 2D array is declared using square brackets for each dimension, like int maze[4][4];.

2. Step 2: Analyze each option

   int maze[4][4]; uses correct syntax. int maze(4,4); uses parentheses which is invalid for arrays. int maze[4,4]; uses comma inside brackets which is incorrect. int maze{4,4}; uses braces which is invalid for declaration.

3. Final Answer:

   int maze[4][4]; -> Option A

4. Quick Check:

   2D array = int maze[4][4]; [OK]

Hint: Use square brackets for array dimensions [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using commas inside brackets
• Using braces for declaration

3. Consider the following C++ code snippet for a 2x2 maze where 1 means open path and 0 means blocked:

int maze[2][2] = {{1, 0}, {1, 1}};
bool solveMaze(int maze[2][2], int x, int y) {
  if (x == 1 && y == 1) return true;
  if (x < 0 || y < 0 || x >= 2 || y >= 2 || maze[x][y] == 0) return false;
  if (solveMaze(maze, x + 1, y)) return true;
  if (solveMaze(maze, x, y + 1)) return true;
  return false;
}
int main() {
  bool result = solveMaze(maze, 0, 0);
  std::cout << (result ? "Path Found" : "No Path") << std::endl;
  return 0;
}

What will be the output when this program runs?

medium

A. Runtime Error

B. No Path

C. Compilation Error

D. Path Found

Solution

1. Step 1: Trace the recursive calls starting at (0,0)

   At (0,0), maze[0][0] = 1 (open). Try moving down to (1,0): maze[1][0] = 1 (open). From (1,0), try moving down to (2,0) invalid, then right to (1,1): maze[1][1] = 1 (open) and is destination.

2. Step 2: Confirm path existence

   Since (1,1) is reached, function returns true and prints "Path Found".

3. Final Answer:

   Path Found -> Option D

4. Quick Check:

   Valid path exists = Path Found [OK]

Hint: Follow recursion down and right moves [OK]

Common Mistakes:

• Ignoring boundary checks
• Assuming no path due to blocked cell
• Confusing indices order

4. The following code snippet is intended to solve the Rat in a Maze problem but has a bug:

bool solveMaze(int maze[3][3], int x, int y) {
  if (x == 2 && y == 2) return true;
  if (x > 2 || y > 2 || maze[x][y] == 0) return false;
  if (solveMaze(maze, x + 1, y)) return true;
  if (solveMaze(maze, x, y + 1)) return true;
  return false;
}

What is the bug in this code?

medium

A. Missing check for negative indices

B. No check for maze boundaries less than zero

C. No check for visited cells causing infinite recursion

D. Incorrect base case coordinates

Solution

1. Step 1: Analyze boundary and base case checks

   The code checks if x or y are greater than 2 and if the cell is blocked. It returns true if destination (2,2) is reached.

2. Step 2: Identify missing visited check

   There is no mechanism to mark visited cells, so the recursion can revisit the same cells repeatedly, causing infinite recursion or stack overflow.

3. Final Answer:

   No check for visited cells causing infinite recursion -> Option C

4. Quick Check:

   Visited check missing = Infinite recursion [OK]

Hint: Always mark visited cells to avoid loops [OK]

Common Mistakes:

• Ignoring visited cells check
• Assuming boundary checks cover all cases
• Confusing base case with boundary

5. Given a 4x4 maze represented as:

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

Write a function to find one path from (0,0) to (3,3) moving only right or down. Which of the following describes the correct approach?

hard

A. Use depth-first search but only move left and up

B. Use backtracking to explore right and down moves, marking visited cells to avoid cycles

C. Use breadth-first search without marking visited cells

D. Use a greedy approach always moving right first without backtracking

Solution

1. Step 1: Understand movement constraints and maze structure

   The rat can move only right or down. The maze has blocked cells (0) and open cells (1). We need to find a path from top-left to bottom-right.

2. Step 2: Choose correct algorithm approach

   Backtracking explores all possible paths by moving right or down, marking visited cells to avoid revisiting and infinite loops. Greedy or BFS without visited checks can fail or loop.

3. Final Answer:

   Use backtracking to explore right and down moves, marking visited cells to avoid cycles -> Option B

4. Quick Check:

   Backtracking + visited = Correct approach [OK]

Hint: Backtrack with visited marks for safe pathfinding [OK]

Common Mistakes:

• Using greedy without backtracking
• Ignoring visited cells causing loops
• Moving in wrong directions