Arc Consistency for General Constraint Networks: Preliminary Results

Abstract

Constraint networks are used more and more to solve combinatorial problems in real-life applications. Much activity is concentrated on improving the efficiency of finding a solution in a constraint network (the constraint satisfaction problem, CSP). Particularly, arc consistency caught many researchers ' attention, involving the discovery of a large number of algorithms. And, for the last two years, it has been shown that maintaining arc consistency during search is a worthwhile approach. However, results on CSPs and on arc consistency are almost always limited to binary constraint networks. The CSP is no longer an academic problem, and it is time to deal with non-binary CSPs, as widely required in real world constraint solvers. This paper proposes a general schema to implement arc consistency on constraints of any arity when no specific algorithm is known. A first instantiation of the schema is presented here, which deals with constraints given by a predicate, by the set of forbidden combinations of values, or by the set of allowed ones.