Rat in a Maze Problem in DSA Javascript

Mental Model

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

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

S 0 1
0 0 1
1 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 paths)

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), it is open, mark as path

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

Why: Try moving right first as possible path

Step 3: Try moving right to (0,2), blocked by wall (1), backtrack

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

Why: Cannot move through walls, so backtrack

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

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

Why: Try moving down after right blocked

Step 5: Try moving right to (1,2), blocked by wall (1), backtrack

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

Why: Cannot move through walls, so backtrack

Step 6: Move down to (2,1), open, mark as path

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

Why: Try moving down to continue path

Step 7: Move right to (2,2), end found, mark as path

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

Why: Reached the destination

Result:

[S] [0] 1
0 [0] 1
1 [0] [E]
Path found from start to end

Annotated Code

DSA Javascript

class MazeSolver {
  constructor(maze) {
    this.maze = maze;
    this.n = maze.length;
    this.path = Array.from({ length: this.n }, () => Array(this.n).fill(0));
  }

  isSafe(x, y) {
    return x >= 0 && y >= 0 && x < this.n && y < this.n && this.maze[x][y] === 0;
  }

  solve() {
    if (this.solveUtil(0, 0)) {
      this.printPath();
    } else {
      console.log('No path found');
    }
  }

  solveUtil(x, y) {
    if (x === this.n - 1 && y === this.n - 1 && this.maze[x][y] === 0) {
      this.path[x][y] = 1; // mark end
      return true;
    }

    if (this.isSafe(x, y)) {
      if (this.path[x][y] === 1) return false; // already visited

      this.path[x][y] = 1; // mark current cell

      // Move right
      if (this.solveUtil(x, y + 1)) return true;

      // Move down
      if (this.solveUtil(x + 1, y)) return true;

      // Backtrack
      this.path[x][y] = 0;
      return false;
    }
    return false;
  }

  printPath() {
    for (let i = 0; i < this.n; i++) {
      let row = '';
      for (let j = 0; j < this.n; j++) {
        row += this.path[i][j] === 1 ? '[1] ' : '[0] ';
      }
      console.log(row.trim());
    }
  }
}

const maze = [
  [0, 0, 1],
  [0, 0, 1],
  [1, 0, 0]
];

const solver = new MazeSolver(maze);
solver.solve();

if (x === this.n - 1 && y === this.n - 1 && this.maze[x][y] === 0) {

Check if current cell is the destination and open

if (this.isSafe(x, y)) {

Check if current cell is within bounds and open

if (this.path[x][y] === 1) return false;

Avoid revisiting cells to prevent loops

this.path[x][y] = 1;

Mark current cell as part of the path

if (this.solveUtil(x, y + 1)) return true;

Try moving right recursively

if (this.solveUtil(x + 1, y)) return true;

Try moving down recursively

this.path[x][y] = 0;

Backtrack: unmark cell if no path found ahead

Output

[1] [1] [0]

[0] [1] [0]

[0] [1] [1]

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 path matrix and recursion stack

vs Alternative: Compared to brute force checking all paths without marking visited, this approach avoids cycles and is more efficient but still exponential

Edge Cases

Empty maze (no cells)

No path found, handled by boundary checks

DSA Javascript

if (this.isSafe(x, y)) {

Start or end cell blocked

No path found, returns false immediately

DSA Javascript

if (x === this.n - 1 && y === this.n - 1 && this.maze[x][y] === 0) {

Maze with no possible path

Backtracks fully and prints 'No path found'

DSA Javascript

return false;

When to Use This Pattern

When you see a grid with blocked and open cells and need to find a path from one corner to another, use backtracking to explore possible routes step-by-step.

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 from start to end by moving only through open cells.

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

The key is to try moves step-by-step, mark your path, and backtrack if stuck.

Practice

1. What is the main goal of the Rat in a Maze problem in 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 objective

   The Rat in a Maze problem requires finding a path from the start cell to the destination cell in a maze grid.

2. Step 2: Identify the correct goal

   The goal is not counting walls, sorting cells, or shortest distance in a graph, but specifically finding a valid path through the maze.

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: Focus on pathfinding from start to end in the maze [OK]

Common Mistakes:

• Confusing pathfinding with counting or sorting
• Thinking it's about shortest path always
• Assuming maze cells need sorting

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 JavaScript?

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] === 1)

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] === 0)

Solution

1. Step 1: Check boundary conditions correctly

   Valid indices in JavaScript arrays start at 0 and go up to length - 1, so conditions must use >= 0 and < length.

2. Step 2: Check cell value for path

   In the Rat in a Maze problem, 1 usually means path is open, so maze[x][y] === 1 is correct.

3. Final Answer:

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

4. Quick Check:

   Boundary + path check = if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) [OK]

Hint: Use >= 0 and < length for array bounds, check for 1 as path [OK]

Common Mistakes:

• Using > 0 excludes index 0
• Using <= length causes out-of-bound errors
• Checking for 0 instead of 1 as path

3. What will be the output of the following JavaScript code snippet for the Rat in a Maze problem?

const maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 1, 0, 0],
  [1, 1, 1, 1]
];

function solveMaze(x, y, maze, path) {
  if (x === maze.length - 1 && y === maze[0].length - 1) {
    path.push([x, y]);
    return true;
  }
  if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) {
    path.push([x, y]);
    maze[x][y] = 0;
    if (solveMaze(x + 1, y, maze, path)) return true;
    if (solveMaze(x, y + 1, maze, path)) return true;
    path.pop();
    return false;
  }
  return false;
}

const path = [];
solveMaze(0, 0, maze, path);
console.log(path);

medium

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

B. []

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

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

Solution

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

   Starting at (0,0), the function tries moving down (x+1,y) first, then right (x,y+1). It marks visited cells as 0 to avoid revisiting.

2. Step 2: Follow the path found

   The path found is (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3), which is a valid path to the destination.

3. Final Answer:

   [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]] -> Option D

4. Quick Check:

   Path traced matches [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]] [OK]

Hint: Follow down moves first, then right moves recursively [OK]

Common Mistakes:

• Assuming right moves tried before down
• Not marking visited cells causing infinite loops
• Misreading maze cell values

4. Identify the bug in the following JavaScript code snippet for the Rat in a Maze problem and select the fix.

function solveMaze(x, y, maze, path) {
  if (x === maze.length - 1 && y === maze[0].length - 1) {
    path.push([x, y]);
    return true;
  }
  if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) {
    path.push([x, y]);
    if (solveMaze(x + 1, y, maze, path)) return true;
    if (solveMaze(x, y + 1, maze, path)) return true;
    path.pop();
    return false;
  }
  return false;
}

medium

A. Mark visited cells as 0 after pushing to path to avoid revisiting

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

C. Change base case to check if x > maze.length and y > maze[0].length

D. Add a check to move diagonally (x+1, y+1) in recursion

Solution

1. Step 1: Identify missing visited marking

   The code does not mark visited cells as 0, so it may revisit the same cell causing infinite recursion.

2. Step 2: Fix by marking visited cells

   After pushing a cell to path, mark maze[x][y] = 0 to avoid revisiting and infinite loops.

3. Final Answer:

   Mark visited cells as 0 after pushing to path to avoid revisiting -> Option A

4. Quick Check:

   Visited marking fixes infinite recursion [OK]

Hint: Mark visited cells to prevent infinite loops [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Removing path.pop() causing wrong paths
• Changing base case incorrectly

5. Given a maze represented by a 2D array where 1 means open path and 0 means blocked, how would you modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to destination (n-1,n-1)?

hard

A. Use backtracking to explore all directions and store each complete path in a list

B. Stop recursion after finding the first path and return it immediately

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

D. Mark all visited cells permanently to avoid revisiting any cell

Solution

1. Step 1: Understand the requirement to find all paths

   Finding all paths means exploring every possible route from start to destination without stopping at the first success.

2. Step 2: Use backtracking to explore all paths

   Backtracking allows exploring all directions, storing each valid path, and backtracking to try other routes.

3. Final Answer:

   Use backtracking to explore all directions and store each complete path in a list -> Option A

4. Quick Check:

   All paths require full backtracking exploration [OK]

Hint: Backtrack fully and save each path to find all solutions [OK]

Common Mistakes:

• Stopping after first path found
• Using BFS only for shortest path
• Marking visited cells permanently blocking other paths