Backtracking is a fundamental algorithmic technique used to solve combinatorial problems by exploring all potential solutions in a systematic manner. It incrementally builds candidates for the solutions and abandons a candidate ("backtracks") as soon as it determines that this candidate cannot possibly lead to a final solution.
What is Backtracking?
In backtracking, the problem space is represented as a tree where each node corresponds to a partial solution. The algorithm performs a depth‑first search (DFS) on this tree, pruning branches that violate constraints, thereby avoiding exhaustive enumeration of all possibilities.
When to Use Backtracking
- Problems that require generating all possible configurations (e.g., permutations, subsets).
- Constraint satisfaction problems such as Sudoku, N‑Queens, and graph coloring.
- Search problems where a solution can be constructed incrementally and early failure detection is possible.
Core Principles
- Choose a candidate for the next step.
- Check if the candidate satisfies the problem constraints.
- If it does, recurse to the next level with the extended partial solution.
- If it does not, discard the candidate and try the next one.
- When a complete solution is found, record or output it.
- Backtrack to explore alternative candidates.
Common Patterns
- Recursive function that accepts the current state and the index/level of recursion.
- A
forloop that iterates over all possible choices at the current level. - A
isSafeorisValidhelper that implements constraint checking. - Undo/restore operations (often called "backtrack") after recursive calls to revert the state.
Implementation in Python
def solve_n_queens(n):
solutions = []
board = [-1] * n # board[i] = column of queen in row i
def is_safe(row, col):
for prev_row in range(row):
prev_col = board[prev_row]
# same column or same diagonal
if prev_col == col or abs(prev_col - col) == abs(prev_row - row):
return False
return True
def backtrack(row):
if row == n:
# a complete solution is found; store a copy
solutions.append(board.copy())
return
for col in range(n):
if is_safe(row, col):
board[row] = col
backtrack(row + 1)
board[row] = -1 # undo
backtrack(0)
return solutions
# Example usage
for sol in solve_n_queens(4):
print(sol)Implementation in C++
#include <iostream>
#include <vector>
using namespace std;
bool isSafe(const vector<int>& board, int row, int col) {
for (int prev = 0; prev < row; ++prev) {
int prevCol = board[prev];
if (prevCol == col || abs(prevCol - col) == abs(prev - row))
return false;
}
return true;
}
void backtrack(int n, int row, vector<int>& board, vector<vector<int>>& solutions) {
if (row == n) {
solutions.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (isSafe(board, row, col)) {
board[row] = col;
backtrack(n, row + 1, board, solutions);
board[row] = -1; // undo
}
}
}
vector<vector<int>> solveNQueens(int n) {
vector<int> board(n, -1);
vector<vector<int>> solutions;
backtrack(n, 0, board, solutions);
return solutions;
}
int main() {
int n = 4;
auto sols = solveNQueens(n);
for (const auto& sol : sols) {
for (int col : sol) cout << col << " ";
cout << "\n";
}
return 0;
}Implementation in Java
import java.util.*;
public class NQueensBacktrack {
private static boolean isSafe(int[] board, int row, int col) {
for (int i = 0; i < row; i++) {
int placedCol = board[i];
if (placedCol == col || Math.abs(placedCol - col) == Math.abs(i - row)) {
return false;
}
}
return true;
}
private static void backtrack(int n, int row, int[] board, List<int[]> solutions) {
if (row == n) {
solutions.add(board.clone());
return;
}
for (int col = 0; col < n; col++) {
if (isSafe(board, row, col)) {
board[row] = col;
backtrack(n, row + 1, board, solutions);
board[row] = -1; // undo
}
}
}
public static List<int[]> solveNQueens(int n) {
List<int[]> solutions = new ArrayList<>();
int[] board = new int[n];
Arrays.fill(board, -1);
backtrack(n, 0, board, solutions);
return solutions;
}
public static void main(String[] args) {
int n = 4;
List<int[]> sols = solveNQueens(n);
for (int[] sol : sols) {
System.out.println(Arrays.toString(sol));
}
}
}Complexity Analysis
The time complexity of backtracking depends on the size of the search tree. In the worst case it is O(b^d), where b is the branching factor (maximum number of choices per level) and d is the depth of the recursion (size of the solution). Pruning can dramatically reduce the effective branching factor.
| Problem | Typical Branching Factor (b) | Depth (d) | Worst‑Case Time | Space (recursion) |
|---|---|---|---|---|
| N‑Queens | n | n | O(n!) | O(n) |
| Sudoku Solver | 9 | 81 | O(9^81) (pruned heavily) | O(81) |
| Subset Sum | 2 | n | O(2^n) | O(n) |
Practical Applications
- Puzzle solvers (Sudoku, Kakuro, crossword generation).
- Combinatorial generation (permutations, combinations, partitions).
- Graph problems (Hamiltonian Path, Hamiltonian Cycle, Hamiltonian Circuit).
- Resource allocation and scheduling where constraints are tight.
Backtracking is not a silver bullet; its power lies in the ability to prune infeasible branches early, turning exponential blow‑up into a tractable search for many real‑world instances.
isSafe check as efficiently as possible. Even a small constant‑time improvement can have a huge impact on overall runtime.Q: How does backtracking differ from simple brute‑force?
A: Brute‑force blindly enumerates every possible configuration, while backtracking prunes branches as soon as a constraint violation is detected, reducing the search space dramatically.
Q: Can backtracking be parallelized?
A: Yes. Independent branches of the search tree can be explored in parallel, but care must be taken to manage shared resources and avoid duplicate work.
Q: When should I prefer dynamic programming over backtracking?
A: If the problem exhibits overlapping sub‑problems and optimal substructure, DP usually offers polynomial‑time solutions, whereas backtracking may remain exponential.
Q. Which of the following statements about backtracking is true?
- It always runs in polynomial time.
- It explores the solution space in a breadth‑first manner.
- It can prune the search tree using constraint checks.
- It never uses recursion.
Answer: It can prune the search tree using constraint checks.
Pruning is the core advantage of backtracking; the other statements are false.
Q. In the N‑Queens problem, what is the maximum number of recursive calls for a board of size n?
- n!
- 2^n
- n^2
- n * (n‑1) / 2
Answer: n!
In the worst case each row tries every column, leading to n * (n‑1) * … * 1 = n! possibilities.