Defining Constraint Satisfaction Problems#

Constraint satisfaction problems require that all a problem’s variables be assigned values, out of a finite domain, that result in the satisfying of all constraints. The ConstraintSatisfactionProblem class aggregates all constraints and variables defined for a problem and provides functionality to assist in problem solution, such as verifying whether a candidate solution satisfies the constraints.

Class#

class ConstraintSatisfactionProblem(vartype)[source]#

A constraint satisfaction problem.

Parameters:

vartype (Vartype/str/set) –

Variable type for the binary quadratic model. Supported values are:

constraints[source]#

Constraints that together constitute the constraint satisfaction problem. Valid solutions satisfy all of the constraints.

Type:

list[Constraint]

variables[source]#

Variables of the constraint satisfaction problem as a dict, where keys are the variables and values a list of all of constraints associated with the variable.

Type:

dict[variable, list[Constraint]]

vartype[source]#

Enumeration of valid variable types. Supported values are SPIN or BINARY. If vartype is SPIN, variables can be assigned -1 or 1; if BINARY, variables can be assigned 0 or 1.

Type:

dimod.Vartype

Example

This example creates a binary-valued constraint satisfaction problem, adds two constraints, $$a = b$$ and $$b \ne c$$, and tests $$a,b,c = 1,1,0$$.

>>> import operator
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem('BINARY')
>>> csp.check({'a': 1, 'b': 1, 'c': 0})
True