Rat in a Maze Problem in DSA Go

Mental Model

Find a path from start to end in a grid by moving step-by-step through allowed cells.

Analogy: Imagine a rat trying to find cheese in a maze by walking only through open paths and avoiding walls.

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

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

Dry Run Walkthrough

Input: maze: [[0,0,1],[0,0,1],[1,0,0]], start at top-left (0,0), end at bottom-right (2,2)

Goal: Find one path from start to end moving only through 0s (open cells) going right or down

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

[S*] -> 0 1
0 -> 0 1
1 -> 0 E

Why: We begin exploring from the start cell

Step 2: Move right to (0,1), cell is open, mark as path

[S*] -> [*] 1
0 -> 0 1
1 -> 0 E

Why: Try moving right first as allowed direction

Step 3: Try moving right to (0,2), cell is wall (1), backtrack

[S*] -> [*] 1
0 -> 0 1
1 -> 0 E

Why: Cannot move into walls, so backtrack to previous cell

Step 4: Move down from (0,1) to (1,1), cell open, mark as path

[S*] -> [*] 1
0 -> [*] 1
1 -> 0 E

Why: Try moving down after right fails

Step 5: Move down from (1,1) to (2,1), cell open, mark as path

[S*] -> [*] 1
0 -> [*] 1
1 -> [*] E

Why: Continue moving down towards end

Step 6: Move right from (2,1) to (2,2), cell open and is end, mark as path

[S*] -> [*] 1
0 -> [*] 1
1 -> [*] [E*]

Why: Reached the end cell successfully

Result:

[S*] -> [*] 1
0 -> [*] 1
1 -> [*] [E*]

Path found from start to end

Annotated Code

DSA Go

package main

import "fmt"

func isSafe(maze [][]int, x, y int) bool {
    n := len(maze)
    return x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 0
}

func solveMazeUtil(maze [][]int, x, y int, sol [][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 && maze[x][y] == 0 {
        sol[x][y] = 1 // mark end cell
        return true
    }
    if isSafe(maze, x, y) {
        if sol[x][y] == 1 {
            return false // already visited
        }
        sol[x][y] = 1 // mark current cell as part of path

        if solveMazeUtil(maze, x, y+1, sol) { // move right
            return true
        }
        if solveMazeUtil(maze, x+1, y, sol) { // move down
            return true
        }

        sol[x][y] = 0 // backtrack
        return false
    }
    return false
}

func solveMaze(maze [][]int) [][]int {
    n := len(maze)
    sol := make([][]int, n)
    for i := range sol {
        sol[i] = make([]int, n)
    }
    if solveMazeUtil(maze, 0, 0, sol) {
        return sol
    }
    return nil
}

func printSolution(sol [][]int) {
    if sol == nil {
        fmt.Println("No path found")
        return
    }
    for i := 0; i < len(sol); i++ {
        for j := 0; j < len(sol); j++ {
            if sol[i][j] == 1 {
                fmt.Print("*")
            } else {
                fmt.Print(" ")
            }
        }
        fmt.Println()
    }
}

func main() {
    maze := [][]int{
        {0, 0, 1},
        {0, 0, 1},
        {1, 0, 0},
    }
    sol := solveMaze(maze)
    printSolution(sol)
}

if x == n-1 && y == n-1 && maze[x][y] == 0 {

check if current cell is the end and open

sol[x][y] = 1 // mark current cell as part of path

mark current cell as part of the solution path

if solveMazeUtil(maze, x, y+1, sol) { // move right

try moving right recursively

if solveMazeUtil(maze, x+1, y, sol) { // move down

try moving down recursively

sol[x][y] = 0 // backtrack

remove current cell from path if no way forward

Output

**

 **

  **

Complexity Analysis

Time: O(2^(n*n)) because in worst case we explore all cells with two choices each

Space: O(n*n) for the solution matrix and recursion stack

vs Alternative: Compared to BFS which uses a queue and finds shortest path, this DFS approach finds one path but can be slower

Edge Cases

Empty maze (0x0)

Returns no path found immediately

DSA Go

if solveMazeUtil(maze, 0, 0, sol) {

Start or end cell blocked

No path found because start or end is not open

DSA Go

if x == n-1 && y == n-1 && maze[x][y] == 0 {

Maze with no possible path

Backtracks fully and returns no path

DSA Go

sol[x][y] = 0 // backtrack

When to Use This Pattern

When you see a grid and need to find a path from one point to another moving stepwise through allowed cells, use backtracking to explore all possible paths.

Common Mistakes

Mistake: Not marking visited cells causing infinite loops
Fix: Mark cells as part of path before recursive calls and unmark on backtrack

Mistake: Trying to move outside maze boundaries
Fix: Check boundaries before moving using isSafe function

Summary

Finds a path through a maze grid from start to end by moving right or down through open cells.

Use when you need to explore all possible paths in a grid with obstacles to find a valid route.

The key is to mark your path and backtrack when hitting dead ends to explore other options.

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