PadhaikoAll subjects

Backtracking Techniques

Analysis of Algorithms (ENCT 388)

Open in the Padhaiko app

6.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.

Definition

State-Space Tree, Constraints, and Bounding Functions

General Recursive Backtracking SchemaC
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.

N-Queens Backtracking AlgorithmC
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);
        }
    }
}
Example 1

1 (5 marks)

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.
Answer:

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 .


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 .

Graph m-Coloring via BacktrackingC
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);
        }
    }
}

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:

  1. Edge exists from predecessor: .
  2. Vertex not yet visited: .
  3. Cycle closure (only when ): .

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.

Definition

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.

Example 2

2 (6 marks)

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 ).
  • Exclude (, ):
    • Include : , (), , (), (none).
    • Exclude (, ): include (, ): (next ), exclude , include ()! Solution 3: .
    • Exclude (, ): remaining combinations , , (none ).
Answer:

The subsets summing to are , , and (binary vectors , , and ).

Example 3

3 (7 marks)

Solve the 0/1 Knapsack problem using Backtracking with upper-bound pruning for capacity and items already sorted by :

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).

Backtracking to exclude Item 2 and exclude Item 1:

  • Exclude Item 2 after Item 1 (): Bound using 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).
  • Exclude Item 1 at root (): Bound using Items 2, 3, 4 (entire right half of tree pruned immediately!).
Answer:

Optimal 0/1 Knapsack selection: Items and (, total weight ) with maximum profit .


Exercises

Exercises — Backtracking Techniques

Question 1

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.

Answer:

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.

Question 2

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.

Answer:

Conflict condition: or . The tuple has distinct columns and zero diagonal conflicts, so it is a valid -Queens solution.

Question 3

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 ).
  • Exclude ():
    • Include (): ; (); (no solution).
    • Exclude (): (pruned immediately).
Answer:

There is subset summing to : (solution vector ).

Question 4

Consider the -vertex graph with vertices and edges .

  1. Using the -Coloring backtracking algorithm with colors , find the lexicographically first valid coloring , and determine the chromatic number .
  2. 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: .

Answer:
  1. Lexicographically first -coloring: ; chromatic number .
  2. Hamiltonian cycle: .
Question 5

Solve the 0/1 Knapsack problem using Backtracking with upper-bound pruning for capacity and items sorted by profit-to-weight ratio:

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).

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!

Answer:

Optimal selection: Items and (, weight ) with maximum profit .

← Dynamic ProgrammingNP-Hard and NP-Complete Problems →