Rat in a Maze Problem in DSA Python

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 moving only through open paths and avoiding walls.

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

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

Dry Run Walkthrough

Input: maze: [[1, 0, 1, 0], [1, 1, 0, 0], [0, 1, 1, 1]], start: (0,0), end: (2,3)

Goal: Find a path from top-left corner (0,0) to bottom-right corner (2,3) moving only on 1s

Step 1: Start at (0,0), mark as part of path

Path: (0,0)
Maze:
[1, 0, 1, 0]
[1, 1, 0, 0]
[0, 1, 1, 1]

Why: We begin from the start cell which is open

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

Path: (0,0)
Maze unchanged

Why: Cell (0,1) is blocked, so we cannot move there

Step 3: Try moving down to (1,0), open, move and mark path

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

Why: Down cell is open, so we move forward

Step 4: From (1,0), try right to (1,1), open, move and mark path

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

Why: Right cell is open, continue path

Step 5: From (1,1), try right to (1,2), blocked (0), backtrack

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

Why: Blocked cell, cannot proceed

Step 6: From (1,1), try down to (2,1), open, move and mark path

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

Why: Down cell is open, continue path

Step 7: From (2,1), try right to (2,2), open, move and mark path

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

Why: Right cell is open, continue path

Step 8: From (2,2), try right to (2,3), open and is end, path found

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

Why: Reached the destination cell

Result:

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

Annotated Code

DSA Python

from typing import List, Tuple

class RatInMaze:
    def __init__(self, maze: List[List[int]]):
        self.maze = maze
        self.n = len(maze)
        self.m = len(maze[0]) if self.n > 0 else 0
        self.path = []

    def is_safe(self, x: int, y: int) -> bool:
        return 0 <= x < self.n and 0 <= y < self.m and self.maze[x][y] == 1

    def solve_maze(self, x: int, y: int, end: Tuple[int, int]) -> bool:
        if (x, y) == end:
            self.path.append((x, y))
            return True

        if self.is_safe(x, y):
            self.path.append((x, y))
            # Move right
            if self.solve_maze(x, y + 1, end):
                return True
            # Move down
            if self.solve_maze(x + 1, y, end):
                return True
            self.path.pop()  # backtrack
        return False


def main():
    maze = [
        [1, 0, 1, 0],
        [1, 1, 0, 0],
        [0, 1, 1, 1]
    ]
    start = (0, 0)
    end = (2, 3)
    rat = RatInMaze(maze)
    if rat.solve_maze(start[0], start[1], end):
        print("Path found:")
        print(" -> ".join(f"({x},{y})" for x, y in rat.path))
    else:
        print("No path found")

if __name__ == "__main__":
    main()

if (x, y) == end:

Check if current cell is the destination

if self.is_safe(x, y):

Check if current cell is open and inside maze

self.path.append((x, y))

Add current cell to path

if self.solve_maze(x, y + 1, end):

Try moving right recursively

if self.solve_maze(x + 1, y, end):

Try moving down recursively

self.path.pop() # backtrack

Remove cell from path if no way forward

Output

Path found:

(0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2) -> (2,3)

Complexity Analysis

Time: O(2^(n*m)) because in worst case we explore all paths in the grid

Space: O(n*m) for recursion stack and path storage in worst case

vs Alternative: Compared to BFS which finds shortest path, this DFS approach finds one path but may explore more nodes

Edge Cases

Empty maze

No path found because there are no cells

DSA Python

if self.is_safe(x, y):

Start or end cell blocked

No path found because start or end is not open

DSA Python

if self.is_safe(x, y):

Maze with no possible path

Backtracking leads to no solution and returns false

DSA Python

self.path.pop()  # backtrack

When to Use This Pattern

When you need to find a path through a grid with obstacles, use backtracking to explore possible routes step-by-step.

Common Mistakes

Mistake: Not backtracking properly by forgetting to remove the cell from path when dead end is reached
Fix: Use path.pop() to remove the last cell when no further moves are possible

Mistake: Trying to move outside the maze boundaries
Fix: Check boundaries with is_safe before moving

Summary

Finds a path from start to end in a grid maze by moving 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 and backtrack when 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 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