= Backtracking leaf bound
{title2=$L\le\prod_i|D_i|$}
Suppose <backtracking> assigns each of finitely many variables once along each branch, branching only on distinct values in its initial nonempty <constraint domain> $D_i$. Then the number of leaves is at most $\prod_i|D_i|$, even if inconsistent partial assignments terminate early. Ignore constraints and associate a leaf with every full domain assignment extending its partial assignment. Each leaf has at least one such extension. Different leaves have disjoint extension families: at their first diverging choice they assigned different values to the same selected variable. These nonempty disjoint families lie in a <Cartesian product> of <cardinality> $\prod_i|D_i|$, proving the bound. The selected next variable can depend on the preceding assignments, provided each full assignment follows a unique branch.
The bound is exact for an unpruned enumeration tree, but need not be attained when actual constraints cause <search pruning>. Counting complete satisfying assignments alone also does not count failed partial leaves.
Back to article page
