Value Ordering for Finding All Solutions

摘要

In finding all solutions to a constraint satisfaction problem, or proving that there are none, with a search algorithm that backtracks chronologically and forms k-way branches, the order in which the values are assigned is immaterial. However, we show that if the values of a variable are assigned instead via a sequence of binary choice points, and the removal of the value just tried from the domain of the variable is propagated before another value is selected, the value ordering can affect the search effort. We show that this depends on the problem constraints; for some types of constraints, we show that the savings in search effort can be significant, given a good value ordering.