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

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 D is a total assignment of a value to each variable. The algorithm returns those assignments that satisfy all of the constraints.

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|=45=1,024 different assignments to be tested. In the crossword example of Exercise 4.1 there are 406=4,096,000,000 possible assignments.

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