Back to Study Material Data Structures and Algorithms

Rat in a Maze

The rat in a maze problem presents an N-by-N grid where each cell is either passable (1) or blocked (0). A rat starts at cell (0, 0) and must reach cell (N...

Rat in a Maze

Problem Description and Grid Traversal

The rat in a maze problem presents an N-by-N grid where each cell is either passable (1) or blocked (0). A rat starts at cell (0, 0) and must reach cell (N-1, N-1). Find all paths from source to destination, or determine if any path exists. The rat can move in four directions: up, down, left, right (or sometimes only right and down in simpler variants).

This is a classic backtracking problem on a grid. The state is the current cell (row, column) and a visited matrix tracking which cells are part of the current path (to avoid cycles). The constraint is: the next cell must be within bounds, passable (value == 1), and not already visited on the current path.

Algorithm: define solve(row, col, path). If (row, col) == (N-1, N-1), record path as a solution. Otherwise, for each direction (up = (-1,0), down = (1,0), left = (0,-1), right = (0,1)): compute next_row = row + dr, next_col = col + dc. If next_row and next_col are in bounds, maze[next_row][next_col] == 1, and not visited[next_row][next_col]: mark visited[next_row][next_col] = true, append direction to path, recurse, unmark, remove direction from path.

A worked example: 4x4 maze with all cells passable. From (0,0) to (3,3), the path "DDRR" means down, down, right, right — going (0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2) — this is not quite right since we need to reach (3,3). A valid path is "DDDRRR" but that exceeds bounds. For a 4x4 grid, a path like "DRRDRR" reaches (3,3) via (1,0),(1,1),(1,2),(2,2),(2,3),(3,3) — wrong length. The correct path "DDRDRR" depends on the specific maze; construct a small example and trace it.

Interview tip: Always validate that your code handles the case where the source or destination cell is blocked (maze[0][0] == 0 or maze[N-1][N-1] == 0). Return empty immediately without entering the main recursion.

Backtracking Implementation with Path Tracking

Implementing rat in a maze with full path tracking requires careful state management. Two approaches exist: pass the path string by value (simple but copies the string at each level, costing O(path_length) per recursive call) or pass it by reference and undo changes after recursion (more efficient).

Reference-based implementation: maintain a global list of solutions and a path string by reference. When entering a cell, append the direction character ('D', 'U', 'L', 'R') to the path. When backtracking, remove the last character. This is the standard backtracking "choose/explore/unchoose" pattern.

Handling the visited matrix: mark the current cell as visited before recursing, unmark it after. This prevents the path from revisiting cells, which would cause infinite loops in mazes with cycles. The visited matrix must be distinct from the maze grid because you need to unmark cells when backtracking.

A subtle implementation point: when moving to the starting cell (0, 0), mark it as visited before calling the recursive function. If the recursion function marks the starting cell itself, you risk off-by-one errors where some adjacent cells appear reachable before (0, 0) is marked.

Path string output format: 'D' for down (row increases), 'U' for up (row decreases), 'L' for left (col decreases), 'R' for right (col increases). Sort the direction order (D, L, R, U) if the problem asks for lexicographically smallest paths first.

Time complexity: O(4^(N^2)) in the worst case (four choices at each of N^2 cells). In practice, blocked cells and the visited constraint dramatically reduce this. Space complexity: O(N^2) for the visited matrix and recursion stack depth (path length is at most N^2).

Interview tip: If asked to find only whether a path exists (not all paths), you can return true as soon as you find the first path and stop exploring. This optimization is significant in large mazes and is worth mentioning as a natural extension.

Comparison with BFS for Shortest Path

Backtracking finds all paths in a maze, but it does not necessarily find the shortest path efficiently. When the goal is specifically the shortest path, BFS (breadth-first search) is the correct algorithm. BFS explores cells level by level (by distance from the source), guaranteeing that the first time it reaches the destination, the path taken is the shortest.

BFS for rat in a maze: use a queue. Enqueue the starting cell with distance 0. Mark it visited. While the queue is not empty: dequeue a cell (row, col, distance). If it is the destination, return the distance. For each valid neighbor, if not visited: mark visited, enqueue (next_row, next_col, distance + 1). If the queue empties without reaching the destination, no path exists.

Difference in use cases: backtracking is appropriate when you need all paths, need to satisfy additional path constraints (e.g., must collect all treasures), or the maze structure makes DFS more natural (tree-shaped mazes). BFS is appropriate when you need the shortest path in an unweighted grid, where each move has equal cost.

For weighted grids (where different cells have different traversal costs), neither plain BFS nor backtracking gives the minimum-cost path. Dijkstra's algorithm is needed, using a priority queue instead of a regular queue and expanding cells in order of increasing total cost.

BFS time complexity: O(N^2) — each cell is visited at most once. Space complexity: O(N^2) for the visited array and the queue. This is vastly better than the O(4^(N^2)) worst case for backtracking in large grids.

Interview tip: When the interviewer asks for the shortest path, recognize that backtracking is the wrong tool and state this clearly: "For the shortest path I would use BFS rather than backtracking, because BFS guarantees shortest distance and runs in O(N^2) instead of exponential time." This shows you choose algorithms based on requirements, not habit.