= Solution
The conventional worst-case estimate is the <backtracking leaf bound> given by the <product> of the initial <constraint domain> sizes. Before exploiting any attacking-queen constraints, the three models give respectively
$$
\boxed{2^{N^2},\qquad (N^2)^N=N^{2N},\qquad N^N.}
$$
Model 1 has $N^2$ binary choices. Model 2 has $N$ labeled queens with $N^2$ possible cells each. Model 3 has $N$ row variables with $N$ possible columns each. The <rule of product> gives the displayed bounds; assigning variables in one prescribed order avoids multiplying again by the number of variable orderings.
With $k$ mutually nonattacking prescribed queens incorporated as singleton <constraint domains>, the corresponding bounds improve to
$$
\boxed{2^{N^2-k},\qquad N^{2(N-k)},\qquad N^{N-k}.}
$$
In Model 1 only the $k$ prescribed occupied cells have been fixed in this estimate; immediate deletion of attacked cells tightens it further. In Model 3 consistent clues occupy $k$ distinct rows. If the clues are inconsistent, preprocessing can reject the instance immediately.
These are \b[upper bounds on leaves, rather than exact attained counts for a fully specified pruning implementation]. Ordinary <backtracking> rejects inconsistent partial assignments and often creates far fewer leaves; a stopped branch is itself a leaf even if not all variables were assigned. Such early leaves still obey the <backtracking leaf bound>, since distinct leaves describe disjoint nonempty families of full domain assignments when constraints are ignored. Counting only possible complete nonattacking assignments is a different question. For example, row/column restrictions alone reduce full assignments to at most $N!$ in Model 3, but that number does not directly count failed partial leaves. Exact counts depend on variable ordering and <constraint propagation>, neither of which is specified.
Back to article page
