Rat in a Maze Problem in DSA Java - Build from Scratch

Rat in a Maze Problem

📖 Scenario: Imagine a small rat trapped in a maze represented by a grid. The rat wants to find a path from the top-left corner to the bottom-right corner by moving only through open cells.

🎯 Goal: You will help the rat find a path through the maze using a simple algorithm. The maze is a 2D grid where 1 means open path and 0 means blocked path. You will create the maze, set up a helper variable, write the logic to find the path, and finally print the path found.

📋 What You'll Learn

Create a 2D integer array called maze with the exact values given

Create a 2D integer array called solution of the same size as maze initialized with zeros

Write a recursive function solveMaze that finds a path from the top-left to bottom-right

Print the solution array showing the path with 1s

💡 Why This Matters

🌍 Real World

Maze solving algorithms are used in robotics for pathfinding and navigation in unknown environments.

💼 Career

Understanding recursion and backtracking is essential for software engineers working on algorithms, game development, and AI.

1

Create the maze grid

Create a 2D integer array called maze with these exact values: {{1, 0, 0, 0}, {1, 1, 0, 1}, {0, 1, 0, 0}, {1, 1, 1, 1}}

DSA Java

# Create the maze array
// Your code here

Hint

Use int[][] maze = { ... }; to create the 2D array with the exact rows and values.

2

Create the solution grid

Create a 2D integer array called solution of size 4x4 initialized with zeros inside the main method after maze

DSA Java

public class RatInMaze {
    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };
        // Create the solution array here
        // Your code here
    }
}

Hint

Use new int[4][4] to create a 4 by 4 array filled with zeros.

3

Write the recursive solver function

Write a static method solveMaze that takes maze, solution, x, and y as parameters and returns boolean. It should check if the rat can move right or down and mark the path in solution with 1s. Use recursion to find the path from (0,0) to (3,3).

DSA Java

public class RatInMaze {
    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };
        int[][] solution = new int[4][4];
        // Your code here
    }
    // Write solveMaze method here
}

Hint

Use recursion to try moving right (x+1, y) and down (x, y+1). Mark the path in solution with 1s. Backtrack if no path found.

4

Print the solution path

Add code inside main to print the solution 2D array after calling solveMaze. Print each row on a new line with spaces between numbers.

DSA Java

public class RatInMaze {
    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };
        int[][] solution = new int[4][4];
        if (solveMaze(maze, solution, 0, 0)) {
            // Print the solution array here
            // Your code here
        } else {
            System.out.println("No path found");
        }
    }

    public static boolean solveMaze(int[][] maze, int[][] solution, int x, int y) {
        int N = maze.length;
        if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {
            solution[x][y] = 1;
            return true;
        }
        if (x >= 0 && x = 0 && y < N && maze[x][y] == 1) {
            if (solution[x][y] == 1) {
                return false; // already visited
            }
            solution[x][y] = 1;
            if (solveMaze(maze, solution, x + 1, y)) {
                return true;
            }
            if (solveMaze(maze, solution, x, y + 1)) {
                return true;
            }
            solution[x][y] = 0; // backtrack
            return false;
        }
        return false;
    }
}

Hint

Use nested for loops to print each element of solution with spaces, and print a new line after each row.

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