Rat in a Maze Problem in DSA Typescript - 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

↓

Move Right

→Move Down

↓

If path found

No↓

Backtrack: Unmark cell

↓

Return False if no moves possible

↓

Goal reached at (N-1,N-1)

↓

Return True - path found

The rat starts at the top-left cell and tries to move right or down if the cell is safe. It marks the path and backtracks if stuck, until it reaches the goal.

Execution Sample

DSA Typescript

function solveMaze(maze: number[][], x: number, y: number, path: number[][]): boolean {
  const N = maze.length;
  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 (solveMaze(maze, x + 1, y, path) || solveMaze(maze, x, y + 1, path)) {
      return true;
    }
    path[x][y] = 0;
  }
  return false;
}

This recursive function tries to find a path from top-left to bottom-right by moving right or down in a safe maze.

Execution Table

Step	Current Position (x,y)	Is Safe?	Action	Path Matrix State
1	(0,0)	Yes	Mark (0,0), Move Right	[[1,0,0],[0,0,0],[0,0,0]]
2	(1,0)	Yes	Mark (1,0), Move Right	[[1,0,0],[1,0,0],[0,0,0]]
3	(2,0)	No	Backtrack (2,0)	[[1,0,0],[1,0,0],[0,0,0]]
4	(1,1)	Yes	Mark (1,1), Move Right	[[1,0,0],[1,1,0],[0,0,0]]
5	(1,2)	Yes	Mark (1,2), Move Right	[[1,0,0],[1,1,1],[0,0,0]]
6	(2,2)	Yes	Mark (2,2), Goal Reached	[[1,0,0],[1,1,1],[0,0,1]]
7	Return True	-	Path Found	[[1,0,0],[1,1,1],[0,0,1]]

💡 Goal reached at (2,2), path found successfully.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
x	0	1	2	Backtrack to 1	1	1	2	2
y	0	0	0	Backtrack to 1	1	2	2	2
path	[[0,0,0],[0,0,0],[0,0,0]]	[[1,0,0],[0,0,0],[0,0,0]]	[[1,0,0],[1,0,0],[0,0,0]]	[[1,0,0],[1,0,0],[0,0,0]]	[[1,0,0],[1,1,0],[0,0,0]]	[[1,0,0],[1,1,1],[0,0,0]]	[[1,0,0],[1,1,1],[0,0,1]]	[[1,0,0],[1,1,1],[0,0,1]]

Key Moments - 3 Insights

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

When both moving right and down from a cell fail to find the goal (see Step 3), we remove the mark to indicate this cell is not part of the correct path, allowing other paths to be explored.

How do we know when the goal is reached?

At Step 6, when the current position is (2,2) which is the bottom-right cell, the function marks it and returns true, signaling the path is complete.

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

Only cells with value 1 are safe to move into. This check prevents moving into blocked cells (like at Step 3 where (2,0) is unsafe).

Visual Quiz - 3 Questions

Look at the execution table, what is the path matrix state after Step 4?

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

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

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

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

💡 Hint

Check the 'Path Matrix State' column for Step 4 in the execution table.

At which step does the algorithm backtrack due to an unsafe cell?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look for the step where the action says 'Backtrack' in the execution table.

If the maze had a blocked cell at (1,2), what would happen at Step 5?

A The algorithm would skip (1,2) and move down

B The algorithm would mark (1,2) and continue

C The algorithm would backtrack from (1,2)

D The algorithm would immediately find the goal

💡 Hint

Refer to the safety check and backtracking logic shown in the execution table and variable tracker.

Concept Snapshot

Rat in a Maze Problem:
- Start at top-left cell (0,0)
- Move only right or down to safe cells (value 1)
- Mark path cells as part of solution
- Backtrack if stuck by unmarking
- Stop when bottom-right cell is reached
- Recursive DFS approach

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 into safe cells marked with 1. The algorithm marks each cell it visits as part of the path. If it reaches a dead end, it backtracks by unmarking the cell and tries other directions. This process continues recursively until the goal cell is reached or no path exists. The execution table shows each step, the current position, safety check, actions taken, and the path matrix state. Key moments include understanding backtracking, recognizing the goal, and checking cell safety. The visual quiz tests understanding of path states, backtracking steps, and behavior when cells are blocked.