Backtracking

Some problems do not reveal which early choice belongs to a solution. A greedy commitment may be unsafe, and enumerating every complete possibility wastes time on partial candidates that are already impossible. Backtracking occupies the space between those extremes: build a candidate one choice at a time, abandon it as soon as it violates a constraint, and undo the choice so another branch can be explored.

Backtracking is exhaustive search with memory and discipline. In the worst case it may still inspect exponentially or factorially many states. Its value is that most real instances contain constraints that make large regions of the conceptual search space provably irrelevant.

Search Trees

A search tree is a conceptual tree, not necessarily a data structure stored in memory.

• The root represents an empty candidate.
• A node represents a partial candidate.
• An edge represents one permitted next choice.
• A leaf represents a complete candidate or a state with no legal continuation.

For permutations of {A, B, C}, the tree begins:

                         []
             /            |            \
           [A]           [B]           [C]
          /   \          /   \          /   \
      [A,B] [A,C]    [B,A] [B,C]    [C,A] [C,B]
        |     |        |     |        |     |
      ABC   ACB      BAC   BCA      CAB   CBA

The algorithm normally stores only the current root-to-node path. Recursion supplies the depth-first control flow; mutable arrays record the current candidate. Thus a search tree with millions of conceptual nodes may need memory proportional only to its depth.

Candidate States

A correct state contains exactly the information needed to answer three questions:

1. Is the current partial candidate still feasible?
2. Is it complete?
3. Which choices are legal next?

For N-Queens, a candidate can be column[row]: the column occupied by the queen already placed in each earlier row. A separate Boolean array for occupied columns and diagonals answers legality quickly. For subset sum, the state may include the next item index, current sum, and selected-item flags. For Sudoku, it includes the grid plus the used digits in each row, column, and box.

State that omits relevant history can accept invalid solutions. State that records irrelevant history creates unnecessarily many distinct subproblems and makes both reasoning and optimization harder.

Search Template

The general pattern is:

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

    choose an unresolved decision
    for each candidate choice:
        if choice is feasible:
            apply choice
            BACKTRACK(state)
            undo choice

The three verbs—choose, explore, undo—are the operational core. A decision made for one branch must not leak into its sibling.

Constraint Checks

A constraint identifies partial states that cannot extend to a valid complete solution. Check constraints as early as correctness permits.

Suppose we generate four-digit codes with distinct digits whose first digit cannot be zero. Filtering all 10,000 complete strings works, but enforcing “first digit nonzero” at depth one and “unused digit” at every depth avoids generating invalid descendants at all.

State Restoration

There are two implementation styles:

• Copy state: construct a fresh state for each child. Reasoning is simple, but copying can be expensive.
• Mutate and undo: change shared state, recurse, then reverse exactly that change. This is fast and common in C, but every return path must restore the invariant.

Keep the mutation and its inverse visibly paired:

used[value] = true;               /* choose */
permutation[depth] = value;
generate(depth + 1);              /* explore */
used[value] = false;              /* undo */

If recursion can return early after finding one solution, decide whether restoration is still required by the caller. A robust pattern restores before propagating success.

Pruning

Pruning removes a subtree only after proving that it cannot contain an answer of interest.

Three common forms are:

1. Feasibility pruning: a hard constraint is already violated, as when two queens attack each other.
2. Bound pruning: even the best possible completion cannot improve the best solution known.
3. Dominance pruning: another previously explored state is at least as good in every relevant respect.

Pruning changes performance, not the mathematical answer. An unsafe prune silently destroys completeness. Every pruning rule deserves its own small proof: if predicate P(state) triggers, then no descendant of that state can satisfy the goal or improve the incumbent.

Permutation Search

Problem. Generate every permutation of n distinct integers exactly once.

The baseline enumerates n^n length-n sequences and rejects repeats. Backtracking enforces uniqueness while building the sequence, producing only the n! valid leaves.

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

static void print_permutation(const int values[], size_t n) {
    for (size_t i = 0; i < n; ++i) {
        printf("%d%c", values[i], i + 1 == n ? '\n' : ' ');
    }
}

static void permute_visit(const int input[], size_t n, size_t depth,
                          int output[], bool used[]) {
    if (depth == n) {
        print_permutation(output, n);
        return;
    }

    for (size_t i = 0; i < n; ++i) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        output[depth] = input[i];
        permute_visit(input, n, depth + 1, output, used);
        used[i] = false;
    }
}

Invariant. On entry at depth d, output[0..d-1] contains d distinct input elements, and used[i] is true exactly when input[i] occurs in that prefix.

• Each legal choice extends the prefix with one unused element, preserving distinctness.
• At depth n, the prefix contains every input element exactly once, so it is a permutation.
• Conversely, every permutation defines one unique sequence of choices, so all permutations are generated exactly once.

There are n! outputs, and printing each requires Theta(n) time. Any generator that materializes them all therefore requires Omega(n * n!) time; this implementation matches that output-sensitive bound. Its auxiliary space is Theta(n) excluding output.

Before the initial call, input must contain n distinct values, output and used must each provide n writable elements, and every entry of used must be false. All buffers must remain valid throughout recursion. print_permutation is the output callback in this version; replacing it with storage or another callback changes the output cost but not the search invariant. The empty input has one mathematical permutation—the empty sequence—and the helper prints one blank line when called with n == 0 and valid zero-length state.

Duplicate input. With values [1,1,2], index-based used[] generates duplicate value sequences. Sort the input and skip candidate i at a depth when i > 0, input[i] == input[i-1], and used[i-1] is false. Among equal unused values, only the earliest index may start a branch at that depth. If the previous equal index is already used higher in the path, the later copy remains available because it represents a genuinely different remaining occurrence. Every value permutation has exactly one canonical index sequence under this rule.

N-Queens

Problem. Place n queens on an n x n chessboard so no two share a row, column, or diagonal.

Placing one queen per row eliminates row conflicts by construction. At row r, try each column c. The two diagonal identifiers are:

descending diagonal: r - c + (n - 1), range 0 .. 2n-2
ascending diagonal:  r + c,           range 0 .. 2n-2

#include <stdbool.h>
#include <stddef.h>

#define MAX_N 32

typedef struct {
    size_t n;
    int column_for_row[MAX_N];
    bool column_used[MAX_N];
    bool down_used[2 * MAX_N - 1];
    bool up_used[2 * MAX_N - 1];
} Queens;

static bool place_queen(Queens *q, size_t row) {
    if (row == q->n) {
        return true;
    }

    for (size_t column = 0; column < q->n; ++column) {
        size_t down = row + (q->n - 1U) - column;
        size_t up = row + column;
        if (q->column_used[column] || q->down_used[down] || q->up_used[up]) {
            continue;
        }

        q->column_for_row[row] = (int)column;
        q->column_used[column] = true;
        q->down_used[down] = true;
        q->up_used[up] = true;

        if (place_queen(q, row + 1U)) {
            return true;
        }

        q->column_used[column] = false;
        q->down_used[down] = false;
        q->up_used[up] = false;
    }
    return false;
}

bool solve_queens(size_t n, Queens *solution) {
    if (solution == NULL || n == 0U || n > MAX_N) {
        return false;
    }
    Queens candidate = {.n = n};
    if (!place_queen(&candidate, 0U)) {
        return false;
    }
    *solution = candidate;
    return true;
}

solve_queens defines the interface as 1 <= n <= MAX_N, zero-initializes every occupancy array, and returns the first solution in column order. false means either invalid input or no solution; an enum can distinguish those outcomes when the caller needs to report them separately.

Queens Trace

For n = 4, assuming columns are tried left to right:

row 0 -> col 0
  row 1 -> col 2
    row 2 -> no legal column        backtrack row 1
  row 1 -> col 3
    row 2 -> col 1
      row 3 -> no legal column      backtrack to row 0
row 0 -> col 1
  row 1 -> col 3
    row 2 -> col 0
      row 3 -> col 2                solution [1, 3, 0, 2]

The solution vector means queens at (0,1), (1,3), (2,0), (3,2).

Correctness

The occupancy arrays ensure every chosen queen avoids all earlier queens. Because one queen is placed per recursive row, reaching row == n gives n pairwise nonattacking queens. For completeness, take any valid solution: its column in the current row is never rejected, so the loop contains the branch matching that solution. Inductively, that branch reaches a complete solution unless the function returns an earlier valid one.

The crude bound is O(n!): columns are never reused, and diagonal pruning only reduces the tree. Legality checks are O(1). Space is O(n) recursion depth plus O(n) occupancy state. There are no solutions for n = 2 or n = 3; an empty 0 x 0 board can be defined as one trivial solution or rejected by the interface—state the convention.

Subset Sum

Decision problem. Given integers a[0..n-1] and target T, does some subset sum to exactly T?

At each index there are two choices: exclude the element or include it.

SUBSET(i, current):
    if i == n: return current == target
    if SUBSET(i + 1, current): return true
    choose a[i]
    if SUBSET(i + 1, current + a[i]): return true
    undo a[i]
    return false

A C17 implementation that also records one witness is:

#include <stdbool.h>
#include <limits.h>
#include <stddef.h>

static bool subset_visit(const int a[], size_t n, size_t i,
                         long long sum, long long target, bool chosen[]) {
    if (i == n) {
        return sum == target;
    }

    chosen[i] = false;
    if (subset_visit(a, n, i + 1U, sum, target, chosen)) {
        return true;
    }

    chosen[i] = true;
    if ((a[i] > 0 && sum > LLONG_MAX - a[i]) ||
        (a[i] < 0 && sum < LLONG_MIN - a[i])) {
        chosen[i] = false;
        return false;
    }
    long long included = sum + a[i];
    if (subset_visit(a, n, i + 1U, included, target, chosen)) {
        return true;
    }

    chosen[i] = false;                 /* restore before reporting failure */
    return false;
}

Invariant. At call (i, sum), sum is exactly the sum of elements marked chosen among indices below i; indices i..n-1 remain undecided.

The two recursive branches enumerate every subset exactly once according to whether it contains a[i]. Thus a returned witness is sound, and if any representable witness exists its branch is explored, establishing completeness. The helper requires non-null arrays when n > 0, and its numeric contract restricts every partial subset sum to long long; the defensive check rejects a branch that violates that contract. A status-returning interface or arbitrary-precision arithmetic is needed to distinguish range failure from “no solution.” Worst-case time is Theta(2^n) and stack space is Theta(n).

Safe Bounds

If all remaining values are nonnegative, prune when sum > target, because adding more values cannot reduce the sum. That rule is incorrect when negative values are allowed. A more general bound precomputes the sum of all remaining negative values and all remaining positive values. Compute those suffix sums and the interval endpoints with checked arithmetic under the same representability contract. Prune if the target lies outside:

Dynamic programming later solves the nonnegative integer version in pseudo-polynomial O(nT) time. That does not make backtracking obsolete: negative values, enormous targets, sparse reachable sums, witness enumeration, or small n may favor search.

Signed Trace

Search a=[7,-3,5,2] for target 4, exploring exclusion before inclusion. The first successful branch is:

exclude 7      sum =  0
include -3     sum = -3
include 5      sum =  2
include 2      sum =  4

The witness is {-3,5,2}. A rule that prunes merely because sum > target would be unsafe: after including 7, the remaining interval contribution is from -3 through 5+2=7, so reachable totals are bounded within [4,14]; target 4 remains possible. If the branch then excludes -3, the remaining contributions are nonnegative and totals lie in [7,14], so pruning becomes safe. The proof follows the suffix interval, not the current sum alone.

The trace also shows why branch order affects the first returned witness. Inclusion-first may find a different valid subset, but soundness requires only that returned choices sum to the target, while completeness requires that every legal include/exclude pattern remains reachable unless a proven bound removes it.

Hamiltonian Cycles

Problem. Given a graph, find a simple cycle that visits every vertex exactly once and returns to the start.

Fix vertex 0 as the start. At depth k, append an unvisited vertex adjacent to path[k-1]. At depth V, accept only if the final vertex is adjacent to 0.

#include <stdbool.h>
#include <stddef.h>

#define MAX_VERTICES 64

typedef struct {
    size_t count;
    bool edge[MAX_VERTICES][MAX_VERTICES];
} MatrixGraph;

static bool hamilton_visit(const MatrixGraph *g, size_t depth,
                           size_t path[], bool used[]) {
    if (depth == g->count) {
        return g->edge[path[depth - 1U]][path[0]];
    }

    size_t previous = path[depth - 1U];
    for (size_t v = 1; v < g->count; ++v) {
        if (used[v] || !g->edge[previous][v]) {
            continue;
        }
        path[depth] = v;
        used[v] = true;
        if (hamilton_visit(g, depth + 1U, path, used)) {
            return true;
        }
        used[v] = false;
    }
    return false;
}

bool hamiltonian_cycle(const MatrixGraph *g, size_t path[]) {
    if (g == NULL || path == NULL || g->count < 3 || g->count > MAX_VERTICES) {
        return false;
    }
    bool used[MAX_VERTICES] = {false};
    path[0] = 0;
    used[0] = true;
    return hamilton_visit(g, 1, path, used);
}

Fixing the start removes rotational duplicates. For an undirected graph, a cycle and its reverse are still symmetric; when enumerating all cycles, impose a canonical condition such as path[1] < path[V-1].

The caller must provide at least g->count writable elements in path; C cannot infer that capacity from the pointer. On failure, the array may contain a partial attempted path and has no result contract. A status-plus-length interface can make that distinction explicit when callers need to preserve the previous contents.

The invariant says the prefix is a simple path starting at 0: all vertices are distinct and every consecutive pair is an edge. The base case adds the closing-edge requirement, so accepted output is a Hamiltonian cycle. Every such cycle starting at 0 corresponds to a branch the loop can follow. Worst-case time is O(V!); adjacency checks are O(1) with the matrix. A necessary precheck for an undirected graph is that every vertex have degree at least two, but that condition is not sufficient.

Sudoku Search

Sudoku illustrates constraint propagation: before branching, derive every forced consequence possible.

State consists of:

• a 9 x 9 grid, with 0 for empty cells;
• used-digit bit masks for nine rows, columns, and 3 x 3 boxes;
• a list of unresolved cells.

For a cell (r,c), legal digits are:

allowed = ALL_DIGITS & ~(row_used[r] | col_used[c] | box_used[box(r,c)])

Choose an empty cell, try each set bit, recurse, then clear the bit and cell on failure. The simplest version chooses the first empty cell; a dramatically better version chooses the cell with the minimum remaining values (MRV)—the fewest legal candidates.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define ALL_DIGITS 0x3FEu             /* bits 1 through 9 */

static int box_index(int row, int col) {
    return (row / 3) * 3 + col / 3;
}

static unsigned bit_count(uint16_t x) {
    unsigned count = 0;
    while (x != 0U) {
        x &= (uint16_t)(x - 1U);
        ++count;
    }
    return count;
}

static bool solve_sudoku(int grid[9][9], uint16_t row_used[9],
                         uint16_t col_used[9], uint16_t box_used[9]) {
    int best_row = -1;
    int best_col = -1;
    uint16_t best_allowed = 0;
    unsigned best_count = 10;

    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            if (grid[row][col] != 0) {
                continue;
            }
            int box = box_index(row, col);
            uint16_t forbidden = (uint16_t)(row_used[row] | col_used[col] |
                                            box_used[box]);
            uint16_t allowed = (uint16_t)(ALL_DIGITS & ~forbidden);
            unsigned count = bit_count(allowed);
            if (count == 0U) {
                return false;
            }
            if (count < best_count) {
                best_count = count;
                best_row = row;
                best_col = col;
                best_allowed = allowed;
            }
        }
    }

    if (best_row == -1) {
        return true;                    /* no empty cell remains */
    }

    int box = box_index(best_row, best_col);
    for (int digit = 1; digit <= 9; ++digit) {
        uint16_t bit = (uint16_t)(1U << digit);
        if ((best_allowed & bit) == 0U) {
            continue;
        }

        grid[best_row][best_col] = digit;
        row_used[best_row] |= bit;
        col_used[best_col] |= bit;
        box_used[box] |= bit;

        if (solve_sudoku(grid, row_used, col_used, box_used)) {
            return true;
        }

        grid[best_row][best_col] = 0;
        row_used[best_row] &= (uint16_t)~bit;
        col_used[best_col] &= (uint16_t)~bit;
        box_used[box] &= (uint16_t)~bit;
    }
    return false;
}

static bool initialize_sudoku(int grid[9][9],
                              uint16_t row_used[9],
                              uint16_t col_used[9],
                              uint16_t box_used[9]) {
    for (int i = 0; i < 9; i++) {
        row_used[i] = 0U;
        col_used[i] = 0U;
        box_used[i] = 0U;
    }

    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            int digit = grid[row][col];
            if (digit < 0 || digit > 9) {
                return false;
            }
            if (digit == 0) {
                continue;
            }

            int box = box_index(row, col);
            uint16_t bit = (uint16_t) (1U << digit);
            if ((row_used[row] & bit) != 0U ||
                (col_used[col] & bit) != 0U ||
                (box_used[box] & bit) != 0U) {
                return false;
            }
            row_used[row] |= bit;
            col_used[col] |= bit;
            box_used[box] |= bit;
        }
    }
    return true;
}

bool sudoku_solve(int grid[9][9]) {
    if (grid == NULL) {
        return false;
    }

    uint16_t row_used[9];
    uint16_t col_used[9];
    uint16_t box_used[9];
    if (!initialize_sudoku(grid, row_used, col_used, box_used)) {
        return false;
    }
    return solve_sudoku(grid, row_used, col_used, box_used);
}

Initialization rejects digits outside 0..9 and duplicate givens in any row, column, or box. The wrapper leaves a valid but unsatisfiable grid restored to its original givens after complete failure because every tentative assignment is undone. Its Boolean return combines invalid input and unsatisfiability; a status enum can distinguish them. The crude search bound is O(9^e) for e empty cells; constraints and MRV reduce practical search enormously, while worst-case exponential behavior remains.

Branch-and-Bound

Branch-and-bound is backtracking specialized to optimization. It maintains:

• an incumbent: the best complete solution found;
• a bound on the best result any completion of the current partial state could possibly achieve.

For minimization, prune when a lower bound is no better than the incumbent. For maximization, prune when an upper bound is no better.

In 0–1 knapsack, a useful upper bound allows fractional pieces of remaining items. Fractional knapsack can only do at least as well as the constrained 0–1 completion. If even this optimistic value cannot beat the current best, no integral descendant can.

SEARCH(state):
    if complete:
        incumbent = better(incumbent, value(state))
        return
    if optimistic_bound(state) cannot beat incumbent:
        return
    explore promising choices

The bound must be optimistic. A fast but pessimistic estimate may prune the branch containing the optimum and turn an exact algorithm into an undocumented heuristic.

For capacity 5, consider density-ordered items A=(weight 2,value 40), B=(3,45), and C=(4,48). Exploring inclusion first finds A+B with value 85, establishing the incumbent.

• At the branch that includes A but excludes B, only three capacity units remain. Even the fractional relaxation can take only 3/4 of C, so its upper bound is 40+36=76; the branch cannot beat 85 and is pruned.
• At the branch excluding A, the relaxation takes all of B and half of C, for bound 45+24=69; that entire subtree is pruned.

The fractional values are not candidate 0–1 solutions. They are deliberately overpowered completions used only to certify that the integral descendants cannot improve the incumbent. Finding a strong incumbent early makes the same bound prune more branches, which is why branch order affects time while leaving the optimum unchanged.

State Reuse

A search tree can contain different paths that reach the same future-relevant state. In subset sum, choices among earlier items may produce the same pair (i,sum). From that point onward, the set of possible completions is identical. Memoized backtracking stores the result for such a state and turns the conceptual tree into a directed acyclic state graph.

When only one witness is needed, caching a state proved impossible is straightforward: every later visit may return failure immediately. Caching success needs either a stored next choice or a reconstruction pass. When every witness must be enumerated, skipping a repeated state can incorrectly discard distinct solution prefixes; the cache must store and combine all suffix witnesses, whose output can itself be exponential.

State identity must include everything that affects legal future choices. Caching graph-coloring results by only (vertex_index,colors_used) is unsound because the exact colors assigned to adjacent vertices affect future legality. A canonical representation can merge symmetric states, but its equivalence proof is part of correctness.

Memoization is most effective when many paths converge on relatively few states. If nearly every partial candidate is unique—as in plain permutation generation—cache lookup adds overhead without collapsing much search. The Dynamic Programming chapter develops the same reuse principle when the state graph is regular enough to evaluate systematically.

Candidate Ordering

Ordering changes neither soundness nor completeness if all legal choices remain available, but it can radically change when good solutions or contradictions are discovered.

• Fail first: choose the most constrained variable, as MRV does in Sudoku. Contradictions appear near the top of the tree.
• Best first: in optimization, explore the branch expected to improve the incumbent, strengthening subsequent bound pruning.
• Least constraining value: try the value that leaves neighbors the most options.
• Symmetry breaking: choose one canonical representative from equivalent branches.

Heuristics should be measured on representative instances. The same ordering can help one input family and hurt another. Always distinguish “changes visitation order” from “removes branches”; only the latter needs a completeness argument.

Search-Tree Cost

Backtracking complexity is best described using search-tree parameters:

• branching factor b;
• maximum depth d;
• cost C to generate and validate a child;
• number N of states actually visited after pruning.

A generic upper bound for b > 1 is:

When b = 1, the tree is a single chain with d + 1 states and cost O(Cd). More directly, if pruning causes the implementation to visit N states and each visit spends at most C non-output work, its instance-sensitive time is O(NC) plus the cost of reporting solutions. This form is often more useful for comparing candidate-ordering and pruning rules on the same instance.

This is often loose. Permutations have decreasing branching and Theta(n!) leaves; subset decisions produce 2^n leaves; graph path choices depend on degrees. Report the bound that reflects the actual choice structure.

Auxiliary space for depth-first backtracking is normally O(d + S), where S is mutable state. Enumerating and storing every solution may require output-sized space far larger than the search stack.

Pruning improves N, often spectacularly, but does not usually change the worst-case complexity class. State that distinction honestly: “fast on constrained instances” is valuable even when “exponential in the worst case” remains true.

Backtracking Traps

• Missing undo: state from one branch contaminates its siblings.
• Over-undo: restoration clears a fact established by an earlier depth.
• Late constraints: correct but needlessly visits impossible descendants.
• Unsafe pruning: assumes nonnegative values, connectivity, or monotonicity not guaranteed by the contract.
• Duplicate generation: symmetric choices or repeated values produce the same semantic solution multiple times.
• Incomplete base case: accepts a Hamiltonian path without checking the closing edge, or a filled Sudoku without validating givens.
• Overflow: cumulative sums, costs, and bounds exceed their integer type.
• Recursion depth: a very deep search can exhaust the C call stack; use an explicit stack when depth is input-scale and unbounded.
• Only testing satisfiable inputs: failure paths and complete exhaustion contain many of the restoration bugs.

Choosing Backtracking

Use backtracking when:

• the problem naturally decomposes into discrete choices;
• partial candidates can be rejected early;
• all solutions, one witness, or an exact optimum is required;
• the effective instance size is moderate or constraints are strong.

Prefer another technique when:

• overlapping subproblems recur under the same state—memoization or dynamic programming may collapse them;
• a safe greedy-choice property exists;
• a polynomial graph, matching, or flow formulation captures the constraints;
• only an approximate answer is needed and exact exponential search is too costly.

Backtracking and these techniques can coexist. Memoized backtracking caches repeated states; branch-and-bound uses a relaxation from a greedy or linear method; constraint solvers combine propagation, learning, and search.

Backtracking Review

• Backtracking explores a conceptual tree of partial candidates in depth-first order.
• Candidate state must support a goal test, constraint checks, and legal next choices.
• Choose-explore-undo keeps sibling branches independent.
• Feasibility pruning, optimization bounds, dominance, and symmetry breaking remove subtrees only with justification.
• Permutation, N-Queens, subset sum, Hamiltonian cycle, and Sudoku share the same search skeleton despite different state.
• Branch-and-bound needs an incumbent and a mathematically optimistic bound.
• Candidate ordering can transform practical performance without changing the result set.
• Worst-case time is commonly exponential or factorial; pruning improves visited states, not necessarily the worst-case class.

Backtracking Problems

Search-State Language

1. Distinguish a search tree from a tree stored by the program.
2. What is the difference between a goal test and a feasibility test?
3. Why must a maximization upper bound be optimistic for safe pruning?
4. Explain why candidate ordering is usually correctness-neutral but pruning is not.

Branch Traces

5. Draw the complete search tree for permutations of [1, 2, 3], marking the used[] state at each internal node.
6. Trace subset sum for [3, 5, 6], target 8, with exclusion explored before inclusion. Count visited calls before the first witness.
7. Trace the first two failed branches and first solution of 4-Queens under left-to-right column order.

Restoration Bugs

8. Remove the final used[v] = false from Hamiltonian search. Construct a graph where a valid cycle is then missed.
9. A subset-sum implementation prunes whenever sum > target. Give a smallest counterexample with a negative element.
10. A Sudoku solver returns true when it finds no zero cell, but its initialization never validates givens. Construct a filled invalid grid it accepts.

Solver Extensions

11. Extend permutation search to avoid duplicate outputs for repeated values. State and prove the skip rule.
12. Modify N-Queens to count every solution rather than stopping at the first. Compare counts for n = 1..10.
13. Extend subset sum to print the selected values while ensuring state is restored on both success and failure paths.
14. Add initialization and output functions to the Sudoku solver, then test an invalid puzzle, a unique puzzle, and an unsatisfiable puzzle.

State Designs

15. Design a backtracking solver for graph coloring with at most k colors. Define state, next choices, constraints, invariant, and a candidate-ordering heuristic.
16. Design a word-search solver for a character grid. Explain how you prevent reusing a cell and how you restore state.
17. Give a branch-and-bound formulation for the travelling-salesperson problem. Propose a safe lower bound and justify it.

Pruning Challenges

18. Combine subset-sum backtracking with memoization of states (i, sum). Explain why caching only “failed” states is easy when one witness is enough, and why enumerating all witnesses changes the design.
19. Implement bit-mask N-Queens for n <= 32, generating available columns with bit operations. Relate each mask operation to the three occupancy arrays.
20. Add forward checking to graph coloring: after assigning a color, maintain each uncolored vertex’s remaining legal colors. Explain the restoration data needed to undo efficiently.