Backtracking along with constraint processing and their time complexities

Abstract

In this review paper we embed several constraint propagation algorithms inside a backtracking algorithm in order to solve constraint satisfaction problems and analyse the time complexities. To get a common frame for presenting the diverse algorithms we provide formal definitions for a uniform treatment of constraint satisfaction problems. For some constraint satisfaction algorithms we prove that their asymptotic total worst-case time complexities are equal to that of ordinary backtracking. If the constraint satisfaction problems are binary, the asymptotic total worst-case time complexities of these algorithms are even better and optimal in the sense that there is no algorithm which improves these complexity bounds. Furthermore, we present a new algorithm that establishes global consistency.