Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence / 3 / e / 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 respectivelyModel 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 toIn 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 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.