Rat in a Maze Problem in DSA Java

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 -> 0 -> 1 -> 0
0 -> 1 -> 0 -> 1
0 -> 0 -> 0 -> E

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

Dry Run Walkthrough

Input: maze: 4x4 grid with 0 as open path and 1 as wall Start at top-left (0,0), goal is bottom-right (3,3) Maze: 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0

Goal: Find a path from start (0,0) to end (3,3) moving only right or down through 0s

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

[S] 0 1 0
1 0 1 0
0 0 0 1
0 1 0 0

Why: We begin from the start cell

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

S [0] 1 0
1 0 1 0
0 0 0 1
0 1 0 0

Why: Right cell is open, continue path

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

S 0 1 0
1 0 1 0
0 0 0 1
0 1 0 0

Why: Cannot move into wall, must try other directions

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

S 0 1 0
1 [0] 1 0
0 0 0 1
0 1 0 0

Why: Down cell is open, continue path

Step 5: Move down to (2,1), cell is 0, mark as path

S 0 1 0
1 0 1 0
0 [0] 0 1
0 1 0 0

Why: Continue moving down through open cells

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

S 0 1 0
1 0 1 0
0 0 [0] 1
0 1 0 0

Why: Right cell is open, continue path

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

S 0 1 0
1 0 1 0
0 0 0 1
0 1 0 0

Why: Wall blocks path, must try other directions

Step 8: Move down to (3,2), cell is 0, mark as path

S 0 1 0
1 0 1 0
0 0 0 1
0 1 [0] 0

Why: Down cell is open, continue path

Step 9: Move right to (3,3), cell is 0, mark as path (goal reached)

S 0 1 0
1 0 1 0
0 0 0 1
0 1 0 [E]

Why: Reached the end cell, path found

Result:

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

Annotated Code

DSA Java

public class RatInMaze {
    static int N = 4;

    // Function to print the solution matrix
    static void printSolution(int[][] sol) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(sol[i][j] + " ");
            }
            System.out.println();
        }
    }

    // Check if x,y is valid index for N*N maze
    static boolean isSafe(int[][] maze, int x, int y) {
        return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0);
    }

    // Recursive utility to solve maze problem
    static boolean solveMazeUtil(int[][] maze, int x, int y, int[][] sol) {
        // If (x,y) is goal, mark and return true
        if (x == N - 1 && y == N - 1) {
            sol[x][y] = 1; // mark path
            return true;
        }

        if (isSafe(maze, x, y)) {
            sol[x][y] = 1; // mark path

            // Move right
            if (solveMazeUtil(maze, x, y + 1, sol))
                return true;

            // Move down
            if (solveMazeUtil(maze, x + 1, y, sol))
                return true;

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

        return false;
    }

    // Main solve function
    static boolean solveMaze(int[][] maze) {
        int[][] sol = new int[N][N];

        if (!solveMazeUtil(maze, 0, 0, sol)) {
            System.out.println("No solution");
            return false;
        }

        printSolution(sol);
        return true;
    }

    public static void main(String[] args) {
        int[][] maze = {
            {0, 0, 1, 0},
            {1, 0, 1, 0},
            {0, 0, 0, 1},
            {0, 1, 0, 0}
        };

        solveMaze(maze);
    }
}

if (x == N - 1 && y == N - 1) { sol[x][y] = 1; return true; }

Mark goal cell and stop recursion

if (isSafe(maze, x, y)) { sol[x][y] = 1;

Mark current cell as part of path if safe

if (solveMazeUtil(maze, x, y + 1, sol)) return true;

Try moving right first

if (solveMazeUtil(maze, x + 1, y, sol)) return true;

If right fails, try moving down

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

Unmark cell if no path found from here

Output

1 1 0 0 

0 1 0 0 

0 1 1 0 

0 0 1 1 

Complexity Analysis

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

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

vs Alternative: Compared to BFS which uses a queue, this DFS backtracking uses recursion and can be simpler but may explore more paths

Edge Cases

Empty maze (no cells)

No path exists, function returns false and prints 'No solution'

DSA Java

if (!solveMazeUtil(maze, 0, 0, sol)) { System.out.println("No solution"); return false; }

Start or end cell is blocked (1)

No path possible, returns false and prints 'No solution'

DSA Java

if (!solveMazeUtil(maze, 0, 0, sol)) { System.out.println("No solution"); return false; }

Maze with only one cell open (start=end)

Returns true immediately marking the single cell as path

DSA Java

if (x == N - 1 && y == N - 1) { sol[x][y] = 1; return true; }

When to Use This Pattern

When you see a problem asking to find a path through a grid with obstacles, think of backtracking to explore all possible routes step-by-step.

Common Mistakes

Mistake: Not backtracking (unmarking) cells when a path fails
Fix: Add sol[x][y] = 0 before returning false to undo the path marking

Mistake: Trying to move in invalid directions (like left or up) without checks
Fix: Only move right or down and check boundaries with isSafe function

Summary

Finds a path from start to end in a maze using backtracking.

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

The key is to mark paths and backtrack when hitting dead ends.

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 number of walls 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

   Among the options, only finding a path from start to destination matches the problem's main goal.

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: Remember: Rat must find a path through the maze [OK]

Common Mistakes:

• Confusing path finding with counting walls
• Thinking it's about sorting or distances
• Ignoring the start and destination points

2. Which of the following is the correct way to check if a cell (x, y) is safe to move in a maze represented by a 2D array maze in Java?

easy

A. if (x > 0 && y > 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0)

B. if (x > 0 && y > 0 && x <= maze.length && y <= maze[0].length && maze[x][y] == 0)

C. if (x >= 0 && y >= 0 && x <= maze.length && y <= maze[0].length && maze[x][y] == 1)

D. if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1)

Solution

1. Step 1: Check valid indices in 2D array

   Indices must be >= 0 and less than maze.length and maze[0].length to avoid ArrayIndexOutOfBoundsException.

2. Step 2: Check if cell is open (usually 1 means open)

   We check if maze[x][y] == 1 to confirm the cell is safe to move.

3. Final Answer:

   if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1) -> Option D

4. Quick Check:

   Bounds + open cell = if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1) [OK]

Hint: Check indices >=0 and < length, and cell == 1 [OK]

Common Mistakes:

• Using > 0 instead of >= 0 causes skipping first row/column
• Using <= length causes index out of bounds
• Checking for 0 instead of 1 for open path

3. What will be the output path for the following maze if the rat starts at (0,0) and destination is (1,2)?

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

Assuming the rat moves only right or down and marks path cells with 2, what is the maze after the path is found?

medium

A. [[1, 0, 0], [2, 2, 2]]

B. [[2, 0, 0], [2, 2, 2]]

C. [[2, 0, 0], [1, 1, 2]]

D. [[2, 0, 0], [2, 1, 2]]

Solution

1. Step 1: Trace the path from (0,0) to (1,2)

   Start at (0,0) which is 1, move down to (1,0) = 1, then right to (1,1) = 1, then right to (1,2) = 1.

2. Step 2: Mark the path cells with 2

   Mark (0,0), (1,0), (1,1), (1,2) as 2. Other cells remain unchanged.

3. Final Answer:

   [[2, 0, 0], [2, 2, 2]] -> Option B

4. Quick Check:

   Path marked with 2 = [[2, 0, 0], [2, 2, 2]] [OK]

Hint: Follow path down then right, mark visited cells [OK]

Common Mistakes:

• Marking cells not in path
• Confusing 0 and 1 cells
• Not marking start cell

4. Given the following code snippet for the Rat in a Maze problem, what is the error?

boolean solveMaze(int[][] maze, int x, int y, int[][] solution) {
  if (x == maze.length - 1 && y == maze[0].length - 1) {
    solution[x][y] = 1;
    return true;
  }
  if (x < maze.length && y < maze[0].length && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return true;
    if (solveMaze(maze, x, y + 1, solution)) return true;
    solution[x][y] = 0;
    return false;
  }
  return false;
}

medium

A. No base case for destination cell

B. Solution array is not updated correctly

C. Missing check for x and y >= 0 before accessing maze[x][y]

D. Recursive calls do not explore all directions

Solution

1. Step 1: Analyze boundary checks before accessing maze

   The code checks if x < maze.length and y < maze[0].length but does not check if x >= 0 and y >= 0, which can cause ArrayIndexOutOfBoundsException if negative indices occur.

2. Step 2: Verify other parts of the code

   The base case for destination exists, solution array updates correctly, and recursive calls explore down and right directions as expected.

3. Final Answer:

   Missing check for x and y >= 0 before accessing maze[x][y] -> Option C

4. Quick Check:

   Bounds must include >= 0 [OK]

Hint: Always check indices >= 0 and < length before access [OK]

Common Mistakes:

• Ignoring negative index checks
• Assuming base case is missing
• Thinking solution array update is wrong

5. You have a 4x4 maze represented as:

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

If the rat can move in all four directions (up, down, left, right) but cannot visit the same cell twice, which of the following is the correct path the rat can take from (0,0) to (3,3)?

hard

A. [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)]

B. [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)]

C. [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3)]

D. [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)]

Solution

1. Step 1: Trace possible path from (0,0) to (3,3) moving up/down/left/right

   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), right to (3,3). All cells are 1 and not visited twice.

2. Step 2: Verify other options for invalid moves or blocked cells

   [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)] moves to (0,1) which is 0 (blocked). [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3)] moves to (2,0) which is 0. [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)] moves to (1,2) which is 0. So only [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] is valid.

3. Final Answer:

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

4. Quick Check:

   Valid path with allowed moves = [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] [OK]

Hint: Check cell value 1 and no repeats in path [OK]

Common Mistakes:

• Choosing paths through blocked cells (0)
• Revisiting same cell twice
• Ignoring allowed movement directions