P. Van Hentenryck, M. Dincbas
When confronted with constraint satisfaction problems (CSP), the "generate b test" strategy of Prolog is particularly inefficient. Also, control mechanisms defined for logic programming languages fall short in CSP because of their restricted use of constraints. Indeed, constraints are used passiveIy for testing generated values and not for actively pruning the search space by eliminating combinations of values which cannot appear together in a solution. One remedy is to introduce the domain concept in logic programming language. This allows for an active use of constraints. This extension which does not impede the declarative (logic) reading of logic languages, consists in a modification of the unification, the redefinition of the procedural semantics of some built-in predicates ( # , < , < , > , >) and a new evaluable function and can be implemented efficiently. Without any change to the search procedure and without introducing a new control mechanism, look ahead strategies, more intelligent choices and consistency techniques can be implemented naturally in programs. Moreover, when combined with a delay mechanism, this leads directly to a strategy which applies active constraints as soon as possible.