Abstract
Arc-Consistency algorithms are the most commonly used ltering techniques
to prune the search space in Constraint Satisfaction Problems (CSPs). 2-consistency is
a similar technique that 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 work we present a new algorithm to achieve 2-
consistency called 2-C4. This algorithm is a reformulation of AC4 algorithm that is able
to reduce unnecessary checking and prune more search space than AC4. The experimental
results show that 2-C4 was able to prune more search space than arc-consistency algo-
rithms in non-normalized instances. Furthermore, 2-C4 was more efficient than other
2-consistency algorithms presented in the literature.
