snakeoil.constraints module

Facilities for solving constraint satisfaction problems.

Usage examples:

>>> def divides_by(x, y):
>>>     return x % y == 0
>>>
>>> p = Problem()
>>> p.add_variable(range(2, 10), 'x', 'y', 'z')
>>> p.add_constraint(divides_by, frozenset({'x', 'y'}))
>>> p.add_constraint(lambda x, z: x > z, frozenset({'z', 'x'}))
>>> p.add_constraint(lambda y, x, z: x+y+z > 0, frozenset({'z', 'x', 'y'}))
>>> for solution in p:
>>>     print(f"x={solution['x']}, y={solution['y']}, z={solution['z']}")

class snakeoil.constraints.Constraint(*args, **kwargs)

Bases: Protocol

Type used for constraint satisfaction check.

__call__(**kwargs: Any) → bool

Check satisfaction of the constraint.

Parameters:

kwargs – keyworded arguments, named after the variables passed to Problem.add_constraint(), with assigned value from the domain.

Returns:

True if the assignment is satisfied.

class snakeoil.constraints.Problem

Bases: object

Class used to define a problem and retrieve solutions.

Define a problem by calling add_variable() and then add_constraint(), and then iterate over the problem to retrieve solutions satisfying the problem.

For building solutions for the problem, the back tracking algorithm is used. It is a deterministic algorithm, which means the same solution is built if the variables and constraints were identically built.

Note:

The class is mutable, so adding variables or constraints during iteration of solutions might break the solver.

__iter__() → Iterator[dict[str, Any]]

Retrieve solutions satisfying the problem. Each solution consists of a dict assigning to each variable in the problem a single value from it’s domain.

add_constraint(constraint: Constraint, variables: frozenset[str])

Add constraint to the problem, which depends on the specified variables.

Parameters:

• constraint – Callable which accepts as keyworded args the variables, and returns True only if the assignment is satisfied.

• variables – names of variables, on which the constraint depends. Only those variables will be passed during check of constraint.

Raises:

AssertionError – if the specified variables weren’t added previously, so they have no domain.

add_variable(domain: Iterable[Any], *variables: str)

Add variables to the problem, which use the specified domain.

Parameters:

• domain – domain of possible values for the variables.

• variables – names of variables, to be used in assignment and checking the constraint satisfaction.

Raises:

AssertionError – if the variable was already added previously to this problem.

Note:

The solver prefers later values from the domain, meaning the first solutions will try to use the later values from each domain.