Rat in a Maze Problem in DSA Java - Execution Trace

Concept Flow - Rat in a Maze Problem

Start at (0,0)

↓

Check if current cell is safe

Yes↓

Mark cell as path

↓

Try move Down

→If success

No↓

Try move Right

→If success

No↓

Backtrack: Unmark cell

↓

Return false

↓

End or find path

The rat starts at the top-left cell, checks if it can move down or right safely, marks the path, and backtracks if stuck, until it reaches the bottom-right cell.

Execution Sample

DSA Java

boolean solveMaze(int[][] maze, int x, int y, int[][] sol) {
  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 down or right recursively.

Execution Table

Step	Position (x,y)	Is Safe?	Action	Path Matrix State	Result
1	(0,0)	Yes	Mark (0,0) and try down (1,0)	[[1,0,0],[0,0,0],[0,0,0]]	Continue
2	(1,0)	Yes	Mark (1,0) and try down (2,0)	[[1,0,0],[1,0,0],[0,0,0]]	Continue
3	(2,0)	No	Blocked cell, backtrack	[[1,0,0],[1,0,0],[0,0,0]]	Backtrack
4	(1,1)	Yes	Mark (1,1) and try down (2,1)	[[1,0,0],[1,1,0],[0,0,0]]	Continue
5	(2,1)	Yes	Mark (2,1) and try right (2,2)	[[1,0,0],[1,1,0],[0,1,0]]	Continue
6	(2,2)	Yes	Mark (2,2) reached goal	[[1,0,0],[1,1,0],[0,1,1]]	Success

💡 Reached goal at (2,2), path found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	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,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]]

Key Moments - 3 Insights

Why do we mark a cell as part of the path before trying moves?

Marking the cell (see Step 1 and 2 in execution_table) helps track the current path and avoid revisiting the same cell, preventing infinite loops.

What happens when both down and right moves fail?

We backtrack by unmarking the cell (Step 3 shows backtracking), which means removing it from the path and trying other routes.

How do we know when the rat has reached the goal?

When the position is at the bottom-right cell (Step 6), we mark it and return success, ending recursion.

Visual Quiz - 3 Questions

Look at the execution_table, what is the path matrix state after Step 2?

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

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

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

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

💡 Hint

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

At which step does the rat backtrack because it cannot enter the cell?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'Backtrack' in the 'Result' column in execution_table.

If the maze had a blocked cell at (2,1), what would happen at Step 5?

A The rat would backtrack from (1,1).

B The rat would try moving right to (2,2) directly.

C The rat would mark (2,1) anyway and continue.

D The rat would reach the goal immediately.

💡 Hint

Refer to the 'Is Safe?' and 'Action' columns at Step 5 in execution_table.

Concept Snapshot

Rat in a Maze Problem:
- Start at (0,0), goal at (N-1,N-1)
- Move only right or down if safe
- Mark path cells as 1 in solution matrix
- Backtrack by unmarking if stuck
- Recursion ends when goal is reached or no path
- Useful for pathfinding in grids

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 into safe cells (cells with value 1). The algorithm marks the current cell as part of the path and tries moving down first, then right. If both moves fail, it backtracks by unmarking the cell and tries other routes. The process continues recursively until the rat reaches the goal cell or all paths are exhausted. The execution table shows step-by-step how the rat moves, marks the path, backtracks (e.g., at blocked (2,0)), and finally finds the path via (0,0)-(1,0)-(1,1)-(2,1)-(2,2). Variables like position and the solution matrix change as the algorithm progresses. Key moments include marking cells before moving, backtracking when stuck, and recognizing the goal cell. The visual quiz tests understanding of these steps and states.

Practice

1. What is the main goal of the Rat in a Maze Problem in data structures?

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 goal

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

2. Step 2: Identify the correct goal

   Among the options, only finding a path from start to destination matches the problem's main goal.

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: Remember: Rat must find a path through the maze [OK]

Common Mistakes:

• Confusing path finding with counting walls
• Thinking it's about sorting or distances
• Ignoring the start and destination points

2. Which of the following is the correct way to check if a cell (x, y) is safe to move in a maze represented by a 2D array maze in Java?

easy

A. if (x > 0 && y > 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0)

B. if (x > 0 && y > 0 && x <= maze.length && y <= maze[0].length && maze[x][y] == 0)

C. if (x >= 0 && y >= 0 && x <= maze.length && y <= maze[0].length && maze[x][y] == 1)

D. if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1)

Solution

1. Step 1: Check valid indices in 2D array

   Indices must be >= 0 and less than maze.length and maze[0].length to avoid ArrayIndexOutOfBoundsException.

2. Step 2: Check if cell is open (usually 1 means open)

   We check if maze[x][y] == 1 to confirm the cell is safe to move.

3. Final Answer:

   if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1) -> Option D

4. Quick Check:

   Bounds + open cell = if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1) [OK]

Hint: Check indices >=0 and < length, and cell == 1 [OK]

Common Mistakes:

• Using > 0 instead of >= 0 causes skipping first row/column
• Using <= length causes index out of bounds
• Checking for 0 instead of 1 for open path

3. What will be the output path for the following maze if the rat starts at (0,0) and destination is (1,2)?

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

Assuming the rat moves only right or down and marks path cells with 2, what is the maze after the path is found?

medium

A. [[1, 0, 0], [2, 2, 2]]

B. [[2, 0, 0], [2, 2, 2]]

C. [[2, 0, 0], [1, 1, 2]]

D. [[2, 0, 0], [2, 1, 2]]

Solution

1. Step 1: Trace the path from (0,0) to (1,2)

   Start at (0,0) which is 1, move down to (1,0) = 1, then right to (1,1) = 1, then right to (1,2) = 1.

2. Step 2: Mark the path cells with 2

   Mark (0,0), (1,0), (1,1), (1,2) as 2. Other cells remain unchanged.

3. Final Answer:

   [[2, 0, 0], [2, 2, 2]] -> Option B

4. Quick Check:

   Path marked with 2 = [[2, 0, 0], [2, 2, 2]] [OK]

Hint: Follow path down then right, mark visited cells [OK]

Common Mistakes:

• Marking cells not in path
• Confusing 0 and 1 cells
• Not marking start cell

4. Given the following code snippet for the Rat in a Maze problem, what is the error?

boolean solveMaze(int[][] maze, int x, int y, int[][] solution) {
  if (x == maze.length - 1 && y == maze[0].length - 1) {
    solution[x][y] = 1;
    return true;
  }
  if (x < maze.length && y < maze[0].length && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return true;
    if (solveMaze(maze, x, y + 1, solution)) return true;
    solution[x][y] = 0;
    return false;
  }
  return false;
}

medium

A. No base case for destination cell

B. Solution array is not updated correctly

C. Missing check for x and y >= 0 before accessing maze[x][y]

D. Recursive calls do not explore all directions

Solution

1. Step 1: Analyze boundary checks before accessing maze

   The code checks if x < maze.length and y < maze[0].length but does not check if x >= 0 and y >= 0, which can cause ArrayIndexOutOfBoundsException if negative indices occur.

2. Step 2: Verify other parts of the code

   The base case for destination exists, solution array updates correctly, and recursive calls explore down and right directions as expected.

3. Final Answer:

   Missing check for x and y >= 0 before accessing maze[x][y] -> Option C

4. Quick Check:

   Bounds must include >= 0 [OK]

Hint: Always check indices >= 0 and < length before access [OK]

Common Mistakes:

• Ignoring negative index checks
• Assuming base case is missing
• Thinking solution array update is wrong

5. You have a 4x4 maze represented as:

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

If the rat can move in all four directions (up, down, left, right) but cannot visit the same cell twice, which of the following is the correct path the rat can take from (0,0) to (3,3)?

hard

A. [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)]

B. [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)]

C. [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3)]

D. [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)]

Solution

1. Step 1: Trace possible path from (0,0) to (3,3) moving up/down/left/right

   Start at (0,0), move down to (1,0), right to (1,1), down to (2,1), down to (3,1), right to (3,2), right to (3,3). All cells are 1 and not visited twice.

2. Step 2: Verify other options for invalid moves or blocked cells

   [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)] moves to (0,1) which is 0 (blocked). [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3)] moves to (2,0) which is 0. [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)] moves to (1,2) which is 0. So only [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] is valid.

3. Final Answer:

   [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] -> Option A

4. Quick Check:

   Valid path with allowed moves = [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] [OK]

Hint: Check cell value 1 and no repeats in path [OK]

Common Mistakes:

• Choosing paths through blocked cells (0)
• Revisiting same cell twice
• Ignoring allowed movement directions