ƒ(x) PatternsAdvanced interactive
Backtracking
Try, fail, undo, try again — search a decision tree.
n_queens_backtracking
step 1 / 369
Place queens row by row so none attack.
placed / safeconflictbacktrack
speed1×
How it works
Backtracking explores a tree of partial solutions, abandoning a branch the moment it can't lead to a valid answer ('pruning'). It systematically generates permutations, subsets, and constraint solutions like N-Queens and Sudoku.
Mental models
- Choose → explore → un-choose. The undo step is what makes it backtracking.
- Pruning invalid branches early is the difference between fast and hopeless.
Complexity
- Time
- O(b^d)branching ^ depth
- Space
- O(d)
Reach for it when
- N-Queens & Sudoku
- Permutations / combinations
- Constraint solving