Constraint satisfaction problems : backtrack search revisited

Many backtrack search algorithms has been designed over the last years to solve constraint satisfaction problems. Among them, Forward Checking (FC) and Maintaining Arc Consistency (MAC) algorithms are the most popular and studied algorithms. In This work, such algorithms are revisited and extensively compared giving rise to interesting characterization of their efficiency with respect to random instances. More precisely, we provide experimental evidence that FC outperforms MAC on hard CSPs with high graph density and low constraint tightness whereas MAC is better on hard CSPs with low density and high constraints tightness. This results show that on some CSPs maintaining full arc consistency during search might be time consuming. Then, we propose a new generic approach that maintain partial and parameterizable form of local consistency.