= 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>.
Back to article page
