Speeding up the Arc Consistency algorithm in Constraint Satisfaction Problems: A New Modification of AC-3

Abstract

Dealing with constraints is always very common in real-world implementation issues. Search algorithms for real problems are also no exception. Because of the constraints in search problems (named Constraint Satisfaction Problems (CSPs)), their main solving algorithm is presented in backtracking form. The constraint propagation algorithm is an auxiliary tool to avoid facing constraint conditions as well as reducing search options. This algorithm has been presented in almost seven versions so far. In this paper, we have updated the third version of this algorithm, which is presented under the title of AC-3, from five aspects and have increased its capabilities. The most important feature of our proposed algorithm is its low time complexity. This feature has been made possible by two auxiliary criteria introduction for detecting more critical binary constraints. Faster investigation of critical constraints leads to early detection of dead-end in the search path and the search continues in this direction stops.