Rat in a Maze Problem in DSA Javascript - Execution Trace

Concept Flow - Rat in a Maze Problem

Start at (0,0)

↓

Check if current cell is safe

Yes↓

Mark cell as part of path

↓

Try move Right

→If success

No↓

Try move Down

→If success

No↓

Backtrack: Unmark cell

↓

Return False

↓

End or continue search

The rat starts at the top-left cell, checks if it can move right or down safely, marks the path, backtracks if stuck, and continues until it reaches the bottom-right cell.

Execution Sample

DSA Javascript

function solveMaze(maze) {
  const n = maze.length;
  const path = Array.from({ length: n }, () => Array(n).fill(0));
  function solve(x, y) {
    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] === 0) {
      path[x][y] = 1;
      if (solve(x, y + 1)) return true;
      if (solve(x + 1, y)) return true;
      path[x][y] = 0;
      return false;
    }
    return false;
  }
  if (solve(0, 0)) return path;
  else return [];
}

This code tries to find a path from top-left to bottom-right in a maze by moving right or down recursively, marking the path, and backtracking if needed.

Execution Table

Step	Position (x,y)	Is Safe?	Action	Path Matrix State
1	(0,0)	Yes	Mark (0,0), Try Right (0,1)	[[1,0,0],[0,0,0],[0,0,0]]
2	(0,1)	Yes	Mark (0,1), Try Right (0,2)	[[1,1,0],[0,0,0],[0,0,0]]
3	(0,2)	No	Backtrack	[[1,1,0],[0,0,0],[0,0,0]]
4	(0,1)	N/A	Try Down (1,1)	[[1,1,0],[0,0,0],[0,0,0]]
5	(1,1)	Yes	Mark (1,1), Try Right (1,2)	[[1,1,0],[0,1,0],[0,0,0]]
6	(1,2)	Yes	Mark (1,2), Try Right Out of bounds	[[1,1,0],[0,1,1],[0,0,0]]
7	(2,2)	Yes	Mark (2,2), Goal reached	[[1,1,0],[0,1,1],[0,0,1]]
8	End	Path found	Return path matrix	[[1,1,0],[0,1,1],[0,0,1]]

💡 Reached goal at (2,2), path found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	After Step 7	Final
x	0	0	0	0	1	2	2
y	0	0	1	1	1	2	2
path	[[0,0,0],[0,0,0],[0,0,0]]	[[1,0,0],[0,0,0],[0,0,0]]	[[1,1,0],[0,0,0],[0,0,0]]	[[1,1,0],[0,0,0],[0,0,0]]	[[1,1,0],[0,1,0],[0,0,0]]	[[1,1,0],[0,1,1],[0,0,1]]	[[1,1,0],[0,1,1],[0,0,1]]

Key Moments - 2 Insights

Why do we backtrack and unmark a cell in the path matrix?

When both right and down moves from a cell fail to reach the goal, we unmark it so it can be reused in other paths if needed. In this trace, backtracking occurs at step 3 but no unmark since down succeeds.

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

We only move to cells that are inside the maze and have value 1 (open path). This check prevents moving into walls or outside the maze, as seen in step 3 where (0,2) is not safe.

Visual Quiz - 3 Questions

Look at the execution_table, what is the path matrix state after step 2?

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

B [[0,1,0],[0,0,0],[0,0,0]]

C [[1,1,0],[0,0,0],[0,0,0]]

D [[1,1,1],[0,0,0],[0,0,0]]

💡 Hint

Check the 'Path Matrix State' column at step 2 in the execution_table.

At which step does the algorithm try to move down from position (0,1)?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look for 'Try Down (1,1)' action in the execution_table.

If the maze had no path to the goal, what would the final returned path matrix be?

A An empty array []

B A matrix with some 1s and some 0s

C A matrix with all 1s

D The original maze matrix

💡 Hint

Refer to the last line of the code in execution_sample where it returns [] if no path is found.

Concept Snapshot

Rat in a Maze Problem:
- Start at (0,0), try moving right or down.
- Mark path cells as 1, backtrack if stuck.
- Check cell safety before moving.
- Stop when bottom-right is reached.
- Return path matrix or empty if no path.

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 through cells marked as 1 (open path). The algorithm uses recursion to try moves, marks the path, and backtracks if a move leads to a dead end. The execution table shows step-by-step how the rat moves, marks cells, backtracks, and finally finds the path. Variables like position and path matrix update at each step. Key moments include understanding why backtracking unmarks cells and why safety checks are necessary. The visual quiz tests understanding of path states and backtracking steps. The concept snapshot summarizes the approach and rules for solving the maze.

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