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

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.