.. _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.