Backtracking

Backtracking is a systematic algorithmic technique for finding all (or some) solutions to computational problems, notably constraint satisfaction problems, by incrementally building candidates to the solutions and abandoning a candidate ('backtracking') as soon as it determines that the candidate cannot possibly be completed to a valid solution. Mathematically, it operates on a directed state-space tree where nodes represent partial candidate states and edges represent state transitions. By coupling Depth-First Search (DFS) with early bound-checking and constraint propagation (pruning), backtracking reduces exponential search spaces from unconstrained enumerations O(b^d) down to tractable domains in practical operational bounds, provided bounding functions tightly encapsulate valid state invariants.

/* 
 * Conceptual state-space tree node formulation for backtracking.
 * S = current state vector
 * D = available choices at current depth
 */

vector<vector<int>> results;

void backtrack(vector<int>& currentState, int depth, const ProblemParams& params) {
    // Base Case: Evaluate if current state satisfies complete solution criteria
    if (isSolution(currentState, params)) {
        results.push_back(currentState);
        return;
    }

    // Explore choices at the current decision level
    for (auto& choice : getValidChoices(currentState, params)) {
        // Pruning Step: Validate constraints before committing
        if (isValidConstraint(currentState, choice)) {
            // 1. Make the move (State Mutation)
            currentState.push_back(choice);
            
            // 2. Recurse deeper into the state-space tree
            backtrack(currentState, depth + 1, params);
            
            // 3. Backtrack: Undo the move to restore exact prior state
            currentState.pop_back();
        }
    }
}

assert(solveNQueens(0).empty() == true);
assert(solveNQueens(1).size() == 1);
assert(solveNQueens(4).size() == 2);

/* Iterative Stack-Based Guard against Stack Overflow */
#include <stack>
#include <vector>

struct Node {
    std::vector<int> state;
    int depth;
};

void iterativeBacktrack(int maxDepth) {
    std::stack<Node> frontier;
    frontier.push({{}, 0});
    while (!frontier.empty()) {
        Node curr = frontier.top();
        frontier.pop();
        if (curr.depth == maxDepth) {
            continue;
        }
        // Generate next states and push to stack
    }
}

Mathematical Formulation & State-Space Trees

Backtracking systematically explores a state-space tree T = (V, E) where each vertex v in V corresponds to a partially constructed solution vector s = [x_1, x_2, …, x_k] of length k <= n. The root node represents the empty state s_0 = []. Edges e = (u, v) correspond to assigning a value to the next decision variable x_{k+1}. Let b be the branching factor (maximum number of valid choices available at any state node) and d be the maximum depth of the search tree (number of decision variables). In the unconstrained worst-case scenario, the algorithm traverses all leaves, resulting in O(b^d) time complexity. However, by introducing a bounding function prune(s) that evaluates to true if a partial state s cannot possibly lead to a valid leaf node, the algorithm prunes entire subtrees of size O(b^{d – k}), dramatically lowering the effective complexity. Space complexity is strictly bounded by O(d) due to the maximum depth of the recursive call stack holding active state variables and choices.

Algorithmic Optimizations & Heuristics

Raw backtracking can degrade to exponential performance without domain-specific heuristics. Key optimization strategies include: (1) Minimum Remaining Values (MRV) heuristic, which selects the variable with the fewest remaining legal values to branch on first; (2) Degree heuristic, which selects the variable involved in the most constraints on other unassigned variables; (3) Forward Checking, which proactively updates and filters domains of unassigned variables immediately after a choice is made, cutting off dead ends before explicit recursion reaches them; and (4) Branch and Bound integration, which maintains a global optimum cost and prunes branches whose lower-bound cost estimation exceeds the current best objective value.