Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

## 4.3 Generate-and-Test Algorithms

Any finite CSP can be solved by an exhaustive generate-and-test
algorithm. The **assignment
space**, * D*, is
the set of assignments of values to all of the variables; it corresponds
to the set of all possible worlds.
Each element of

*is a total assignment of a value to each variable. The algorithm returns those assignments that satisfy all of the constraints.*

**D**Thus, the **generate-and-test** algorithm is as follows: check each total assignment in turn; if an
assignment is found that satisfies all of the constraints, return that assignment.

**Example 4.11:**In Example 4.8 the assignment space is

D={ {A=1,B=1,C=1,D=1,E=1}, {A=1,B=1,C=1,D=1,E=2},..., {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. In the crossword example of
Exercise 4.1 there are

*40*possible assignments.

^{6}=4,096,000,000If each of the *n* variable domains has size *d*, then * D* has

*d*elements. If there are

^{n}*e*constraints, the total number of constraints tested is

*O(ed*. As

^{n})*n*becomes large, this very quickly becomes intractable, and so we must find alternative solution methods.