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.