Why Rat in a Maze Problem in DSA Typescript?

The Big Idea

What if you could teach a rat to always find its way out of any maze without getting lost?

The Scenario

Imagine you are in a big maze trying to find a path from the start to the exit. You try every possible turn by walking around, but it's easy to get lost or miss the right path.

The Problem

Manually checking every path is slow and confusing. You might go in circles or waste time exploring dead ends. It's hard to remember where you have been and which paths lead nowhere.

The Solution

The Rat in a Maze problem uses a smart way to explore paths step-by-step, backtracking when hitting a dead end. This method finds the correct path without getting lost or repeating work.

Before vs After

✗ Before

let found = false;
// Try every direction randomly
// No memory of visited paths
// May loop forever

✓ After

function solveMaze(maze, x, y, path) {
  if (exitFound) return true;
  if (safeToMove) {
    markPath();
    if (solveMaze(nextStep)) return true;
    unmarkPath(); // backtrack
  }
  return false;
}

What It Enables

This approach lets us find a path through complex mazes quickly and reliably, even when many routes exist.

Real Life Example

Robots exploring unknown buildings use similar logic to find exits without getting stuck or lost.

Key Takeaways

Manual maze solving is slow and error-prone.

Backtracking explores paths systematically and remembers visited spots.

It finds a valid path or tells if none exists.