Your Backtracking Solver Is Slower Than Brute Force

You wrote a backtracking solver that prunes branches early, expecting it to beat brute force. On some inputs it crawls instead. The overhead of constraint checks can exceed the savings from pruning, especially when constraints are loose early in the search. This article shows how to detect that situation and adapt.

By the end you will be able to:

• Spot inputs where backtracking loses to brute force
• Measure the real branching factor of your solver
• Implement an adaptive strategy that picks the faster approach at runtime

Why pruning backfires

Backtracking explores a search tree. Each node runs a constraint check before recursing. The hope is that most branches die quickly. But constraint checks cost time. If a check is expensive and most branches survive it, you pay the check cost on every node without gaining the pruning benefit.

This happens when constraints are loose early in the search. The solver descends deep before any constraint fails. The tree grows wide and shallow, and every node pays the check fee. The Exponential Time Hypothesis (ETH) suggests that for some problems no algorithm can avoid exhaustive search in the worst case. When your problem instance hits that worst case, clever pruning becomes pure overhead.

Measure the branching factor

Before optimizing, measure. Count how many children each node actually produces. A healthy backtracking solver has a low average branching factor. A failing one has a branching factor close to the brute-force baseline.

The following instrumented solver tracks nodes visited and branches generated. Run it on your worst-case input. If avg_branch is high and nodes is large, your pruning is not helping.

import time

class Solver:
    def __init__(self, n):
        self.n = n
        self.nodes = 0
        self.branches = 0

    def solve(self, state):
        self.nodes = 0
        self.branches = 0
        start = time.perf_counter()
        result = self._backtrack(state, 0)
        elapsed = time.perf_counter() - start
        avg_branch = self.branches / self.nodes if self.nodes else 0
        print(f"nodes={self.nodes} avg_branch={avg_branch:.2f} time={elapsed:.4f}s")
        return result

    def _backtrack(self, state, depth):
        self.nodes += 1
        if self._is_solution(state):
            return state
        candidates = self._candidates(state)
        self.branches += len(candidates)
        for c in candidates:
            child = self._apply(state, c)
            if self._consistent(child):
                result = self._backtrack(child, depth + 1)
                if result is not None:
                    return result
        return None

    # Stub methods -- replace with your problem
    def _is_solution(self, state): return False
    def _candidates(self, state): return []
    def _apply(self, state, c): return state
    def _consistent(self, state): return True

The _backtrack method increments nodes on every call and adds the number of candidates to branches. The average branching factor is branches / nodes. A value near the theoretical maximum (for example, n for permutations) means the constraint check rarely prunes.

When brute force wins

When the branching factor stays high, fall back to exhaustive search. Brute force has no per-node overhead; it simply iterates over the Cartesian product of choices.

from itertools import product

def brute_force(n, check):
    for combo in product(range(n), repeat=n):
        if check(combo):
            return combo
    return None

# Example: find a permutation where no element is in its index (derangement)
brute_force(4, lambda c: all(c[i] != i for i in range(len(c))))

Compare the two timings on the same input. On loose-constraint inputs, brute force often wins because it avoids the function-call and consistency-check overhead of recursion.

Build an adaptive solver

A robust solver picks its strategy based on the input. Measure the first few levels of the search tree. If the branching factor exceeds a threshold, switch to brute force.

class AdaptiveSolver:
    def __init__(self, n, threshold=2.5):
        self.n = n
        self.threshold = threshold

    def solve(self, state):
        # Quick probe: expand two levels and measure
        level1 = self._candidates(state)
        if not level1:
            return None
        total = 0
        for c in level1:
            child = self._apply(state, c)
            if self._consistent(child):
                total += len(self._candidates(child))
        avg = total / len(level1)
        if avg > self.threshold:
            return self._brute_force(state)
        return self._backtrack(state, 0)

    def _brute_force(self, state):
        # Implement problem-specific exhaustive search
        pass

    def _backtrack(self, state, depth):
        # Standard backtracking with pruning
        pass

    # Problem-specific methods
    def _is_solution(self, state): return False
    def _candidates(self, state): return []
    def _apply(self, state, c): return state
    def _consistent(self, state): return True

The probe expands the first two levels of the tree. level1 are the children of the root. For each consistent child we count its candidates. The average of those counts estimates the branching factor deeper in the tree. If it exceeds threshold (tune empirically), we delegate to a brute-force implementation.

Common pitfalls

• Probe cost: The two-level probe adds overhead. Keep it cheap; if the probe itself is expensive, you may misclassify easy instances.
• Threshold tuning: A fixed threshold works poorly across problem sizes. Consider scaling the threshold with n or learning it from a few sample runs.
• State representation: Brute force often requires a different state representation (e.g., a flat tuple). Ensure both strategies can operate on the same input or convert efficiently.
• Partial solutions: If the problem asks for all solutions, brute force must enumerate the entire space. Backtracking with pruning may still be better if solutions are clustered.

Key takeaways

• Pruning adds per-node overhead; when constraints are loose, that overhead dominates.
• Measure the average branching factor on realistic inputs before committing to a strategy.
• Brute force with itertools.product can outperform backtracking on wide, shallow trees.
• An adaptive solver that probes the first two levels and switches strategies captures the best of both worlds.
• Tune the switching threshold on a representative benchmark suite, not on a single test case.

Source

This article builds on Three new discoveries in mathematics, computer science, and physics, adding implementation detail and tradeoffs for practitioners.

Support this work

These write-ups are researched and published with no paywall, sponsor, or tracking. If one saved you an afternoon, a small tip keeps them coming.

USDT, USDC or USDD · TRC-20 (Tron)

TFTNsfyomKrnUutRjBTGVULp19ByW29KbY