Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence / 3 / c / Solution

For a finite constraint satisfaction problem with $v$ variables, all complete assignments have depth $v$ when each step assigns one new variable. Thus the shallowest-solution property of breadth-first search offers no advantage: every complete solution is already at that depth.

Depth-first search with backtracking stores a path and pending choices, using $O(vd)$ auxiliary space with ordinary explicit choice bookkeeping, or $O(v)$ when each level stores only a current value index. Breadth-first search may store an exponentially large frontier, up to $O(d^v)$ partial assignments. Depth-first search can also combine naturally with immediate constraint propagation and undoing changes. The finite depth avoids the infinite-branch obstruction of unrestricted depth-first tree search. Neither traversal removes the possible exponential time complexity.