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.