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

↓

Recurse

↓

Recurse

↓

If at destination

↓

Print path and return

↓

Backtrack if no moves

↓

End

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

Execution Sample

DSA Rust

fn is_safe(maze: &Vec<Vec<i32>>, x: usize, y: usize) -> bool {
    x < maze.len() && y < maze[0].len() && maze[x][y] == 1
}

fn solve_maze(maze: &Vec<Vec<i32>>, x: usize, y: usize, path: &mut Vec<Vec<i32>>) -> bool {
    if x == maze.len() - 1 && y == maze[0].len() - 1 {
        path[x][y] = 1;
        return true;
    }
    if is_safe(maze, x, y) {
        path[x][y] = 1;
        if solve_maze(maze, x + 1, y, path) || solve_maze(maze, x, y + 1, path) {
            return true;
        }
        path[x][y] = 0;
    }
    false
}

This function tries to find a path from top-left to bottom-right in the maze by moving right or down recursively.

Execution Table

Step	Position (x,y)	Is Safe?	Action	Path Matrix State
1	(0,0)	Yes	Mark path[0][0]=1, Try Right (1,0)	[[1,0,0],[0,0,0],[0,0,0]]
2	(1,0)	Yes	Mark path[1][0]=1, Try Right (2,0)	[[1,0,0],[1,0,0],[0,0,0]]
3	(2,0)	No	Backtrack path[2][0]=0	[[1,0,0],[1,0,0],[0,0,0]]
4	(1,0)	Back to (1,0)	Try Down (1,1)	[[1,0,0],[1,0,0],[0,0,0]]
5	(1,1)	Yes	Mark path[1][1]=1, Try Right (2,1)	[[1,0,0],[1,1,0],[0,0,0]]
6	(2,1)	Yes	Mark path[2][1]=1, Try Right (3,1) out of bounds, Try Down (2,2)	[[1,0,0],[1,1,0],[0,1,0]]
7	(2,2)	Yes	Mark path[2][2]=1, Destination reached	[[1,0,0],[1,1,0],[0,1,1]]
8	Return True	-	Path found, unwind recursion	[[1,0,0],[1,1,0],[0,1,1]]

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 6	After Step 7	Final
x	0	1	2	Back to 1	1	2	2	2
y	0	0	0	Back to 0	1	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,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 set path[x][y] back to 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 execution_table row 3 where path[2][0] is reset to 0.

How do we know when the destination is reached?

At Step 7, when position is (2,2) which is the bottom-right cell, we mark it and return true to stop further recursion, as shown in execution_table row 7.

Why do we try moving right before moving down?

The code tries moving right first (see Step 1 and 2) to explore that path. If it fails, it tries moving down (Step 4 and 5). 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],[0,0,0],[0,0,0]]

B [[1,0,0],[1,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 in execution_table row 5.

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

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look for 'Backtrack' action in execution_table rows.

If the maze had no safe cell at (1,1), what would happen in the execution?

A The path would include (1,1) anyway

B The algorithm would backtrack earlier and try other paths

C The algorithm would stop immediately at start

D The destination would be reached faster

💡 Hint

Consider how 'Is Safe?' affects path marking and backtracking in execution_table.

Concept Snapshot

Rat in a Maze Problem:
- Start at top-left cell (0,0).
- Move only right or down if cell is safe (1).
- Mark path cells as 1 in path matrix.
- Use recursion to explore moves.
- Backtrack by unmarking if stuck.
- Stop when destination (bottom-right) is reached.

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 marked as 1. The algorithm uses recursion to try moving right first, then down. If a move is not safe or leads to a dead end, it backtracks by unmarking the path cell. When the destination is reached, the path is printed. The execution table shows each step with position, safety check, action taken, and the current path matrix state. Variables x and y track the current position, and path tracks the cells included in the path. Key moments include understanding backtracking, recognizing the destination, and the order of moves. The visual quiz tests understanding of path states, backtracking steps, and behavior when cells are unsafe.

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 total number of cells 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

   The goal is not counting cells, sorting, or shortest distance but finding a valid path through allowed cells.

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 cells
• Thinking it finds shortest path always
• Mixing it with sorting or graph distance problems

2. Which of the following Rust function signatures is correct for a recursive function solving the Rat in a Maze problem?

easy

A. fn solve_maze(maze: Vec<i32>, x: usize, y: usize) -> Vec<(usize, usize)>

B. fn solve_maze(maze: Vec, x: i32, y: i32) -> i32

C. fn solve_maze(maze: &mut Vec<i32>, x: usize, y: usize) -> bool

D. fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool

Solution

1. Step 1: Check parameter types for maze and coordinates

   The maze is a 2D grid, so it should be a reference to a vector of vectors of integers (&Vec). Coordinates are usize for indexing.

2. Step 2: Check return type and path parameter

   The function returns bool to indicate success and uses a mutable path vector to store the route.

3. Final Answer:

   fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool -> Option D

4. Quick Check:

   Correct signature uses references and bool return [OK]

Hint: Use references for maze and bool return for success [OK]

Common Mistakes:

• Passing maze by value causing unnecessary copying
• Using wrong coordinate types (i32 instead of usize)
• Returning wrong types like i32 or Vec instead of bool

3. Given the following Rust code snippet for Rat in a Maze, what will be printed?

fn main() {
    let maze = vec![
        vec![1, 0, 0, 0],
        vec![1, 1, 0, 1],
        vec![0, 1, 0, 0],
        vec![1, 1, 1, 1],
    ];
    let mut path = Vec::new();
    if solve_maze(&maze, 0, 0, &mut path) {
        println!("Path found: {:?}", path);
    } else {
        println!("No path found");
    }
}

fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool {
    let n = maze.len();
    if x == n - 1 && y == n - 1 {
        path.push((x, y));
        return true;
    }
    if x < n && y < n && maze[x][y] == 1 {
        path.push((x, y));
        if x + 1 < n && solve_maze(maze, x + 1, y, path) {
            return true;
        }
        if y + 1 < n && solve_maze(maze, x, y + 1, path) {
            return true;
        }
        path.pop();
    }
    false
}

medium

A. Path found: [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]

B. Path found: [(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]

C. No path found

D. Path found: [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]

Solution

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

   Start at (0,0) which is 1 (allowed). Try moving down to (1,0) which is 1, then (2,0) is 0 (blocked), so backtrack. Then try right from (1,0) to (1,1) which is 1.

2. Step 2: Continue path to destination

   From (1,1), down to (2,1) is 1, then down to (3,1) is 1, right to (3,2) is 1, and right to (3,3) is 1 (destination). Path is [(0,0),(1,0),(1,1),(2,1),(3,1),(3,2),(3,3)].

3. Final Answer:

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

4. Quick Check:

   Recursive path = Path found: [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)] [OK]

Hint: Follow down then right moves recursively [OK]

Common Mistakes:

• Assuming path goes right first instead of down
• Not backtracking correctly on blocked cells
• Confusing coordinates order in path

4. Identify the bug in this Rust code snippet for Rat in a Maze and select the fix:

fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool {
    let n = maze.len();
    if x == n - 1 && y == n - 1 {
        path.push((x, y));
        return true;
    }
    if x < n && y < n && maze[x][y] == 1 {
        path.push((x, y));
        if solve_maze(maze, x + 1, y, path) {
            return true;
        }
        if solve_maze(maze, x, y + 1, path) {
            return true;
        }
        path.pop();
    }
    false
}

medium

A. Change maze parameter to mutable reference

B. Remove path.pop() to keep all visited cells

C. Add boundary checks before recursive calls to avoid out-of-bounds

D. Return i32 instead of bool for success

Solution

1. Step 1: Analyze recursive calls for boundary safety

   The recursive calls use x+1 and y+1 without checking if they exceed maze size, risking out-of-bounds panic.

2. Step 2: Fix by adding boundary checks before recursion

   Adding checks like x + 1 < n and y + 1 < n before calling solve_maze prevents invalid indexing.

3. Final Answer:

   Add boundary checks before recursive calls to avoid out-of-bounds -> Option C

4. Quick Check:

   Boundary checks prevent panic [OK]

Hint: Always check indices before recursive calls [OK]

Common Mistakes:

• Ignoring index bounds causing runtime panic
• Changing maze to mutable unnecessarily
• Removing path.pop() causing wrong paths

5. You want to modify the Rat in a Maze solution in Rust to find all possible paths from start to finish instead of just one. Which approach is best?

hard

A. Use a queue to perform breadth-first search and return the shortest path only

B. Return a vector of paths and explore all possible moves recursively without stopping at first success

C. Stop recursion as soon as one path is found to save time

D. Modify the maze to mark visited cells permanently to avoid revisiting

Solution

1. Step 1: Understand requirement to find all paths

   Finding all paths means exploring every possible route without stopping at the first success.

2. Step 2: Use recursion to explore all moves and collect paths

   Return a vector of paths and do not return early. Backtrack properly to explore all options.

3. Final Answer:

   Return a vector of paths and explore all possible moves recursively without stopping at first success -> Option B

4. Quick Check:

   Explore all paths recursively [OK]

Hint: Collect all paths, don't stop at first success [OK]

Common Mistakes:

• Stopping recursion early losing other paths
• Using BFS only for shortest path, not all paths
• Marking visited permanently blocking other paths