Depth-First Search with Backtracking

This is the pattern behind solving puzzles like Sudoku and the eight-queens problem, and it is the natural way to explore any space of choices — whether you are scheduling tasks, planning a route, or making a program that can reason about moves in a game. Once you can think in terms of trying a path, checking if it works, and undoing it when it dead-ends, you can tackle a whole class of problems that otherwise feel impossibly complex. It also sets up the idea of recursion — defining a problem in terms of smaller versions of itself — which is the backbone of tree traversal, parsing, and many AI algorithms. If you go on to build agentic systems, this is the same logic that lets an agent try a tool call, see if it fails, and try another.

Imagine you are exploring a maze. You walk forward along a path, making a choice at each fork. If you hit a dead end, you walk back to the last fork and try the other branch. That is depth-first search: you commit to one choice and follow it as far as possible before backing up. Backtracking is the act of undoing your most recent choice to try an alternative. The key insight is that you do not need to remember every dead end — you only need to remember the current path and the choices still available at each level. When you reach a dead end, you 'undo' the last move and try the next option. If all options at that level are exhausted, you undo one more level. This systematic 'try, fail, undo, try again' is what makes the search complete — it will visit every reachable state in the worst case, but pruning lets you skip huge regions that cannot contain a solution.

Think of navigating a maze by dropping breadcrumbs. You start at the entrance, and at every fork you pick a passage and mark it with a pebble. You walk as far as you can, leaving a trail of pebbles behind you. If you reach a dead end, you turn around and walk back, picking up your pebbles as you go, until you reach a fork where you have not yet tried a path. You then take that path. If you ever return to a fork and find all its paths marked, you pick up the pebble at the fork itself and continue back to the previous fork. This is exactly what backtracking does — you are unwinding your steps, retracing the recursion stack. The breadcrumbs are the record of what you have already tried. The maze is the tree of choices, and your walk is a depth-first traversal. Where the analogy breaks down: in a maze, you can physically walk back; in a program, you have to restore the state (like a list of choices made) to what it was before the failed branch. Also, in a maze, you do not necessarily know if a path leads to a dead end until you reach it; backtracking lets you prune early based on partial constraints, like realising a path is blocked even before the end. And a program can revisit a state; a maze is static, but in puzzles like Sudoku, the state changes as you fill cells, so you must undo those changes when you backtrack.

Depth-first search with backtracking is a way of exploring all possible sequences of choices by trying one option as far as possible, and when it fails, undoing the last choice and trying the next one, until a solution is found or all options are exhausted.

This concept builds directly on the idea of recursion, which is the natural way to write it — today you have already mastered base cases and recurrence, and this is where they come alive. When you write a recursive function that tries a choice and calls itself on the remaining problem, you are doing depth-first search; when that call returns without success and you undo the choice, you are backtracking. It also connects to stack memory behaviour, because each recursive call consumes a stack frame — your recursion depth is exactly the depth of your search path. And it relates to tail recursion: sometimes you can turn a recursive backtracking function into a loop, but because you need to undo and try alternatives, backtacking is not usually tail recursive in the simple sense.