backtracking
Backtracking is a systematic way to search through all the ways of building something — a placement, an arrangement, a path — by extending a partial solution one choice at a time, abandoning a line the moment it can't possibly work, and undoing the last choice to try another. The mental image is exploring a maze while trailing a thread: you push forward down a corridor, and the instant you hit a dead end you walk back to the last junction and try a different door. Crucially, you erase your last step as you retreat — that undo is what the word backtrack literally means.
Three actions form the loop: choose (make the next decision), explore (recurse to extend the solution), and un-choose (undo the decision so the next sibling choice starts from a clean slate). What makes backtracking far better than blind brute force is pruning: at each partial step you check the constraints, and if the partial solution already violates them you cut off that whole branch without exploring any of its descendants. In the N-queens problem you place queens column by column and abandon a column the moment a queen would attack one already placed — sparing yourself the vast subtree below.
Backtracking is the engine behind generating all permutations or subsets, solving Sudoku and crosswords, the N-queens puzzle, and constraint-satisfaction problems in general. Its honest cost is exponential in the worst case — it is, after all, exploring a search tree that can be enormous — so its practicality rests entirely on how aggressively the constraints let you prune. Good pruning is the difference between a solution that returns in milliseconds and one that never returns at all.
void permute(vector<int>& a, int k) {
if (k == a.size()) { record(a); return; } // a full arrangement
for (int i = k; i < a.size(); ++i) {
swap(a[k], a[i]); // choose
permute(a, k + 1); // explore
swap(a[k], a[i]); // un-choose (backtrack)
}
}The swap-then-swap-back pattern is the choose / explore / un-choose loop in miniature.
Backtracking is depth-first search over a tree of partial solutions, with the extra step of undoing each choice on the way back up. Without pruning it degenerates into exhaustive brute force; the constraint checks that let you abandon doomed branches early are what give it its power.