2-C3: From Arc-Consistency to 2-Consistency

Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction Problems (CSPs). Since many researchers associate arc consistency with binary normalized CSPs, there is a confusion between the notion of arc consistency and 2-consistency. 2-consistency guarantees that any instantiation of a value to a variable can be consistently extended to any second variable. Thus, 2-consistency can be stronger than arc-consistency in binary CSPs. In this paper, we present a new algorithm, called 2-C3, which achieves 2-consistency in binary and non-normalized CSPs. This algorithm is a reformulation of the well-known AC3 algorithm. The evaluation section shows that 2-C3 is able to prune more search space than AC3 and AC4.