Constraint Satisfaction

:A D), the assignment of false to A, true to B, false to C and false to D, is a satisfying truth value assignment. The structure of a constraint network is depicted by a constraint graph whose nodes represents the variables and any two nodes are connected if the corresponding variables participate in the same constraint. In the k- colorability formulation, the graph to be colored is the constraint graph. In our SAT example the constraint graph has A connected to D and A; B and C are connected to each other. Constraint networks have proven successful in modeling mundane cognitive tasks such as vision, language comprehension, default reasoning, and abduction, as well as in applications such as scheduling, design, diagnosis, and temporal and spatial reasoning. In general, constrai