On the need for a different backtracking rule when dealing with late evaluation

AbstractConstraint Satisfaction Problems (CSPs) represent a widely used framework for many real-life problems. Constraint Logic Programming (CLP) languages are an effective tool for modeling problems in terms of CSPs and solving them efficiently.Lazy domain evaluation is a solving technique that has proven effective for solving CSPs, allowing the minimization of the number of constraint checks. However, exploiting lazy domain evaluation in CLP is not very effective, mainly because of the chronological backtracking rule used in CLP. After each backtracking step, in fact, all the obtained results are lost, even if they had nothing to do with the culprit of the failure. The intelligent backtracking rule widely studied in the past does not solve the problem either.In this paper, we propose a backtracking rule useful for dealing efficiently and declaratively with lazy domain evaluation in CLP, and we show a simple implementation of a metainterpreter providing the depicted functionality