Rat in a Maze Problem in DSA Python - 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

↓

Check if destination reached

↓

Return True

↓

Try moving Right

↓

Backtrack if no path

↓

Return False if no moves

The rat starts at the top-left cell and tries to move right or down if the cell is safe, marking the path. If it reaches the destination, it returns success; otherwise, it backtracks.

Execution Sample

DSA Python

def solve_maze(maze, x, y, path):
    if is_safe(maze, x, y):
        path[x][y] = 1
        if x == len(maze) - 1 and y == len(maze[0]) - 1:
            return True
        if solve_maze(maze, x + 1, y, path):
            return True
        if solve_maze(maze, x, y + 1, path):
            return True
        path[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.

Execution Table

Step	Position (x,y)	Is Safe?	Action	Path Matrix State	Return Value
1	(0,0)	Yes	Mark (0,0), Try Down (1,0)	[[1,0,0],[0,0,0],[0,0,0]]	Pending
2	(1,0)	Yes	Mark (1,0), Try Down (2,0)	[[1,0,0],[1,0,0],[0,0,0]]	Pending
3	(2,0)	No	Backtrack (2,0)	[[1,0,0],[1,0,0],[0,0,0]]	False
4	(1,0)	Back at (1,0)	Try Right (1,1)	[[1,0,0],[1,0,0],[0,0,0]]	Pending
5	(1,1)	Yes	Mark (1,1), Try Down (2,1)	[[1,0,0],[1,1,0],[0,0,0]]	Pending
6	(2,1)	Yes	Mark (2,1), Try Down (3,1) - Out of bounds	[[1,0,0],[1,1,0],[0,1,0]]	Pending
7	(2,2)	Yes	Mark (2,2), Destination reached	[[1,0,0],[1,1,0],[0,1,1]]	True
8	(1,1)	Return True	Propagate success	[[1,0,0],[1,1,0],[0,1,1]]	True
9	(1,0)	Return True	Propagate success	[[1,0,0],[1,1,0],[0,1,1]]	True
10	(0,0)	Return True	Propagate success	[[1,0,0],[1,1,0],[0,1,1]]	True

💡 Reached destination at (2,2), returned True and propagated success back to start.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 7	Final
x	0	1	2	1	2	2
y	0	0	0	1	2	2
path	[[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,1]]	[[1,0,0],[1,1,0],[0,1,1]]

Key Moments - 3 Insights

Why do we backtrack and set path[x][y] = 0?

When both right and down moves fail from a cell (see Step 3), we remove that cell from the path to try other routes. This is shown in the execution_table where path is reset before returning False.

How do we know when the destination is reached?

At Step 7, when x and y equal the bottom-right cell coordinates, we mark it and return True immediately, signaling success.

Why do we try moving down before moving right?

The code tries moving down first (Step 1 to Step 3), then right if down fails (Step 4 onwards). This order affects the path found and is visible in the execution_table.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

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

At which step does the algorithm backtrack from position (2,0)?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'Backtrack (2,0)' action in the execution_table.

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

A It would be [[1,0,0],[0,0,0],[0,0,0]]

B It would be [[1,0,0],[1,0,0],[0,0,0]]

C It would be [[1,0,0],[1,1,0],[0,0,0]]

D It would be [[1,0,0],[1,1,1],[0,0,1]]

💡 Hint

If (1,1) is blocked, it won't be marked as 1; check variable_tracker for path states.

Concept Snapshot

Rat in a Maze Problem:
- Start at top-left (0,0).
- Move only right or down if cell is safe.
- Mark path cells with 1.
- If destination reached, return True.
- If stuck, backtrack by unmarking cell.
- Recursion explores all paths until success or failure.

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 uses recursion to try moving down first, then right. It marks the current cell as part of the path. If it reaches the destination, it returns True. If it hits a dead end, it backtracks by unmarking the cell and tries other paths. The execution table shows each step's position, safety check, action, path state, and return value. Variable tracking shows how the position and path matrix change over time. Key moments clarify why backtracking happens, how destination is detected, and the order of moves. The visual quiz tests understanding of path states and backtracking steps. This approach helps visualize how recursion and backtracking work together to solve the maze.

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 objective

   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

   The goal is to find a valid path through open cells, avoiding obstacles, not just counting walls or distances.

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 measuring [OK]

Common Mistakes:

• Confusing pathfinding with counting obstacles
• Thinking the problem is about shortest path always
• Assuming the maze is always square

2. Which of the following is the correct way to check if the rat can move to cell (x, y) in Python?

easy

A. if x >= 0 and y >= 0 and maze[x][y] == 1:

B. if maze[x][y] == 1 and x >= 0 and y >= 0:

C. if maze[x][y] == 1 or x >= 0 or y >= 0:

D. if maze[x][y] != 1 and x > 0 and y > 0:

Solution

1. Step 1: Check boundary conditions first

   We must first ensure x and y are within valid indices (>= 0) before accessing maze[x][y] to avoid errors.

2. Step 2: Check if the cell is open (value 1)

   After confirming indices, check if maze[x][y] == 1 to confirm the cell is open for movement.

3. Final Answer:

   if x >= 0 and y >= 0 and maze[x][y] == 1: -> Option A

4. Quick Check:

   Check bounds before access [OK]

Hint: Check indices before accessing maze to avoid errors [OK]

Common Mistakes:

• Checking maze[x][y] before verifying indices
• Using 'or' instead of 'and' in conditions
• Checking for maze[x][y] != 1 instead of == 1

3. What will be the output of the following code snippet for the given maze?

maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 1, 0, 0],
  [1, 1, 1, 1]
]

solution = [[0]*4 for _ in range(4)]

def solve_maze(x, y):
    if x == 3 and y == 3:
        solution[x][y] = 1
        return True
    if 0 <= x < 4 and 0 <= y < 4 and maze[x][y] == 1:
        solution[x][y] = 1
        if solve_maze(x + 1, y):
            return True
        if solve_maze(x, y + 1):
            return True
        solution[x][y] = 0
        return False
    return False

solve_maze(0, 0)
print(solution)

medium

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

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

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

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

Solution

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

   The function tries moving down first, then right. It marks cells in solution as 1 when moving forward and backtracks by resetting to 0 if dead end.

2. Step 2: Follow the path and update solution matrix

   Path found is (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3). These cells are marked 1 in solution.

3. Final Answer:

   [[1, 0, 0, 0], [1, 1, 0, 0], [0, 1, 0, 0], [0, 1, 1, 1]] -> Option C

4. Quick Check:

   Path marked correctly in solution [OK]

Hint: Follow recursion path and mark visited cells [OK]

Common Mistakes:

• Confusing backtracking reset steps
• Assuming right move tried before down
• Not marking the destination cell

4. Identify the error in the following code snippet for solving the Rat in a Maze problem:

def solve_maze(x, y):
    if x == len(maze) - 1 and y == len(maze[0]) - 1:
        solution[x][y] = 1
        return True
    if x >= 0 and y >= 0 and maze[x][y] == 1:
        solution[x][y] = 1
        if solve_maze(x + 1, y):
            return True
        if solve_maze(x, y + 1):
            return True
        solution[x][y] = 0
        return False
    return False

medium

A. The function does not backtrack properly

B. The boundary check misses upper limits for x and y

C. The base case does not mark the destination cell

D. The maze is not checked for obstacles

Solution

1. Step 1: Analyze boundary checks in the condition

   The condition 'if x >= 0 and y >= 0 and maze[x][y] == 1' misses checking if x and y are less than maze size, risking index errors.

2. Step 2: Confirm base case and backtracking correctness

   The base case marks destination cell and returns True. Backtracking resets solution[x][y] to 0 correctly. Maze obstacles are checked.

3. Final Answer:

   The boundary check misses upper limits for x and y -> Option B

4. Quick Check:

   Check both lower and upper bounds [OK]

Hint: Always check both lower and upper bounds for indices [OK]

Common Mistakes:

• Forgetting to check upper bounds causes errors
• Assuming base case is wrong when it is correct
• Ignoring backtracking step

5. Given a maze represented by a 2D list where 1 means open path and 0 means blocked, how would you modify the standard Rat in a Maze backtracking algorithm to find all possible paths from start to destination instead of just one?

hard

A. Return True immediately after finding the first path

B. Use a queue instead of recursion to find paths

C. Stop recursion when a path is found

D. Store each valid path in a list and continue searching after backtracking

Solution

1. Step 1: Understand standard algorithm behavior

   The standard algorithm returns True immediately after finding the first path, stopping further search.

2. Step 2: Modify to find all paths

   Instead of returning True immediately, store the current path in a list and continue exploring other paths by backtracking to find all possible routes.

3. Final Answer:

   Store each valid path in a list and continue searching after backtracking -> Option D

4. Quick Check:

   Collect all paths by continuing search [OK]

Hint: Collect paths and backtrack fully to find all [OK]

Common Mistakes:

• Stopping after first path found
• Not storing paths properly
• Confusing BFS queue with backtracking recursion