Unit 6: Backtracking

I. Foundations of Backtracking

Backtracking is a systematic algorithm-design technique for solving constraint-satisfaction and combinatorial search problems. It constructs a solution incrementally and abandons a partial candidate as soon as that candidate cannot lead to a valid complete solution.

• Governing principle: Search the state-space tree depth-first, applying constraints early to eliminate unproductive branches.
• Candidate solution: A sequence (x_1,x_2,\ldots,x_k) representing decisions made through level (k).
• State-space tree: A rooted tree in which:
  • The root represents an empty solution.
  • Each edge represents a choice.
  • A node at level (k) represents (k) completed choices.
  • A leaf represents either a complete solution or a dead end.
• Promising node: A partial solution that satisfies all constraints checked so far and may still extend to a complete solution.
• Non-promising node: A partial solution that violates a constraint or cannot possibly be completed; its entire subtree is pruned.
• Backtracking step: Undo the most recent choice when no valid continuation exists, then try the next available choice.
• Search order: Standard backtracking uses depth-first search, so its auxiliary storage is generally proportional to the maximum recursion depth rather than the total number of states.
• Problem requirements: Backtracking is most useful when:
  • A solution consists of a sequence of discrete choices.
  • Constraints can be tested on partial solutions.
  • Exhaustive enumeration would generate many invalid candidates.
• Core distinction: Brute force generates complete candidates before testing them, whereas backtracking rejects invalid candidates during construction.

II. General Method — Systematic Constraint-Guided Search

A. General method

The general method chooses one candidate at a time, tests whether the resulting partial solution is promising, and recursively continues or reverses the choice.

• Recursive structure: A generic backtracking procedure has a choose–explore–unchoose cycle.

BACKTRACK(state, level):
    if state is a complete solution:
        report state
        return

    for each candidate c available at level:
        choose c and add it to state

        if PROMISING(state, level):
            BACKTRACK(state, level + 1)

        remove c from state

• state is the current partial solution.
• level is the next decision position.
• c is one candidate choice.
• PROMISING tests whether the partial solution can remain valid.

• Implicit constraints: These define the basic form of a candidate; for example, selecting one column for each row in the queens problem.
• Explicit constraints: These determine whether a candidate is acceptable; for example, requiring that no two queens share a diagonal.
• Feasibility test: It prevents recursion whenever a newly added choice conflicts with an earlier choice.
• Solution objectives:
  1. Decision version: Stop after finding one solution, such as determining whether a Hamiltonian cycle exists.
  2. Enumeration version: Continue after each solution to generate all solutions, such as listing every valid coloring.
• Search-tree cost: If level (i) offers at most (b_i) choices, exhaustive exploration may visit approximately

1 + b₁ + b₁b₂ + ... + b₁b₂...bₙ

where (n) is the number of decisions and (b_i) is the branching factor at level (i).

• Pruning effectiveness: Runtime depends strongly on how early PROMISING detects failure; a stronger inexpensive test usually reduces the explored tree substantially.
• Worked example: To choose three distinct values from ({1,2,3}), the partial state ([2,2]) is rejected immediately by a distinctness test instead of generating ([2,2,1]) and ([2,2,3]).

B. Applications and limitations

Backtracking provides exact solutions to many finite search problems, but its worst-case cost commonly remains exponential.

• Applications: Typical uses include permutations, subset selection, scheduling, puzzles, graph traversal under constraints, and constraint-satisfaction problems.
• Correctness basis:
  • Every legal choice is considered at its decision level.
  • Only partial states that cannot yield a valid answer are pruned.
  • Therefore, every valid complete solution remains reachable.
• Time limitation: If pruning rarely succeeds, the method approaches exhaustive search; (n) binary choices can produce (2^n) complete candidates.
• Space advantage: A depth-first implementation stores one active path plus recursion data, often requiring (O(n)) auxiliary space for depth (n).
• Heuristic improvement: Trying the most constrained decision first can expose contradictions earlier without changing correctness.
• Boundary condition: Pruning must be logically safe; rejecting a state that still has a valid completion makes the algorithm incomplete.

III. The 8-Queens Problem — Nonattacking Placement

A. The 8-queens problem

The 8-queens problem asks for eight queens to be placed on an (8\times8) chessboard so that no two queens attack each other.

• Representation: Let (x_i) denote the column containing the queen in row (i), where (1\leq i\leq8) and (1\leq x_i\leq8).
• Row constraint: Exactly one queen is placed in each row by construction.
• Column constraint: Queens in rows (i) and (j) must satisfy (x_i\neq x_j).
• Diagonal constraint: Two queens share a diagonal precisely when

|xᵢ - xⱼ| = |i - j|

where (i,j) are row numbers and (x_i,x_j) are their selected columns.

• Promising condition: A queen proposed at ((k,c)) is valid if, for every earlier row (i<k),

xᵢ ≠ c  and  |xᵢ - c| ≠ |i - k|

where (k) is the current row and (c) is the proposed column.

• Algorithm:

PLACE(row):
    if row = 9:
        report x[1..8]
        return

    for column = 1 to 8:
        if column is safe for row:
            x[row] = column
            PLACE(row + 1)
            clear x[row]

• Worked example: If queens occupy ((1,1)) and ((2,3)), column (5) is invalid for row (3), because (|5-3|=|3-2|=2) is false, but against ((1,1)), (|5-1|=4\neq2); checking all earlier queens is essential. By contrast, ((3,2)) conflicts diagonally with ((2,3)) because both differences equal (1).

B. Efficiency and significance

The problem illustrates how a compact representation and immediate conflict detection reduce a large board search to a constrained permutation search.

• Reduced search: Fixing one queen per row removes row conflicts; forbidding reused columns limits complete candidates to at most (8!), rather than considering arbitrary sets of 8 among 64 squares.
• Generalization: For the (N)-queens problem, the same rules use an array (x[1..N]).
• Worst-case time: A permutation-based search has an (O(N!)) upper bound, although diagonal pruning usually eliminates many nodes.
• Auxiliary space: The placement array and recursion stack require (O(N)) space.
• Faster safety checks: Boolean arrays can record occupied columns and the diagonals indexed by (r-c) and (r+c), making each safety test (O(1)).
• Limitation: Symmetric rotations and reflections may produce equivalent arrangements unless the algorithm explicitly removes symmetric duplicates.

IV. Graph Coloring — Assigning Compatible Vertex Colors

A. Graph coloring

Graph coloring assigns at most (m) colors to the vertices of a graph so that adjacent vertices receive different colors.

• Input: For a graph (G=(V,E)), (V) is the vertex set, (E) is the edge set, and (m) is the maximum number of available colors.
• Assignment: Let color[v] be an integer from (1) to (m) for vertex (v); zero may represent “uncolored.”
• Validity condition: For every edge ((u,v)\in E),

color[u] ≠ color[v]

• Backtracking order: Assign colors to vertices (v_1,v_2,\ldots,v_n), where (n=|V|), and reject a color if an already colored neighbor has that color.
• Algorithm:

COLOR(k):
    if k > n:
        report color[1..n]
        return true

    for c = 1 to m:
        if no colored neighbor of vₖ has color c:
            color[vₖ] = c
            if COLOR(k + 1): return true
            color[vₖ] = 0

    return false

• (k) is the current vertex position.
• (c) is a candidate color.
• Returning immediately finds one coloring; removing the early return enumerates all colorings.

• Worked example: A triangle (K_3) cannot be colored with (m=2): after assigning colors 1 and 2 to two adjacent vertices, the third vertex is adjacent to both and has no legal color. With (m=3), assigning colors (1,2,3) succeeds.

B. Complexity and applications

Graph-coloring backtracking is exact, but its efficiency depends on vertex order and graph structure.

• Worst-case time: Each of (n) vertices may try (m) colors, giving (O(m^n)) candidate assignments.
• Space use: The color array and recursion depth require (O(n)) auxiliary space, excluding graph storage.
• Ordering heuristic: Coloring a high-degree or highly constrained vertex first often causes earlier rejection.
• Applications: Concrete models include examination timetabling, register allocation, frequency assignment, and conflict-free resource scheduling.
• Chromatic number: The minimum feasible (m) is (\chi(G)); repeated feasibility tests for different values of (m) can determine it.
• Limitation: Finding an optimal coloring is computationally difficult for general graphs, so large instances often require bounds or heuristics.

V. Hamiltonian Cycles — Visiting Every Vertex Exactly Once

A. Hamiltonian cycles

A Hamiltonian cycle in (G=(V,E)) is a simple cycle that visits every vertex exactly once and returns to its starting vertex.

• Path representation: path[0..n−1] stores a permutation of all (n=|V|) vertices, usually with path[0] fixed to one starting vertex.
• Distinctness condition: A candidate vertex must not already occur in path.
• Adjacency condition: For position (k>0), edge ((path[k-1],path[k])) must belong to (E).
• Closure condition: After all vertices are placed, ((path[n-1],path[0])) must also belong to (E).
• Algorithm:

HAM(k):
    if k = n:
        return edge(path[n-1], path[0]) exists

    for each unused vertex v:
        if edge(path[k-1], v) exists:
            path[k] = v
            if HAM(k + 1): return true
            remove v from path[k]

    return false

• (k) is the next path position.
• (v) is an unused candidate vertex.
• (n) is the number of vertices.

• Worked example: In the cycle graph with edges (AB,BC,CD,DA), the sequence (A,B,C,D,A) is Hamiltonian because every consecutive pair is adjacent and each of (A,B,C,D) occurs once before returning to (A).

B. Complexity and limitations

Backtracking avoids permutations containing missing edges, but difficult graphs may still require factorial search.

• Worst-case time: Fixing the starting vertex leaves up to ((n-1)!) orderings, so the upper bound is (O(n!)).
• Auxiliary space: The path, used-vertex markers, and recursion stack require (O(n)) space.
• Pruning: Rejecting nonadjacent candidates immediately prevents completion of impossible path prefixes.
• Symmetry reduction: Fixing the first vertex removes rotational duplicates; treating a cycle and its reverse as equivalent can halve duplicate output in undirected graphs.
• Distinction from Eulerian cycles: A Hamiltonian cycle visits every vertex once, whereas an Eulerian cycle traverses every edge once.
• Applications: The model supports routing, sequencing, circuit design, and the decision form underlying the traveling salesperson problem.
• Limitation: No simple local condition guarantees a Hamiltonian cycle in every graph, and the general decision problem is NP-complete.