Backtracking is a refined form of brute force. It builds solutions incrementally and abandons paths ("backtracks") as soon as it determines they cannot lead to a valid solution.
State-Space Trees
Think of the decision process as a tree. Each node represents a state, and each edge is a choice. Backtracking explores this tree, using recursion to go deep into promising branches.
Pruning: The Secret Sauce
Pruning is what makes backtracking efficient. By checking constraints early, we can avoid exploring huge sections of the tree that would never work, saving massive amounts of computation.
Common Applications
From solving puzzles like Sudoku and N-Queens to finding paths in a maze, backtracking is the go-to strategy for problems involving a sequence of interdependent choices.