Backtracking leaf bound ($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.