A new method for solving constraint satisfaction problems
Raimund Seidel · International Joint Conference on Artificial Intelligence · 1981
This paper deals with the combinatorial search problem of finding values for a set of variables subject to a set of constraints. This problem is referred to as a constraint satisfaction problem. We present an algorithm for finding all the solutions of a constraint satisfaction problem with worst case time bound 0(m*kf+1) and space bound 0(n*kf+1), where n is the number of variables in the problem, m the number of constraints, k the cardinality of the domain of the variables, and f<n an integer depending only on a graph which is associated with the problem. It will be shown that for planar graphs and graphs of fixed genus this f is 0(n).