Backtracking
debt(d7/e5/b3/t5)
Closest to 'only careful code review or runtime testing' (d7) — detection_hints lists xdebug/blackfire profilers and marks automated:no, so missing pruning or un-undone state surfaces only via runtime profiling or review.
Closest to 'touches multiple files / significant refactor' (e5) — quick_fix says add base cases and prune early, but fixing a flawed backtracking algorithm (state undo, pruning logic, termination) typically means restructuring the recursive routine, more than a one-line patch (e3) but contained in one component.
Closest to 'localised tax' (b3) — applies_to web/cli but the algorithm itself is component-local; it doesn't impose system-wide gravity, just a tax on the module that uses it.
Closest to 'notable trap most devs eventually learn' (t5) — misconception ('just brute force') and common_mistakes (forgetting to undo state, missing early termination) are documented gotchas, not catastrophic inversions of behaviour.
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
}