Rat in a Maze Problem in DSA Go - Execution Trace

Concept Flow - Rat in a Maze Problem

Start at maze[0

↓

Check if current cell is safe

Yes↓

Mark cell as part of path

↓

Try move Down

→If path found

↓

Try move Right

→If path found

↓

Backtrack: Unmark cell

↓

Return False if no moves work

↓

End

The rat starts at the top-left cell and tries to move right or down if the cell is safe, marking the path. If stuck, it backtracks and tries other paths until it reaches the bottom-right cell or exhausts options.

Execution Sample

DSA Go

func solveMaze(maze [][]int, x, y int, path [][]int) bool {
  if x == len(maze)-1 && y == len(maze[0])-1 {
    path[x][y] = 1
    return true
  }
  if isSafe(maze, x, y) {
    path[x][y] = 1
    if solveMaze(maze, x+1, y, path) || solveMaze(maze, x, y+1, path) {
      return true
    }
    path[x][y] = 0
  }
  return false
}

This recursive function tries to find a path from (x,y) to the bottom-right corner by moving right or down if safe, marking the path, and backtracking if needed.

Execution Table

Step	Current 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)	Yes	Mark (2,0), Try Down (3,0) out of bounds, Try Right (2,1)	[[1,0,0],[1,0,0],[1,0,0]]	Pending
4	(2,1)	No (blocked)	Backtrack from (2,0)	[[1,0,0],[1,0,0],[0,0,0]]	False
5	(1,0)	Yes	Try Right (1,1), Mark (1,1)	[[1,0,0],[1,1,0],[0,0,0]]	Pending
6	(1,1)	Yes	Try Down (2,1)	[[1,0,0],[1,1,0],[0,0,0]]	Pending
7	(2,1)	Yes	Mark (2,1), Try Down (3,1) out of bounds, Try Right (2,2)	[[1,0,0],[1,1,0],[0,1,0]]	Pending
8	(2,2)	Yes	Reached goal, Mark (2,2)	[[1,0,0],[1,1,0],[0,1,1]]	True
9	(1,1)	Return True	Path found	[[1,0,0],[1,1,0],[0,1,1]]	True
10	(1,0)	Return True	Path found	[[1,0,0],[1,1,0],[0,1,1]]	True
11	(0,0)	Return True	Path found	[[1,0,0],[1,1,0],[0,1,1]]	True

💡 Reached bottom-right cell (2,2), path found, recursion unwinds returning True

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
x	0	0	1	2	2	1	1	2	2	0
y	0	0	0	0	1	1	1	1	2	0
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],[1,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,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 unmark a cell in the path?

When both right and down moves from a cell fail (see Step 4), we remove the mark to indicate this cell is not part of the correct path, allowing other paths to be explored.

Why do we check if the current cell is safe before moving?

Only safe cells (not blocked) can be part of the path. This check (see Steps 1, 2, 3) prevents moving into walls or outside the maze.

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

When the current position is the bottom-right cell (Step 8), we mark it and return true to indicate success.

Visual Quiz - 3 Questions

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

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

B [[1,0,0],[0,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 at Step 5 in the execution_table

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

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

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

If the cell (2,1) was blocked, what would happen at Step 7?

A The rat would mark (2,1) and continue

B The rat would backtrack from (2,1)

C The rat would try moving left

D The rat would immediately reach the goal

💡 Hint

Refer to Step 4 where a blocked cell causes backtracking

Concept Snapshot

Rat in a Maze Problem:
- Start at top-left cell (0,0)
- Move only right or down if cell is safe (not blocked)
- Mark path cells as part of solution
- Backtrack by unmarking if stuck
- Success when bottom-right cell is reached
- Uses recursion and backtracking to explore paths

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. The algorithm marks the current cell as part of the path and recursively tries to move right or down. If both moves fail, it backtracks by unmarking the cell and tries other paths. This continues until the rat reaches the goal or all paths are exhausted. The execution table shows each step with the current position, safety check, path marking, and backtracking. Variable tracking shows how the position and path matrix change over time. Key moments clarify why backtracking is needed, why safety checks are important, and how the goal is detected. The visual quiz tests understanding of path states, backtracking steps, and blocked cells. The concept snapshot summarizes the approach in simple steps.

Practice

1. What is the main goal of the Rat in a Maze Problem in Data Structures & Algorithms?

easy

A. Calculate the shortest distance between two points in a graph

B. Count the number of walls in the maze

C. Find a path from the start to the destination in a maze

D. Sort the maze cells in ascending order

Solution

1. Step 1: Understand the problem context

   The Rat in a Maze problem involves navigating through a maze represented by a grid to find a path from the start cell to the destination cell.

2. Step 2: Identify the goal

   The goal is to find any valid path that the rat can take to reach the destination without crossing walls or blocked cells.

3. Final Answer:

   Find a path from the start to the destination in a maze -> Option C

4. Quick Check:

   Goal = Find path [OK]

Hint: Remember: Rat must find a path, not count or sort [OK]

Common Mistakes:

• Confusing path finding with counting walls
• Thinking the problem is about shortest path always
• Assuming sorting cells is required

2. Which of the following Go function signatures correctly represents a recursive function to solve the Rat in a Maze problem?

easy

A. func solveMaze(maze [][]int, x, y int) bool

B. func solveMaze(maze []int, x int) int

C. func solveMaze(maze [][]int) string

D. func solveMaze(x, y int) [][]int

Solution

1. Step 1: Analyze function parameters for maze solving

   The function should accept the maze as a 2D slice and current coordinates (x, y) to explore recursively.

2. Step 2: Check return type for success indication

   The function returns a boolean indicating if a path exists from current position to destination.

3. Final Answer:

   func solveMaze(maze [][]int, x, y int) bool -> Option A

4. Quick Check:

   Correct signature = func solveMaze(maze [][]int, x, y int) bool [OK]

Hint: Look for 2D maze and bool return for path found [OK]

Common Mistakes:

• Using 1D slice instead of 2D for maze
• Wrong return type like int or string
• Missing current position parameters

3. What will be the output of the following Go code snippet for a 2x2 maze where all cells are open (1)?

package main
import "fmt"

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        (*path)[x][y] = 1
        return true
    }
    if x >= 0 && y >= 0 && x < n && y < n && maze[x][y] == 1 {
        (*path)[x][y] = 1
        if solveMaze(maze, x+1, y, path) {
            return true
        }
        if solveMaze(maze, x, y+1, path) {
            return true
        }
        (*path)[x][y] = 0
        return false
    }
    return false
}

func main() {
    maze := [][]int{{1,1},{1,1}}
    path := [][]int{{0,0},{0,0}}
    if solveMaze(maze, 0, 0, &path) {
        fmt.Println(path)
    } else {
        fmt.Println("No path found")
    }
}

medium

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

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

C. [[1 1] [1 1]]

D. No path found

Solution

1. Step 1: Trace the recursive calls on 2x2 maze

   Starting at (0,0), mark path[0][0]=1, try moving down (1,0), mark path[1][0]=1, then try moving right (1,1), mark path[1][1]=1 and reach destination.

2. Step 2: Backtrack if needed and finalize path matrix

   Right move from (0,0) to (0,1) is also possible but the code tries down first. The final path marks (0,0), (1,0), and (1,1) as 1, and (0,1) as 0.

3. Final Answer:

   [[1 0] [1 1]] -> Option A

4. Quick Check:

   Path matrix = [[1 0] [1 1]] [OK]

Hint: Follow recursion order: down first, then right [OK]

Common Mistakes:

• Assuming path includes (0,1) first
• Confusing path matrix with maze matrix
• Ignoring backtracking step

4. Identify the bug in this Go code snippet for the Rat in a Maze problem:

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        (*path)[x][y] = 1
        return true
    }
    if x < 0 || y < 0 || x >= n || y >= n || maze[x][y] == 0 {
        return false
    }
    (*path)[x][y] = 1
    if solveMaze(maze, x+1, y, path) || solveMaze(maze, x, y+1, path) {
        return true
    }
    (*path)[x][y] = 0
    return false
}

medium

A. Using pointer for path is unnecessary

B. Missing backtracking step to reset path[x][y] to 0

C. Wrong maze boundary checks

D. Incorrect base case for destination cell

Solution

1. Step 1: Review path marking and backtracking logic

   The code marks path[x][y] = 1 when visiting but never resets it to 0 if path fails, causing incorrect path recording.

2. Step 2: Identify missing backtracking step

   Backtracking requires resetting path[x][y] = 0 before returning false to allow other paths to be explored correctly.

3. Final Answer:

   Missing backtracking step to reset path[x][y] to 0 -> Option B

4. Quick Check:

   Backtracking reset missing = Missing backtracking step to reset path[x][y] to 0 [OK]

Hint: Always reset path on failure to backtrack [OK]

Common Mistakes:

• Forgetting to reset path cell on dead end
• Misplacing base case condition
• Ignoring boundary checks

5. Given a 4x4 maze represented as:

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

Which path matrix will correctly represent a valid path from top-left (0,0) to bottom-right (3,3) using the Rat in a Maze algorithm?

hard

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

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

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

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

Solution

1. Step 1: Trace the valid path through the maze

   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), and right to (3,3).

2. Step 2: Mark path cells as 1 and others as 0

   Mark these cells in the path matrix as 1, others remain 0. This matches [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] exactly.

3. Final Answer:

   [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] -> Option D

4. Quick Check:

   Valid path marked = [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] [OK]

Hint: Follow open cells from start to end marking path [OK]

Common Mistakes:

• Marking blocked cells as path
• Skipping valid moves down or right
• Confusing path matrix with maze layout