Rat in a Maze Problem in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rat Path in a Simple Maze

What is the output path of the rat in the maze after running the code below? The rat starts at top-left (0,0) and tries to reach bottom-right (2,2). 1 means open path, 0 means blocked.

DSA Python

def rat_in_maze(maze):
    n = len(maze)
    path = [[0]*n for _ in range(n)]
    def solve(x, y):
        if x == n-1 and y == n-1 and maze[x][y] == 1:
            path[x][y] = 1
            return True
        if 0 <= x < n and 0 <= y < n and maze[x][y] == 1:
            if path[x][y] == 1:
                return False
            path[x][y] = 1
            if solve(x+1, y):
                return True
            if solve(x, y+1):
                return True
            path[x][y] = 0
            return False
        return False
    if solve(0, 0):
        return path
    else:
        return []

maze = [
    [1, 0, 0],
    [1, 1, 0],
    [0, 1, 1]
]
result = rat_in_maze(maze)
print(result)

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

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

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

D []

💡 Hint

Trace the path from top-left to bottom-right moving only down or right on cells with 1.

The rat moves down from (0,0) to (1,0), then right to (1,1), then down to (2,1), and finally right to (2,2). The path matrix marks these cells with 1.

🧠 Conceptual

intermediate

Understanding Rat Movement Constraints

In the Rat in a Maze problem, which of the following movement rules is typically allowed for the rat to find a path?

A The rat can jump over blocked cells.

B The rat can move up, down, left, or right.

C The rat can move diagonally only.

D The rat can move only down or right.

💡 Hint

Think about the simplest movement rules to keep the problem solvable.

Typically, the rat moves only down or right to simplify the problem and avoid cycles.

🔧 Debug

advanced

Identify the Bug in Maze Pathfinding Code

What error will the following code produce when run? The maze is a 2x2 grid with all open paths.

DSA Python

def rat_in_maze(maze):
    n = len(maze)
    path = [[0]*n for _ in range(n)]
    def solve(x, y):
        if x == n-1 and y == n-1 and maze[x][y] == 1:
            path[x][y] = 1
            return True
        if 0 <= x < n and 0 <= y < n and maze[x][y] == 1:
            if path[x][y] == 1:
                return False
            path[x][y] = 1
            if solve(x+1, y):
                return True
            if solve(x, y+1):
                return True
            path[x][y] = 0
            return False
        return False
    if solve(0, 0):
        return path
    else:
        return []

maze = [
    [1, 1],
    [1, 1]
]
result = rat_in_maze(maze)
print(result)

A RecursionError due to infinite recursion

B IndexError due to out of range access

C TypeError due to wrong data type

D No error, outputs [[1, 1], [0, 1]]

💡 Hint

Check if the code prevents revisiting the same cell properly.

The code does not prevent revisiting cells correctly, causing infinite recursion and stack overflow.

🚀 Application

advanced

Number of Paths in a Maze with Obstacles

Given a 3x3 maze with some blocked cells (0) and open cells (1), how many unique paths exist from top-left to bottom-right moving only down or right?

DSA Python

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

# Count paths function not shown

A 2

B 3

C 4

D 1

💡 Hint

Count all possible ways moving down or right avoiding blocked cells.

There are exactly 2 unique paths avoiding blocked cells in this maze.

❓ Predict Output

expert

Output of Rat Path with Backtracking and Multiple Paths

What is the output path matrix after running the code below? The rat tries to find one path from top-left to bottom-right in a 4x4 maze.

DSA Python

def rat_in_maze(maze):
    n = len(maze)
    path = [[0]*n for _ in range(n)]
    def solve(x, y):
        if x == n-1 and y == n-1 and maze[x][y] == 1:
            path[x][y] = 1
            return True
        if 0 <= x < n and 0 <= y < n and maze[x][y] == 1:
            if path[x][y] == 1:
                return False
            path[x][y] = 1
            if solve(x+1, y):
                return True
            if solve(x, y+1):
                return True
            if solve(x-1, y):
                return True
            if solve(x, y-1):
                return True
            path[x][y] = 0
            return False
        return False
    if solve(0, 0):
        return path
    else:
        return []

maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
]
result = rat_in_maze(maze)
print(result)

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

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

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

D []

💡 Hint

The rat can move back and forth but must find a valid path marking visited cells.

The rat finds a path going down, right, down, and then right to reach the end. The path matrix marks these cells with 1.

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