Pattern 4: Backtracking on a grid

Backtracking is DFS with a twist: you mark a cell when entering a path and unmark it when leaving, freeing it for other attempts. It is like exploring a maze by unrolling a thread and reeling it back in when you return.

🎯

Try it first: Word Search

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Given a letter grid board and a word, return true if the word can be formed from adjacent letters (horizontal/vertical), without reusing the same cell.

Example: board [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word "ABCCED" → true.

Carregando editor…

Tried it? The hard part here is not finding the first letter — it is not reusing the same cell in the path, and being able to try another path when one fails. The theory below shows the missing piece: undoing the mark on the way back.

The theory: mark, explore, unmark

In flood fill (lesson 4), a visited cell stayed marked forever — we wanted to cover the region once. In backtracking it is different: we want to find a specific path, and a cell that did not work for this path may work for another. That is why the mark is temporary:

dfs(r, c, i):                      # try to match word[i] at (r,c)
    if i == len(word)        → found it all! return True
    if outside the grid
       or grid[r][c] != word[i]  → return False
    if (r,c) is already in the path  → return False
    mark (r,c) in the path        # ENTER
    try the 4 neighbors for word[i+1] (if any returns True, propagate)
    unmark (r,c) from the path    # LEAVE (backtrack!)
    return (whether any neighbor worked)

The "unmark" line is the heart of backtracking. Without it, a failed attempt would block cells forever and valid paths would be lost. Watch the path (green) grow as it advances and shrink when the DFS comes back — that is the backtrack happening before your eyes:

Execução real, gravada passo a passo

Carregando Python no navegador (primeira vez demora alguns segundos)…

(In the visualizer, the word is ABFD: follow the path try a direction, fail, back up and try another, until it assembles the word.)

Why is the complexity exponential in the worst case?

From each cell, the DFS can follow up to ~4 directions, and the search tries to start from each of the m·n cells. In the worst case, that gives something like O(m·n·4ᴸ), where L is the length of the word (from each cell ~3 new directions branch out, L times). It is exponential in L — and that's fine: backtracking explores a search space that can be large, but the pruning (stopping as soon as grid[r][c] != word[i]) cuts the vast majority of branches early. The space is O(L) (recursion depth / path length).

DFS vs. backtracking: they are cousins. In flood fill, the mark is permanent (cover a region). In backtracking, the mark is undone (explore alternative paths). Recognizing which of the two the problem calls for is half the battle.

Where backtracking shows up

Word Search, generating permutations/combinations, Sudoku, N-Queens, mazes with "all paths". The skeleton is always the same: choose → explore → undo the choice. You will run into it outside grids too — it is one of the most transferable patterns in the course.

🧠 Review quiz

0/4

1. What is the essential difference between the flood fill DFS (lesson 4) and backtracking?

2. Why is the 'unmark the cell' line indispensable in word search?

3. What lets backtracking, despite exponential worst-case complexity, be viable in practice?

4. What is the general skeleton of any backtracking?

Summary

Backtracking = DFS with a temporary mark: mark on entry, unmark on exit.
Word Search: match word[i] at the cell, try the neighbors for word[i+1], undo on failure.
Worst case exponential in L, but pruning makes it viable; space O(L).
Universal skeleton: choose → explore → undo.

Next lesson: when the question is "the shortest path" — BFS.

All lessons in this section