Some incomplete constraint solvers
Krzysztof Rafal Apt · Cambridge University Press eBooks · 2003
FOR SOME SPECIFIC domains and constraints for which no efficient solving methods exist or are known to exist specialised techniques have been developed. The aim of this chapter is to illustrate such techniques on a number of examples. In each case they amount to reducing a given CSP to a simpler one that is equivalent to the original one. Because in general from the resulting CSP one cannot immediately generate solutions to it, these methods amount in the terminology of Chapter 4 to incomplete constraint solvers. We define these incomplete constraint solvers using the proof theoretic framework introduced in Section 4.1, so by means of the proof rules that work on CSPs. Ideally, we would like to use the general rules defined in Chapter 5. Unfortunately, this is easier said than done. Consider for example the HYPER-ARC CONSISTENCY rule of Section 5.3 that is clearly of interest, since given a constraint C on the variables x 1 , …, x k , it allows us to remove all ‘unneeded’ elements from the domains of the variables x 1 , …, x k . When the constraints are defined using a specific language, it is not clear how to compute the new variable domains that appear in the rule conclusion. So for each specific language we rather provide rules that are defined syntactically and consequently can be readily implemented.