Backtracking and Constraint Search

Backtracking is search with an undo. You commit to a choice, recurse, and if the choice cannot lead anywhere valid you unwind it and try the next. Described that way it sounds simple; written as recursive code with a mutable state that has to be restored precisely, it is a common source of confusion.

This is the topic where watching execution helps most, because the shape of the algorithm is a tree being walked and pruned. Seeing N-Queens place a queen, hit a conflict several rows later and unwind makes the undo step concrete, and the same structure then reads clearly in subsets, permutations and Sudoku.