.. _csp_sdk: ======================= Constraint Satisfaction ======================= A constraint satisfaction problem (CSP) _ requires that all the problem's variables be assigned values, out of a finite domain, that result in the satisfying of all constraints. The map-coloring CSP, for example, is to assign a color to each region of a map such that any two regions sharing a border have different colors. .. figure:: ../_images/Problem_MapColoring.png :name: ProblemMapColoringCanada :alt: image :align: center :scale: 70 % Coloring a map of Canada with four colors. The constraints for the map-coloring problem can be expressed as follows: * Each region is assigned one color only, of :math:C possible colors. * The color assigned to one region cannot be assigned to adjacent regions. A finite domain CSP consists of a set of variables, a specification of the domain of each variable, and a specification of the constraints over combinations of the allowed values of the variables. A constraint :math:C_\alpha(\bf{x}_\alpha) defined over a subset of variables :math:\bf{x}_\alpha defines the set of feasible and infeasible combinations of :math:\bf{x}_\alpha. The constraint :math:C_\alpha may be be viewed as a predicate which evaluates to true on feasible configurations and to false on infeasible configurations. For example, if the domains of variables :math:X_1,X_2,X_3 are all :math:\{0,1,2\}, and the constraint is :math:X_1+X_2 to construct a :term:BQM from a CSP. It maps each individual constraint in the CSP to a ‘small’ Ising model or QUBO, in a mapping called a :doc:penalty model . For more information on using the D-Wave system to solve CSPs, see the following documentation: * :std:doc:Getting Started with the D-Wave System  Introduces the use of QUBOs to represent constraints in some simple examples. * :std:doc:D-Wave Problem-Solving Handbook  Provides a variety of techniques for, and examples of, reformulating CSPs as BQMs.