2.1.3 Interleaving Generation and Checking

The `generate and test' method generates complete assignments and only then checks whether they are solutions or failures. We can usually improve on it by interleaving generation and checking: after each choice we can check if any constraint is obviously violated. For example, in our problem the constraints are V1 < V2, V2 < V3, ... , V14 < V15. Thus, as soon as we have guessed values for V1 and V2, we can immediately check whether V1 < V2 is violated or not; we don't have to wait until values have been guessed for all other variables too. As a result, we can decide failure much earlier and the search tree become much smaller. For the example with only 6 variables, it now contains 631 nodes instead of 93311:

This strategy, often implemented using some notion of coroutines, is traditionally called `test and generate'. The tests are posted first, but each remains suspended until its variables have all been assigned. Generation then proceeds as before, except that a test becomes active as soon as its variables have been assigned and thus may cause failure before further levels of the search tree are generated.


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.2.4 (20020829)