Rat in a Maze Problem in DSA Typescript

Mental Model

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

Analogy: Imagine a mouse trying to find cheese in a maze by moving step-by-step through open paths without hitting walls.

S -> 1 0 0
1 -> 1 1 0
0 -> 0 1 E

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

Dry Run Walkthrough

Input: maze: [[1,0,0],[1,1,0],[0,1,1]], start at top-left (0,0), goal bottom-right (2,2)

Goal: Find one path from start to goal moving only on 1s

Step 1: Start at (0,0), mark path

[S] -> 0 0
1 -> 1 0
0 -> 1 E

Why: We begin from the start cell

Step 2: Move down to (1,0), path is open

S -> [1] 0
↑ -> 1 0
0 -> 1 E

Why: Down is open and closer to goal

Step 3: Move right to (1,1), path is open

S -> 0 0
1 -> [1] 0
0 -> 1 E

Why: Right is open and leads towards goal

Step 4: Move down to (2,1), path is open

S -> 0 0
1 -> 1 0
0 -> [1] E

Why: Down is open and closer to goal

Step 5: Move right to (2,2), goal reached

S -> 0 0
1 -> 1 0
0 -> 1 [E]

Why: Reached the destination

Result:

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

Annotated Code

DSA Typescript

class MazeSolver {
  maze: number[][];
  n: number;
  path: number[][];

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

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

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

  solveUtil(x: number, y: number): boolean {
    if (x === this.n - 1 && y === this.n - 1 && this.maze[x][y] === 1) {
      this.path[x][y] = 1;
      return true;
    }

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

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

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

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

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

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

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

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

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

check if current cell is goal 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 path

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

try moving down

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

try moving right

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

backtrack if no path found from current cell

Output

1 0 0 

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

vs Alternative: Compared to BFS which finds shortest path, this DFS approach finds one path but may be slower in large mazes

Edge Cases

Empty maze (no cells)

No path found, function returns false

DSA Typescript

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

Start or end cell blocked

No path found, function returns false

DSA Typescript

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

Maze with no possible path

Backtracking exhausts all options, prints 'No path found'

DSA Typescript

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

When to Use This Pattern

When you see a grid with blocked and open cells and need to find a path from start to end, use backtracking to explore possible routes.

Common Mistakes

Mistake: Not marking visited cells causing infinite loops
Fix: Mark cells as visited in path matrix before recursive calls

Mistake: Trying to move outside grid boundaries
Fix: Check boundaries with isSafe before moving

Summary

Finds a path through a maze from start to finish using backtracking.

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

The key is to try moves step-by-step and backtrack when stuck.