Rat in a Maze is the classic first taste of backtracking — exploring a path, hitting a wall, and undoing your steps to try another route. It is the same shape as solving a maze on paper with a pencil and an eraser.
Problem. You are given an n x n grid where 1 is an open square and 0 is a wall. A rat starts
at the top-left (0,0) and wants to reach the bottom-right (n-1, n-1), moving only Down or
Right onto open squares. Return the sequence of moves (a string of D and R) that reaches the
goal, or report that none exists.
Example grid (1 = open, 0 = wall):
1 1 1 0
1 0 1 0
1 0 1 1
0 0 0 1Going Down first leads into a dead end, so the answer is RRDDRD.
The slow way first
You could try to enumerate every possible move sequence and test each one — but that explodes fast, and most sequences walk straight into a wall or off the board. The smarter move is to build the path one step at a time and abandon a branch the instant it cannot continue.
The question to ask: while I am standing on a square, which moves are still legal? Only the ones that stay on the board and land on an open square I am not already standing on. If none are legal, this square is a dead end — so I should step back and let the previous square try its next option.
The idea: walk forward, erase on a dead end
Do a depth-first search from (0,0). At each square: mark it as part of the current path, then try the moves in a fixed order (Down, then Right). Recurse into the first legal move. If that whole branch fails, try the next move. If every move fails, this square is a dead end — un-mark it (erase it from the path) and return failure so the caller can try something else.
The key insight: marking a cell as we enter and un-marking it as we leave is what makes backtracking work. The mark stops us from re-stepping onto our own path, and the un-mark frees the cell for a different route once this branch is abandoned.
Walk through it
Step through the animation. The rat first tries Down from (0,0), walking (1,0) then (2,0) — but (2,0) is boxed in by walls, a dead end. Watch those two cells un-mark as the recursion unwinds back to (0,0). From there it tries Right instead, and that branch flows cleanly down to (3,3). The path string RRDDRD is the answer, and the winning route lights up at the end.
Pseudocode
solve(grid, r, c, path):
if (r,c) is off the board: return failure
if grid[r][c] is not open: return failure # wall or on the path
mark grid[r][c] as on-the-path
if (r,c) is the goal: return path
for each move (Down, then Right):
result = solve(grid, neighbour, path + move)
if result is not failure: return result # a child reached the goal
un-mark grid[r][c] # backtrack
return failureThe Python solution
def solve(grid, r, c, path):
n = len(grid)
if r < 0 or r >= n or c < 0 or c >= n:
return None # off the board
if grid[r][c] != 1:
return None # wall or already on path
grid[r][c] = 2 # mark on the current path
if r == n - 1 and c == n - 1:
return path # reached the goal
for dr, dc, move in [(1, 0, "D"), (0, 1, "R")]:
result = solve(grid, r + dr, c + dc, path + move)
if result is not None:
return result # a child found the goal
grid[r][c] = 1 # un-mark (backtrack)
return None- The two guard
ifs reject any move that is off the board or onto a non-open cell (!= 1catches both walls and cells already on the path). grid[r][c] = 2is the mark — it temporarily turns an open cell into a path cell so we never step on it twice.- When
(r,c)is the bottom-right corner we have arrived, so we return the accumulatedpathstring. - The loop tries Down
(1,0)then Right(0,1); the first child that returns a non-Noneresult is bubbled straight up. grid[r][c] = 1on the way out is the backtrack — it un-marks the cell so a different route can use it later.
Complexity
| Case | Time | Notes |
|---|---|---|
| Worst case | O(2^(n²)) (moderate) | branch per open cell on dead-end-heavy grids |
| This grid | O(n²) (slow) | few branches; most paths short-circuit at walls |
O(n²) (slow)The recursion can, in the worst case, explore exponentially many partial paths, but the marking prunes hard: any branch that revisits a cell or hits a wall dies immediately. The extra space is the recursion stack plus the in-place marks, both bounded by the number of cells.
When this pattern shows up
Any problem that asks you to find a path or an arrangement by trying options and undoing the ones that fail is backtracking: maze solving, N-Queens, Sudoku, word search, and permutations. The signature move is the matched pair — mark before you recurse, un-mark after — so the grid (or board) is restored exactly as you found it.
Do not forget to un-mark on the way out. If you mark a cell and never reset it, a failed branch permanently blocks those squares, and a later route that genuinely needed them will report no solution.
Practice
The rat walks Down from (0,0) to (1,0) to (2,0). From (2,0), Down is (3,0) and Right is (2,1) — both walls. What happens next?
1. What does marking a cell (setting it to 2) accomplish?
2. Why must we un-mark a cell when a branch fails?
3. In what order does this solution try moves at each cell?
4. For the example grid, what path does the rat return?