BacktrackingAlgorithmaka rat in a maze, path in a grid, grid DFS

Maze Search (Grid Backtracking)

Find a path from start to exit in a grid by recursively stepping into open neighbors, marking cells on the current path and unmarking on retreat.

▶ VisualizePattern: Depth-First SearchPractice (4)
Progress

Overview

Maze search is Depth-First Search (DFS) on an implicit grid graph, written as backtracking. From the current cell, try each of the four directions; if the neighbor is inside the grid, open, and not on the current path, step into it and recurse. If the recursion reaches the exit, propagate true and leave the path marks in place; otherwise unmark and try the next direction.

Two variants matter: find any path (mark visited permanently — each cell needs to be explored once, giving O(rows · cols)) versus enumerate all simple paths (un-mark on retreat — exponential, because a cell may be part of many different paths).

backtrackinggridDFSpath findingvisited marking

Intuition

A mental model before the formal terms.

You are in the maze with a piece of chalk. At each cell you mark the floor, then try up/right/down/left. When you hit a wall or a chalk-marked cell, turn to the next direction. When every direction fails, erase the chalk and step back. The chalk trail at the moment you reach the exit is the path.

For "any path", you keep the chalk even after retreating: a cell that led nowhere once will lead nowhere again, so never re-enter it.

How it works

  1. Base cases: out of bounds, wall, or already on the path → false. Cell equals the target → true.
  2. Mark the cell as on the path and append it to path.
  3. For each direction (dr, dc) in [(1,0),(0,1),(-1,0),(0,-1)], recurse on (r+dr, c+dc); if it returns true, return true immediately.
  4. None succeeded: pop the cell from path, unmark (for all-paths) or leave marked (for any-path), and return false.

Why it works

The marking guarantees the current path is simple (no repeated cells), so the recursion depth is bounded by the number of cells and terminates.

For any-path: if a cell cannot reach the exit via cells not on the current path, it also cannot reach it later — the set of unexplored cells only shrinks — so permanent marking loses nothing. This is exactly the DFS visited-set argument.

For all-paths: unmarking restores the state so that sibling directions explore the same cell through a different prefix, which is required because a cell may lie on many distinct simple paths.

Recognition

How to tell a problem wants this.

  • 2D grid of open/blocked cells; "is there a path", "print a path", "count all paths".
  • 4-directional (or 8-directional) movement with an obstacle predicate.
  • If the question is shortest path, this is the wrong tool — see BFS Shortest Path (Unweighted).
“connected groups” → Depth-First Search“all combinations” → Backtracking

Interactive visualization

Play, step, change the input. ← → and space work too.

S
.
#
.
.
.
.
#
#
.
#
.
.
.
.
.
#
.
.
#
.
#
.
.
.
#
.
.
.
T
Path stack (0)
empty
1/18DFS from S at (0,0) to T at (4,5). The recursion stack doubles as the path; dead ends are undone by popping.
StartTargetWallCurrent cellCurrent pathDead end (visited)
PseudocodeLearn Maze Search (Grid Backtracking) →
1dfs(r, c):
2  if out of bounds or wall or visited: return false
3  visited[r][c] = true; path.push((r,c))
4  if (r,c) == T: return true
5  for each direction: if dfs(next): return true
6  path.pop(); return false     // backtrack
Variables
rows5
cols6
Complexity
worst O(R · C) for one path; exponential for all paths
space O(R · C)
Speed

Pseudocode

1dfs(r, c):
2  if out of bounds or wall or onPath[r][c]: return false
3  path.push((r, c)); onPath[r][c] = true
4  if (r, c) == target: return true
5  for (dr, dc) in DIRS:
6    if dfs(r + dr, c + dc): return true
7  path.pop(); onPath[r][c] = false   # keep true for any-path variant
8  return false

Implementations

11 · Direction vectors
2DIRS = [(1, 0), (0, 1), (-1, 0), (0, -1)]
3 
4 
5def find_path(grid: list[list[int]], start: tuple[int, int],
6              target: tuple[int, int]) -> list[tuple[int, int]] | None:
7    """grid[r][c] == 0 open, 1 wall. Returns one start-to-target path or None."""
8    rows, cols = len(grid), len(grid[0])
9    visited = [[False] * cols for _ in range(rows)]
10    path: list[tuple[int, int]] = []
11 
12    def dfs(r: int, c: int) -> bool:
132 · Reject out-of-bounds, walls, and revisits
14        if not (0 <= r < rows and 0 <= c < cols):
15            return False
16        if grid[r][c] == 1 or visited[r][c]:
17            return False
183 · Choose: mark the cell and extend the path
19        visited[r][c] = True               # permanent: any-path variant
20        path.append((r, c))
21        if (r, c) == target:
22            return True
234 · Explore the four neighbors
24        for dr, dc in DIRS:
25            if dfs(r + dr, c + dc):
26                return True
275 · Un-choose: drop the cell from the path
28        path.pop()                         # visited stays True: dead cell
29        return False
30 
31    return path if dfs(*start) else None
Walkthrough
  1. The chained comparison 0 <= r < rows and 0 <= c < cols is the idiomatic bounds check.
  2. visited is built with a list comprehension — one independent row list per row.
  3. Section 3 marks the cell permanently and appends to path; tuples compare by value, so (r, c) == target just works.
  4. Section 4 tries the four neighbors in order and short-circuits on the first success, leaving the successful route in path.
  5. Section 5 pops the failed cell but keeps visited[r][c] True: a cell that could not reach the target once never can.
  6. dfs(*start) unpacks the start tuple into the two positional arguments.
Complexity (this implementation)
time O(R · C) — each cell is entered at most once · space O(R · C) for visited plus recursion depth up to R · C

CPython's default recursion limit is 1000, which a ~32×32 grid can exceed on a snaking path.

Language notes
  • Raise the limit with sys.setrecursionlimit(rows * cols + 100) for larger grids, or rewrite with an explicit list-based stack (no limit, and faster).
  • [[False] * cols for _ in range(rows)] is correct; [[False] * cols] * rows aliases one row object rows times.
  • Tuples are hashable, so a set[tuple[int, int]] is a drop-in alternative to the boolean matrix.
Common mistakes in this language
  • Building the visited matrix with * on the outer list, so marking one row marks them all.
  • Recursing on big grids without raising the recursion limit — RecursionError at depth 1000.
  • Unmarking visited on retreat when only one path is needed, blowing up to exponential time.
Language differences that matter here
  • Out-of-bounds indexing: C++ is undefined behavior (check first, always); JS/TS yield undefined; Python raises IndexError — and negative indices silently wrap, so the explicit range check is still required.
  • Recursion depth can reach R·C: Python hits its 1000-frame default limit first (sys.setrecursionlimit or an explicit stack); JS/TS and C++ fail later but just as hard.
  • Coordinate equality: Python tuples compare by value; C++ std::pair has operator==; JS/TS arrays compare by reference, so coordinates are compared element-wise.

Complexity

Best
—
Average
—
Worst
O(R · C) for one path; exponential for all paths
Space
O(R · C)

Any-path with permanent visited marks touches each cell once. Enumerating all simple paths is exponential in grid size. Recursion depth can reach R·C — iterate with an explicit stack for large grids.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Existence or one example of a path in a grid with obstacles.
  • Enumerating or counting all simple paths on a small grid.
  • Flood fill / connected regions (Connected Components on a grid) where DFS order is irrelevant.
Avoid it when

Alternatives

BFS Shortest Path (Unweighted)Depth-First Search (DFS)Grid DPA* Search

Common mistakes

  • Forgetting the bounds check before indexing grid[r][c].
  • Unmarking visited in the any-path variant, turning O(RC) into exponential time.
  • Not unmarking in the all-paths variant, missing most paths.
  • Marking the cell visited after the recursive calls instead of before, causing infinite recursion between two adjacent cells.
  • Stack overflow on large grids (10^6 cells) — use an explicit stack.

Interview patterns

  • Rat in a Maze (return one path / all paths as direction strings).
  • Number of Islands and flood fill: DFS with permanent marking, counted per start.
  • Unique Paths III: all paths that visit every open cell exactly once — backtracking with a remaining-cells counter.
Interview questions on this
Mock interviews

Example problems

Number of IslandsmediumShortest Path in Binary MatrixmediumRotting OrangesmediumWord Searchmedium