Overview
Backtracking is a general algorithmic technique for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems. It incrementally builds candidates for solutions and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Core Concepts
- State-Space Search: Exploring all possible configurations of a problem.
- Pruning: The process of eliminating a branch of the search tree early if it’s clear it won’t lead to a solution. This is what makes backtracking more efficient than brute-force.
- Recursive Exploration: typically implemented via recursion.
- The Backtracking Cycle:
- Choose: Pick a potential option.
- Explore: Recursively try to solve the rest of the problem.
- Un-choose: If the exploration failed, undo the choice (backtrack) and try the next option.
Code Examples
// N-Queens conceptual logic
function solveNQueens(board: number[][], row: number, n: number): boolean {
if (row >= n) return true; // Base case: all queens placed
for (let col = 0; col < n; col++) {
if (isSafe(board, row, col, n)) {
board[row][col] = 1; // Choose
if (solveNQueens(board, row + 1, n)) return true; // Explore
board[row][col] = 0; // Un-choose (Backtrack)
}
}
return false;
}Use Cases
- Combinatorial Problems: Generating all permutations or combinations of a set.
- Puzzles: Solving Sudoku, Crosswords, or the N-Queens problem.
- Maze Solving: Finding a path from start to end in a grid.
Gotchas
- Exponential Time Complexity: In the worst case, backtracking is $O(k^n)$, which is extremely slow. Efficient pruning is critical.
- Stack Overflow: Deep recursion can lead to stack overflow errors.
- Difficult to Debug: Tracking the state of the “un-choose” step across multiple recursive calls can be mentally taxing.