Backtracking Techniques
Open in the Padhaiko app6.1 Basic concepts
Backtracking is a systematic, depth-first search (DFS) algorithmic technique that constructs candidate solutions incrementally, one component at a time, and immediately abandons (prunes) a partial vector as soon as it violates a constraint or cannot possibly lead to a better solution than the best found so far.
State-Space Tree, Constraints, and Bounding Functions
- Explicit Constraints: Rules restricting each variable to take values from a prescribed finite domain (e.g., or ).
- Implicit Constraints: Conditions specifying how tuple components must relate to each other to form a valid solution (e.g., no two queens attack each other, or total weight ).
- State-Space Tree: The rooted tree of all partial and complete tuples defined by the explicit constraints.
- Live Node: A generated node whose children have not all been explored.
- E-Node (Expansion Node): The live node currently being expanded.
- Dead Node: A node whose children are completely explored or which has been killed by a bounding function because it violates an implicit constraint (or cannot beat the current optimum).
void backtrack(int k, int n, int x[]) {
for (each candidate val in domain(k)) {
x[k] = val;
if (isValidBound(x, k)) { // bounding function prunes invalid subtrees
if (k == n) printSolution(x, n);
else backtrack(k + 1, n, x);
}
}
}6.2 The N-Queen problem
The -Queens problem asks to place queens on an chessboard so that no two queens attack each other—no two share the same row, column, or diagonal.
- Tuple Representation: Assign one queen per row: let be the column of the queen placed in row (). This automatically guarantees distinct rows.
- Implicit Constraints (
Place(k, i)): Placing queen in column conflicts with an earlier queen iff:- Same column: , or
- Same diagonal: (slope ).
int canPlace(int x[], int k, int col) {
for (int j = 1; j < k; j++) {
if (x[j] == col || abs(x[j] - col) == abs(j - k))
return 0; // column or diagonal conflict
}
return 1;
}
void nQueens(int k, int n, int x[]) {
for (int col = 1; col <= n; col++) {
if (canPlace(x, k, col)) {
x[k] = col;
if (k == n) printSolution(x, n);
else nQueens(k + 1, n, x);
}
}
}- Complexity: Worst-case nodes explored is , though pruning eliminates most branches early (for , only of tuples are visited before finding all solutions; for , there are solutions).
1
Trace the backtracking search for the -Queens problem () and list all valid solution vectors .
Exploring (Queen 1 in column ):
- cannot be (col) or (diag):
- Try has no valid column ( col/diag with row 1/2; diag with ) backtrack.
- Try is valid, then has no valid column ( blocked by cols, blocked by diag from ) backtrack to root.
Exploring and symmetric branches :
- :
- cannot be only .
- : cols taken, col conflicts diag with .
- : cols taken (no diagonal conflict: , , ). Solution 1: .
- (mirror image of ):
- . Solution 2: .
- (mirror image of ): yields no valid completions.
The -Queens problem has exactly solutions: and .
6.3 Sum of subsets
Given a set of distinct positive integers sorted in non-decreasing order () and a target sum , find all subsets of whose elements sum to .
- Fixed-Size Binary Representation: Let indicate whether is excluded () or included ().
- State Variables at Depth :
- (current partial sum)
- (sum of all remaining weights).
- Bounding Functions (Pruning Rules):
- Left child (, include ) is pruned if (already overshoots target; since weights are sorted, no later single addition can help either).
- Either branch is pruned if (when excluding , remaining weights cannot reach ) or globally if .
6.4 Graph coloring
Given an undirected graph with vertices and colors , the -Coloring problem assigns a color to each vertex so that no two adjacent vertices share the same color:
The minimum for which a valid coloring exists is the chromatic number .
int isSafeColor(int k, int c, int n, int adj[n][n], int x[]) {
for (int j = 0; j < k; j++) {
if (adj[k][j] && x[j] == c) return 0;
}
return 1;
}
void mColoring(int k, int n, int m, int adj[n][n], int x[]) {
for (int c = 1; c <= m; c++) {
if (isSafeColor(k, c, n, adj, x)) {
x[k] = c;
if (k == n - 1) printSolution(x, n);
else mColoring(k + 1, n, m, adj, x);
}
}
}- Time Complexity: At most states in the state-space tree (each of vertices branches ways); Space Complexity: recursion stack + color array.
6.5 Hamiltonian cycles
A Hamiltonian cycle in a graph with vertices is a simple cycle that visits every vertex exactly once and returns to the starting vertex (fixed to vertex to avoid cyclic duplicates).
At step (), NextValue(k) tries vertices satisfying three conditions:
- Edge exists from predecessor: .
- Vertex not yet visited: .
- Cycle closure (only when ): .
- Time Complexity: Worst case (or with fixed); Space Complexity: .
6.6 0/1 knapsack problem using backtracking approach
In Backtracking for 0/1 Knapsack, we first sort items in non-increasing order of value-to-weight ratio (). At each item , we branch on (include, if ) before (exclude), maintaining bestProfit.
Fractional Upper-Bound Function for 0/1 Knapsack Pruning
Given current profit and current weight after deciding items , the maximum profit any completion of the subtree can achieve is bounded above by greedily filling remaining capacity with fractional pieces of items :
Whenever , the entire subtree is pruned immediately.
2
Using the Sum of Subsets backtracking algorithm with pruning rules and , find all subsets of that sum to .
Root initialization: Sorted weights: , total remaining sum , initial , .
Tracing left-first (include) and right (exclude) branches:
- Include (, ):
- Include (, ):
- Include (, ): next weight gives (prune include ). Exclude check remaining.
- Exclude (, ): include () (prune). Exclude (, ): include ()! Solution 1: .
- Exclude (, ):
- Include (, ): include ()! Solution 2: .
- Exclude (, ): , (pruned).
- Exclude (, ): max possible with , , , , , (none ).
- Include (, ):
- Exclude (, ):
- Include : , (), , (), (none).
- Exclude (, ): include (, ): (next ), exclude , include ()! Solution 3: .
- Exclude (, ): remaining combinations , , (none ).
The subsets summing to are , , and (binary vectors , , and ).
3
Solve the 0/1 Knapsack problem using Backtracking with upper-bound pruning for capacity and items already sorted by :
- Item 1: ()
- Item 2: ()
- Item 3: ()
- Item 4: ()
Root and left branch (Item 1 included, Item 2 included):
- Root ():
Bound. - Include Item 1 ():
Bound.- Include Item 2 ():
Bound.- Include Item 3? (infeasible — pruned).
- Exclude Item 3 ():
- Include Item 4 (): leaf! Update
bestProfit = 80(). - Exclude Item 4 ():
Bound = 70 <= 80(pruned).
- Include Item 4 (): leaf! Update
- Include Item 2 ():
Backtracking to exclude Item 2 and exclude Item 1:
- Exclude Item 2 after Item 1 ():
Boundusing Items 3, 4 (explore!).- Include Item 3 ():
Bound.- Include Item 4? (infeasible — pruned).
- Exclude Item 4 (): leaf! Update
bestProfit = 90().
- Exclude Item 3 ():
Bound(pruned).
- Include Item 3 ():
- Exclude Item 1 at root ():
Boundusing Items 2, 3, 4 (entire right half of tree pruned immediately!).
Optimal 0/1 Knapsack selection: Items and (, total weight ) with maximum profit .
Exercises
Exercises — Backtracking Techniques
Distinguish between explicit constraints and implicit constraints in backtracking. Define live node, E-node, dead node, and bounding function, and explain why backtracking can outperform exhaustive brute-force search despite having the same worst-case complexity.
Explicit vs. Implicit Constraints and Tree Nodes:
- Explicit Constraints define the valid domain for each component independently (e.g., ), forming the static state-space tree.
- Implicit Constraints specify relationships among components (e.g., or ) that determine whether a path represents a feasible solution.
- A live node has unexplored children; the E-node is the live node currently expanding; a dead node has no more children to explore or was killed early.
Bounding Functions and Practical Speedup: A bounding function tests whether a partial tuple violates an implicit constraint or has an upper bound worse than the current best solution. Whenever it fails, the entire subtree rooted at that node is pruned without generation, cutting down practical runtime dramatically even though the worst-case bound remains exponential.
Explicit constraints restrict individual variable domains; implicit constraints govern cross-variable feasibility. A bounding function turns infeasible or non-improving live/E-nodes into dead nodes, pruning whole subtrees to outperform brute force in practice.
Write the exact conflict condition used in the -Queens backtracking algorithm to test whether placing a queen in row , column conflicts with an earlier queen in row (). Verify whether is a valid solution to the -Queens problem.
Conflict condition: Queen conflicts with queen iff (same column) or (same diagonal).
Checking for :
- All column values are distinct (no column conflicts).
- Check all pairs for diagonal conflict :
- : ; : ; : ; :
- : ; : ; :
- : ; :
- : .
No pair shares a diagonal.
Conflict condition: or . The tuple has distinct columns and zero diagonal conflicts, so it is a valid -Queens solution.
Using the Sum of Subsets backtracking method with and target sum , trace the search tree (showing pruned branches) to find all subsets summing to .
Tracing with (current sum) and (remaining sum, initially ):
- Include ():
- Include ():
- Include (): include (pruned); exclude : (dead).
- Exclude (): include ()! Solution: .
- Exclude (): :
- Include (): include (pruned).
- Exclude (): (pruned by ).
- Include ():
- Exclude ():
- Include (): ; (); (no solution).
- Exclude (): (pruned immediately).
There is subset summing to : (solution vector ).
Consider the -vertex graph with vertices and edges .
- Using the -Coloring backtracking algorithm with colors , find the lexicographically first valid coloring , and determine the chromatic number .
- Find a Hamiltonian cycle in starting at vertex using backtracking.
Graph -Coloring trace:
- .
- : adjacent to , so smallest valid color is .
- : adjacent to both and (triangle ), so smallest valid color is .
- : adjacent to (color ) and (color ), not adjacent to , so smallest valid color is .
Because contains triangle , colors are impossible, so .
Hamiltonian Cycle from vertex :
- .
- Try neighbor (edge ).
- From , try (edge ).
- From , try (edge ).
- At , check closing edge — exists!
Valid Hamiltonian cycle: .
- Lexicographically first -coloring: ; chromatic number .
- Hamiltonian cycle: .
Solve the 0/1 Knapsack problem using Backtracking with upper-bound pruning for capacity and items sorted by profit-to-weight ratio:
- Item 1: ()
- Item 2: ()
- Item 3: ()
- Item 4: ()
Exploring with Item 1 included ():
- Root bound .
- Include Item 1 ():
- Include Item 2? (infeasible — pruned).
- Exclude Item 2 ():
Bound.- Include Item 3 ():
- Include Item 4? (pruned).
- Exclude Item 4 (): leaf!
bestProfit = 65().
- Exclude Item 3 ():
Bound(pruned).
- Include Item 3 ():
Exploring with Item 1 excluded (): Bound using Items 2, 3, 4 . Because the upper bound () is already less than bestProfit = 65, the entire right branch (excluding Item 1) is pruned without expanding any nodes!
Optimal selection: Items and (, weight ) with maximum profit .