Backtracking
Backtracking is an algorithmic technique for solving constraint satisfaction and combinatorial problems by incrementally building a solution and abandoning (backtracking from) a partial solution as soon as it is determined to violate the problem constraints, then trying the next possibility. It is essentially a depth-first search through the space of candidate solutions, pruning branches that cannot lead to a valid solution. Backtracking is used to solve N-Queens, Sudoku, crossword puzzles, subset-sum, and graph coloring problems.
Backtracking Problem Examples and Complexity
| Problem | State Space | Pruning Strategy | Worst Case |
|---|---|---|---|
| N-Queens | n^n placements | Row/column/diagonal conflicts | O(n!) |
| Sudoku | 9^81 cells | Row/col/box constraint checks | O(9^81) naive |
| Subset Sum | 2^n subsets | Sum exceeds target | O(2^n) |
| Graph Coloring | k^V colorings | Adjacent same-color check | O(k^V) |
| Hamiltonian Path | V! paths | Revisit check | O(V!) |
Interactive Tools
Khan Academy – Algorithms
Foundational algorithms course covering recursive and backtracking strategies
Open Tool
Wikimedia Commons, CC BY-SA
Related Terms
Depth-First Search
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking, using a stack (either explicit or via recursion) to track the path. It is fundamental in computer science for solving problems involving connected components, cycle detection, and pathfinding. DFS is widely used in topological sorting, maze generation, and solving puzzles like Sudoku.
Recursion
Recursion is a programming and mathematical technique in which a function calls itself with a smaller or simpler version of the original problem, progressing toward one or more base cases that terminate the chain of calls. Every recursive solution requires a base case (stopping condition) and a recursive case (self-referential reduction). Recursion is fundamental to tree traversal, divide-and-conquer algorithms, backtracking, and functional programming.
Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
The term "backtracking" was coined by American mathematician D.H. Lehmer in the 1950s. The word combines "back" (Old English bæc) and "track" (Middle English trak), meaning to retrace one's path. The systematic formalization of backtracking as an algorithmic technique was developed by Robert Floyd and others in the 1960s.