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

Rat in a Maze Problem

📖 Scenario: Imagine a small rat trying to find its way through a maze to reach the cheese. The maze is a grid where some cells are open paths and others are walls. The rat can only move right or down. Your task is to help the rat find a path from the top-left corner to the bottom-right corner.

🎯 Goal: Build a program that represents the maze as a 2D array, sets up a solution grid, finds a path for the rat using backtracking, and prints the path taken by the rat.

📋 What You'll Learn

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

Create a 2D array called solution initialized with zeros.

Write a function solveMaze that finds a path from start to end using backtracking.

Print the solution grid 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 backtracking and pathfinding is important for software engineers working in game development, robotics, and AI.

1

Create the maze grid

Create a 2D array called maze with these exact values:
[[1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1]].
Here, 1 means open path and 0 means wall.

DSA Typescript

# Your code here

Hint

Use const maze: number[][] = [...] to create the 2D array with the exact values.

2

Create the solution grid

Create a 2D array called solution with the same size as maze, filled with zeros.

DSA Typescript

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

# Your code here

Hint

Create solution as a 2D array with zeros matching the maze size.

3

Write the backtracking function

Write a function called solveMaze that takes maze, solution, x, and y as parameters.
Use backtracking to find a path from top-left (0,0) to bottom-right (3,3).
Mark the path in solution with 1s.
Return true if path found, else false.
Use only moves right (x + 1) and down (y + 1).

DSA Typescript

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

const solution: number[][] = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
];

# Your code here

Hint

Use recursion and backtracking. Check if current cell is safe, mark it, try moving right and down, backtrack if needed.

4

Print the solution path

Call solveMaze(maze, solution, 0, 0) to find the path.
If path found, print the solution grid row by row.
Each row should be printed as space-separated numbers.

DSA Typescript

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

const solution: number[][] = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
];

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

function solveMaze(maze: number[][], solution: number[][], x: number, y: number): boolean {
  if (x === maze.length - 1 && y === maze[0].length - 1 && maze[x][y] === 1) {
    solution[x][y] = 1;
    return true;
  }

  if (isSafe(maze, x, y)) {
    if (solution[x][y] === 1) {
      return false; // already part of solution path
    }

    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;
}

# Your code here

Hint

Call solveMaze(maze, solution, 0, 0). If it returns true, print each row of solution with spaces.