Looking Forward in Constraint Satisfaction Algorithms

Empirical evidence indicates that the most successful backtracking algorithms for solving constraint satisfaction problems do some level of forward constraint propagation. That is they check constraints against the as yet uninstantiated variables in the search tree. Two popular examples are the forward checking and maintaining arc-consistency algorithms. Although there is a growing body of empirical evidence supporting the superiority of these algorithms, relatively little is known about the theoretical relationship between these forward looking algorithms and backtracking algorithms that do not employ any constraint propagation, like generic backtracking and backmarking. In this paper we demonstrate that there is in fact a strong relationship between these different types of algorithms. 1 Introduction Constraint satisfaction problems (CSPs) [Mac87] are typical of the NP-complete combinatorial problems that are so pervasive in AI. A number of techniques have been proposed in the liter...