Faangprep Logo
Log inStart free
Browse curriculum

Rat in a Maze

The Rat in a Maze problem asks for a path through an N*N maze with obstacles, from the top-left corner to the bottom-right corner.

The rat tries down, then right, then up, then left. When a cell has nothing left to try, it steps back off — and that cell is open again for a different route.

READY

S
G

Backtracks

0

 

Start at (0, 0), reach (4, 4). Nothing walked yet.

Next

Step onto (0, 0) — position 1 on the route.

Maze

Intuition

Imagine a rat starts at the source and wants to reach the destination. The rat can move in four directions: up, down, left, right. It cannot move to a blocked cell or a cell it has already visited in the current path. If it hits a dead end, it backtracks.

Concept

Key Concepts:

  1. Grid Traversal: Moving through a 2D array.
  2. State Management: Keeping track of visited cells to avoid cycles.
  3. Backtracking: Exploring a path, and if it fails, undoing the last move to try a different direction.
  4. Directions: Typically Down, Right, Up, Left (lexicographical order if required).

How it Works

  1. Start at (0, 0).
  2. Mark the current cell as part of the solution path.
  3. Try moving in allowed directions (e.g., D, L, R, U).
  4. Check if the next cell is safe (within bounds, open, not visited).
  5. If safe, recursively jump to that cell.
  6. If the recursion returns true (destination found), propagate true up.
  7. If all directions fail, unmark the current cell (backtrack) and return false.

Step-by-Step Breakdown

Example 3x3 Maze:

  • Start (0,0). Valid. Path: [(0,0)]
  • Try Down (1,0): Wall.
  • Try Right (0,1): Valid. Path: [(0,0), (0,1)]
  • From (0,1), Try Down (1,1): Valid. Path: ...
  • Continue until (N-1, N-1) is reached.
  • If stuck, remove last cell from path and try next direction.

When to Use

  • Pathfinding in grids with obstacles.
  • Generating all possible paths in a maze.
  • Robotics path planning (basic).

When NOT to Use

  • Finding the shortest path in an unweighted graph (use BFS).
  • Large open grids where A* or other heuristic search is more efficient.

How to Identify

"Find path in a grid", "Maze", "Rat", "Reach destination".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Sudoku Solver

Next

Introduction

Frequently Asked Questions

What is Rat in a Maze?

A pathfinding problem where a "Rat" must find its way from a start to an end point through a grid with obstacles (walls).

Role of the "Visited" array?

To prevent infinite recursion, the algorithm marks cells as "Visited" so the rat doesn't cycle between the same two cells.

Generating multiple paths?

After finding a path, the algorithm "Un-marks" cells (backtracks) to find other possible routes to the destination.