Backtracking: Complete Beginner's Guide With easy examples.

Backtracking builds a solution one step at a time and undoes the last step whenever it hits a dead end. Imagine a maze: you walk down one path, and if it is blocked, you walk back to the last crossing and try the next path.

It matters because puzzles like N-Queens and Sudoku have far too many arrangements to list blindly. Backtracking explores them in a smart order and abandons hopeless paths early, saving enormous wasted work.

Key Concepts

• Choice point: a spot where you pick one of several options, like choosing a digit for a Sudoku cell.
• Constraint: a rule the answer must satisfy, e.g. "no two queens may attack each other".
• Candidate solution: the partial answer built so far, extended one choice at a time.
• Backtrack step: when the partial answer breaks a rule, remove the last choice and try the next option. Pruning cuts off a whole branch that can never succeed.
• Base case: the answer is complete and every rule holds; the search stops and reports success.

Formulas

• N-Queens recurrence: T(n) = n × T(n − 1), which solves to T(n) = O(n!). Each of the n rows tries up to n columns.
• Permutations: all arrangements of n items take O(n × n!) time — n! arrangements, each O(n) to output.

These assume each choice is tested in constant time and describe the worst case: pruning makes real runs much faster but does not change the worst-case class.

Worked Example

Place 4 queens on a 4×4 board so none attack each other. Rows and columns numbered 0 to 3:

1. Row 0: try column 0. Queen at (0, 0). Safe.
2. Row 1: column 0 is attacked by (0, 0), column 1 diagonally attacked. Try column 2: queen at (1, 2).
3. Row 2: every column is attacked — column 0 by (0, 0), columns 1 and 3 diagonally by (1, 2), column 2 sharing a column with it. Dead end.
4. Backtrack: remove (1, 2), try column 3 in row 1: queen at (1, 3). Row 2's options fail again, so backtrack once more.
5. After exhausting dead branches, one valid answer emerges: (0, 1), (1, 3), (2, 0), (3, 2). Spot-check (1, 3) vs (3, 2): row gap 2, column gap 1 — not equal, so no diagonal attack. All six pairs pass.

Common Misconceptions

• "Backtracking is brute force." Brute force tests every full answer at the end. Backtracking tests partial answers as it goes and abandons dead branches early.
• "It always finds the best answer." It finds a valid answer. Optimisation needs extra machinery like branch-and-bound.
• "Recursion depth does not matter." A size-n search can recurse n levels deep and overflow the call stack; iterative versions or depth limits fix this.

Real-World Applications

• Puzzle solvers: Sudoku and crossword apps use backtracking.
• Scheduling: exam timetables assign slots one by one and backtrack on clashes.
• Route planning: navigation and robot path search back out of dead ends.
• Game AI: maze solving and game-tree search use the same try-and-undo idea.

Backtracking turns an impossible-looking search into a patient, orderly one: try a choice, check the rules, step back when something breaks. It powers puzzle solvers, timetables, and route planners.