A fast arc consistency algorithm for n-ary constraints

Abstract

The GAC-Scheme has become a popular general pur-pose algorithm for solving n-ary constraints, although it may scan an exponential number of supporting tuples. In this paper, we develop a major improvement of this scheme. When searching for a support, our new algo-rithm is able to skip over a number of tuples exponen-tial in the arity of the constraint by exploiting knowl-edge about the current domains of the variables. We demonstrate the effectiveness of the method for large table constraints.