Look-Ahead Value Ordering for Constraint Satisfaction Problems

Abstract

Looking ahead during search is often useful when solving constraint satisfaction problems. Previous studies have shown that looking ahead helps by causing dead-ends to occur earlier in the search, and by providing information that is useful for dynamic variable ordering. In this paper, we show that another benefit of looking ahead is a useful domain value ordering heuristic, which we call look-ahead value ordering or LVO. LVO counts the number of times each value of the current variable conflicts with some value of a future variable, and the value with the lowest number of conflicts is chosen first. Our experiments show that look-ahead value ordering can be of substantial benefit, especially on hard constraint satisfaction problems. 1 Introduction In this paper we present a new heuristic for prioritizing the selection of values when searching for the solution of a constraint satisfaction problem. Because the task of finding a solution for a constraint satisfaction problem is NP-comp...