Backtracking

Backtracking builds candidate solutions incrementally and abandons a partial candidate as soon as it cannot be completed.

Try, and undo

Backtracking is a refined brute force. It builds a solution one choice at a time and, whenever the current partial solution cannot possibly be extended to a valid full solution, it undoes the last choice and tries another. This early abandonment, called pruning, is what separates backtracking from exhaustively enumerating every candidate.

The search tree

Conceptually, backtracking explores a tree of partial solutions with a depth-first search. Each node is a partial assignment, and children extend it by one more choice. Pruning cuts off entire subtrees whose root already violates a constraint, so the effective search can be far smaller than the full tree.

• Extend a partial solution by one choice
• Check constraints; prune if the partial cannot be completed
• Recurse; on failure, undo the choice and try the next
• Report or count full solutions when reached

def solve_nqueens(n):
    cols, d1, d2, sols = set(), set(), set(), []
    def place(r, cur):
        if r == n:
            sols.append(cur[:]); return
        for c in range(n):
            if c in cols or (r-c) in d1 or (r+c) in d2:
                continue
            cols.add(c); d1.add(r-c); d2.add(r+c); cur.append(c)
            place(r+1, cur)
            cols.remove(c); d1.remove(r-c); d2.remove(r+c); cur.pop()
    place(0, [])
    return sols

Pruning is everything

Without pruning, backtracking degrades into checking every candidate, which is exponential. The techniques that make it practical are constraint propagation, which narrows future choices after each decision; the most-constrained-variable heuristic, which assigns the tightest variable first to fail fast; and bounding, which abandons a branch once a partial cost proves it cannot beat the best solution found so far, the idea behind branch and bound.

Where it is used

Backtracking solves constraint problems like the N-queens puzzle, Sudoku, graph colouring, and the boolean satisfiability problem. It is also the engine behind generating permutations and combinations and behind regular-expression matching. Its worst case can be exponential, so good pruning, constraint ordering, and choosing the most constrained variable first are what make it practical on real inputs.