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

The constraints for the map-coloring problem can be expressed as follows:

• Each region is assigned one color only, of $$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 $$C_\alpha(\bf{x}_\alpha)$$ defined over a subset of variables $$\bf{x}_\alpha$$ defines the set of feasible and infeasible combinations of $$\bf{x}_\alpha$$. The constraint $$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 $$X_1,X_2,X_3$$ are all $$\{0,1,2\}$$, and the constraint is $$X_1+X_2<X_3$$ then the feasible set is $$\{(0,0,1),(0,0,2),(0,1,2),(1,0,2)\}$$, and all remaining combinations are infeasible.

## Binary CSPs¶

Solving such problems as the map-coloring CSP on a sampler such as the D-Wave system necessitates that the mathematical formulation use binary variables because the solution is implemented physically with qubits, and so must translate to spins $$s_i\in\{-1,+1\}$$ or equivalent binary values $$x_i\in \{0,1\}$$. This means that in formulating the problem by stating it mathematically, you might use unary encoding to represent the $$C$$ colors: each region is represented by $$C$$ variables, one for each possible color, which is set to value $$1$$ if selected, while the remaining $$C-1$$ variables are $$0$$.

Another example is logical circuits. Logic gates such as AND, OR, NOT, XOR etc can be viewed as binary CSPs: the mathematically expressed relationships between binary inputs and outputs must meet certain validity conditions. For inputs $$x_1,x_2$$ and output $$y$$ of an AND gate, for example, the constraint to satisfy, $$y=x_1x_2$$, can be expressed as a set of valid configurations: (0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 1), where the variable order is $$(x_1, x_2, y)$$.

Boolean AND Operation

$$x_1,x_2$$

$$y$$

$$0,0$$

$$0$$

$$0,1$$

$$0$$

$$1,0$$

$$0$$

$$1,1$$

$$1$$

You can use Ocean’s dwavebinarycsp to construct a BQM from a CSP. It maps each individual constraint in the CSP to a ‘small’ Ising model or QUBO, in a mapping called a penalty model.

For more information on using the D-Wave system to solve CSPs, see the following documentation: