Backtracking

Applies to: general, python

Backtracking builds a candidate one choice at a time and undoes a choice as soon as it cannot lead to a solution. It explores all valid combinations without repeating work, and is the skeleton behind subsets, permutations, and constraint puzzles like N-queens.

def solve(path):
    if done(path): record(path); return
    for choice in options(path):
        path.append(choice); solve(path); path.pop()

See also: recursion, depth-first-search