Rat in a maze
mediumThe clearest picture of what backtracking actually means: a path is marked on the way in and erased on the way out, so a dead end leaves no trace to block later attempts.
O(4^(rows×cols))Space O(rows×cols)Saved in this browser - no sign-up, nothing sent anywhere.
How rat in a maze works
A rat starts at the top-left of a grid and must reach the bottom-right, moving one open cell at a time. The recursion is choose-explore-undo made spatial: stepping onto a cell marks it as part of the path, the four directions are tried in the fixed order down, right, up, left, and a cell that leads nowhere is unmarked before the function returns.
That unmarking is the point of the module. The path matrix doubles as the visited set and as the returned answer, so a dead end must be erased - leave it marked and the answer handed back includes corridors that lead nowhere. On screen this is a corridor lighting up on the way in and going dark as the recursion unwinds.
Backtracking here finds a path, not the shortest path: it commits to the first direction that works and reconsiders only on failure. On the default maze it returns 19 cells while the true shortest route is 17 - when distance matters, use breadth-first search instead. Direction order changes which route appears and how many cells get tried, but never whether a route exists.
Step by step
- From the start (0, 0), down is a wall, so the rat moves right to (0, 1) and then descends to (2, 1).
- It hugs the wall rightward through (2, 2) and (2, 3), where down and right are both blocked.
- The third choice, up, saves the branch: the rat climbs to (1, 3) and (0, 3), escaping over the wall block.
- Along the top and down column 5, it reaches (2, 5), then slides right to (2, 7) as walls close off down.
- Column 7 is an open shaft: the rat drops straight through rows 3 to 6 and steps onto the goal.
- The run ends with a 19-cell path after trying exactly 19 cells - no dead end at all. Paint a wall on the detour and cells go dark as recursion unwinds.
Complexity
| Worst case time | O(4^(rows×cols)) |
|---|---|
| Space | O(rows×cols) |
Finds *a* path, not the shortest - use BFS for that.
Reference implementation
Python
def solve_maze(grid):
n, m = len(grid), len(grid[0])
path = [[0] * m for _ in range(n)]
def walk(r, c):
if not (0 <= r < n and 0 <= c < m): return False
if grid[r][c] == 1 or path[r][c]: return False
path[r][c] = 1 # choose
if (r, c) == (n - 1, m - 1):
return True
for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
if walk(r + dr, c + dc): # explore
return True
path[r][c] = 0 # undo - dead end
return False
return path if walk(0, 0) else NoneJavaScript
function solveMaze(grid) {
const n = grid.length, m = grid[0].length;
const path = Array.from({ length: n }, () => new Array(m).fill(0));
const walk = (r, c) => {
if (r < 0 || r >= n || c < 0 || c >= m) return false;
if (grid[r][c] === 1 || path[r][c]) return false;
path[r][c] = 1;
if (r === n - 1 && c === m - 1) return true;
for (const [dr, dc] of [[1,0],[0,1],[-1,0],[0,-1]]) {
if (walk(r + dr, c + dc)) return true;
}
path[r][c] = 0; // dead end
return false;
};
return walk(0, 0) ? path : null;
}Worth noticing
The undo is visible here
Watch a corridor light up, hit a wall, and go dark again as the recursion unwinds. That erasing *is* the backtrack - the state has to be restored or the rat blocks itself out of routes it never actually took.
Backtracking finds a path, not the shortest
It commits to the first direction that works and only reconsiders on failure. If you need the shortest route, use BFS - see the grid pathfinding visualizer for the comparison.
Direction order changes everything except the answer
Trying down-then-right explores a completely different part of the maze from right-then-down. Both find a path if one exists; the number of cells visited can differ enormously.
Common pitfalls
- Checking the cell before the bounds. Python's negative indexing makes grid[-1][c] silently read the bottom row instead of failing, so the order of the two guards matters.
- Leaving dead ends marked. The path grid is also the answer - skip the path[r][c] = 0 undo and the returned route includes cells that lead nowhere.
- Not tracking cells already on the path. Without that check, down followed by up revisits the same cell forever and the recursion never terminates.
- Checking the goal before marking it. This variant marks first, so the goal cell appears in the returned path - reorder the two and the route arrives one cell short.
- Expecting the shortest route. The first direction that works wins, so the answer can wander - 19 cells here against a 17-cell optimum. Reach for BFS when length matters.
Where it is used
- Grid word puzzles - Boggle and word-search solvers mark a letter, extend the word, and unmark, exactly this pattern.
- Game and level tooling, where a solver proves a generated maze or puzzle level is actually completable.
- Micromouse and robotics teaching, where wall-following and backtracking are the entry point before real planners like A star.
- The interview grid-DFS family - word search unmarks exactly like this, while flood fill and number of islands drop the undo.
Frequently asked questions
What is the time and space complexity of rat in a maze?
Worst-case time is O(4^(rows×cols)) - four direction choices at every step of a path that could wind through every cell. Space is O(rows×cols) for the path matrix plus a recursion stack that can grow as long as the path. In practice the wall and on-path checks cut the tree drastically: the default 8×8 maze finishes after touching 19 cells.
What is the difference between DFS and backtracking?
Backtracking is depth-first search plus undo. Plain DFS marks a cell visited forever, which is fine for reachability; backtracking un-marks on failure because its state is part of the answer being built. Here the path matrix is the answer, so dead ends must be erased from it.
Does backtracking find the shortest path?
No. It returns the first complete path its direction order stumbles into - 19 cells on the default maze, where BFS finds 17. Backtracking answers whether a path exists and produces one such path; shortest-path questions belong to BFS on unweighted grids, or Dijkstra when moves have weights.
What happens when the maze has no solution?
The search exhausts every reachable open cell, unwinds each one as a dead end, and returns false from the start cell. That failure is a proof - backtracking is complete, so no route found genuinely means no route exists, not just none noticed.