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.
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.
