Backtracking

Also Known As

TL;DR

Explanation

Backtracking is a refined brute force: try a candidate, check constraints, recurse, and undo the choice if it leads to a dead end. Classic problems: N-Queens, Sudoku solver, permutations/combinations, maze solving, and constraint satisfaction. The key insight: pruning invalid branches early avoids exploring the full exponential search space. Backtracking is the basis for many combinatorial optimisation algorithms.

Common Misconception

Why It Matters

Common Mistakes

• Not undoing state changes when backtracking — the undo step is as important as the do step.
• Pruning too aggressively — checking invalid constraints costs time; only prune when the check is cheap relative to the avoided search.
• Using backtracking when dynamic programming applies — overlapping subproblems are better solved with DP.
• No early termination when the first valid solution is found — continue searching unnecessarily.

Code Examples

// Brute force permutations — generates all then filters:
function permutations(array $arr): array {
    if (count($arr) <= 1) return [$arr];
    $result = [];
    foreach ($arr as $i => $val) {
        $rest = array_values(array_filter($arr, fn($k) => $k !== $i, ARRAY_FILTER_USE_KEY));
        foreach (permutations($rest) as $perm) $result[] = array_merge([$val], $perm);
    }
    return $result; // Generates all n! then caller filters — wasteful
}

// Backtracking Sudoku solver — prunes invalid choices early:
function solveSudoku(array &$board): bool {
    foreach ($board as $r => $row) {
        foreach ($row as $c => $cell) {
            if ($cell !== 0) continue;
            for ($num = 1; $num <= 9; $num++) {
                if (isValid($board, $r, $c, $num)) {
                    $board[$r][$c] = $num;
                    if (solveSudoku($board)) return true; // Recurse
                    $board[$r][$c] = 0; // Backtrack — undo the choice
                }
            }
            return false; // No valid number — backtrack further
        }
    }
    return true; // All cells filled
}

References

• ↗ https://en.wikipedia.org/wiki/Backtracking

Tags

Related Terms