The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

# 4.2 Generate-and-Test Algorithms

A finite CSP could be solved by an exhaustive generate-and-test algorithm. The assignment space, $D$, is the set of total assignments. The algorithm returns one model or all models.

The generate-and-test algorithm to find one model is as follows: check each total assignment in turn; if an assignment is found that satisfies all of the constraints, return that assignment. A generate-and-test algorithm to find all models is the same except, instead of returning the first model found, it saves all of the models found.

###### Example 4.10.

In Example 4.9 the assignment space is

 $\displaystyle{D}=\{$ $\displaystyle\{A{=}1,B{=}1,C{=}1,D{=}1,E{=}1\},$ $\displaystyle\{A{=}1,B{=}1,C{=}1,D{=}1,E{=}2\},\dots,$ $\displaystyle\{A{=}4,B{=}4,C{=}4,D{=}4,E{=}4\}\}.$

In this case there are $|{D}|=4^{5}=1,024$ different assignments to be tested. If there were 15 variables instead of 5, there would be $4^{15}$, which is about a billion, assignments to test. This method could not work for 30 variables.

If each of the $n$ variable domains has size $d$, then $D$ has $d^{n}$ elements. If there are $e$ constraints, the total number of constraints tested is $O(ed^{n})$. As $n$ becomes large, this very quickly becomes intractable, and so we must find alternative solution methods.