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.add_constraint(operator.eq, ['a', 'b'])
>>> csp.add_constraint(operator.ne, ['b', 'c'])
>>> csp.check({'a': 1, 'b': 1, 'c': 0})
True

Methods#

Adding variables and constraints#

ConstraintSatisfactionProblem.add_constraint(...)

Add a constraint.

ConstraintSatisfactionProblem.add_variable(v)

Add a variable.

Satisfiability#

ConstraintSatisfactionProblem.check(solution)

Check that a solution satisfies all of the constraints.

Transformations#

ConstraintSatisfactionProblem.fix_variable(v, ...)

Fix the value of a variable and remove it from the constraint satisfaction problem.