Constraint satisfaction problem

From Glossary

Jump to: navigation, search

A classical Constraint Satisfaction Problem (CSP) is defined by a finite set of variables LaTeX: X = \{x_1, \dots, x_n\} where each variable LaTeX: x_i is associated with a finite domain of integers LaTeX: D_i= \{1, \dots, N_i\}. Furthermore, a finite set of constraints LaTeX:  \mathcal{C} = \{C_1, \dots, C_m \} is imposed on the variables, where a constraint LaTeX: C_i is an arbitrary relation on a subset of variables LaTeX: X. A solution to the CSP is a value assignment to each variable such that the value lies within the respective domain and all constraints are satisfied.

There exist different variants and sub-classes of constraint satisfaction problem:

Personal tools