API Documentation

class constraint.Problem(solver=None)

Class used to define a problem and retrieve solutions.

Initialization method.

Parameters:

solver (instance of a Solver) – Problem solver (default OptimizedBacktrackingSolver)

addConstraint(constraint, variables=None)

Add a constraint to the problem.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> problem.addConstraint(lambda a, b: b == a+1, ["a", "b"])
>>> problem.addConstraint("b == a+1 and a+b >= 2")   # experimental string format, automatically parsed, preferable over callables
>>> solutions = problem.getSolutions()
>>>
Parameters:

  • constraint (instance of Constraint, function to be wrapped by FunctionConstraint, or string expression) – Constraint to be included in the problem. Can be either a Constraint, a callable (function or lambda), or Python-evaluable string expression that will be parsed automatically.

  • variables (set or sequence of variables) – Variables affected by the constraint (default to all variables). Depending on the constraint type the order may be important.

addVariable(variable, domain)

Add a variable to the problem.

Example

>>> problem = Problem()
>>> problem.addVariable("a", [1, 2])
>>> problem.getSolution() in ({'a': 1}, {'a': 2})
True
Parameters:

  • variable (hashable object) – Object representing a problem variable

  • domain (list, tuple, or instance of Domain) – Set of items defining the possible values that the given variable may assume

addVariables(variables, domain)

Add one or more variables to the problem.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> solutions = problem.getSolutions()
>>> len(solutions)
9
>>> {'a': 3, 'b': 1} in solutions
True
Parameters:

  • variables (sequence of hashable objects) – Any object containing a sequence of objects represeting problem variables

  • domain (list, tuple, or instance of Domain) – Set of items defining the possible values that the given variables may assume

getSolution()

Find and return a solution to the problem.

Example

>>> problem = Problem()
>>> problem.getSolution() is None
True
>>> problem.addVariables(["a"], [42])
>>> problem.getSolution()
{'a': 42}
Returns:

Solution for the problem

Return type:

dictionary mapping variables to values

getSolutionIter()

Return an iterator to the solutions of the problem.

Example

>>> problem = Problem()
>>> list(problem.getSolutionIter()) == []
True
>>> problem.addVariables(["a"], [42])
>>> iter = problem.getSolutionIter()
>>> next(iter)
{'a': 42}
>>> next(iter)
Traceback (most recent call last):
    ...
StopIteration
getSolutions()

Find and return all solutions to the problem.

Example

>>> problem = Problem()
>>> problem.getSolutions() == []
True
>>> problem.addVariables(["a"], [42])
>>> problem.getSolutions()
[{'a': 42}]
Returns:

All solutions for the problem

Return type:

list of dictionaries mapping variables to values

getSolutionsAsListDict(order=None, validate=True)

Returns the searchspace as a list of tuples, a dict of the searchspace for fast lookups and the size.

Return type:

tuple[list[tuple], dict[tuple, int], int]

getSolutionsOrderedList(order=None)

Returns the solutions as a list of tuples, with each solution tuple ordered according to order.

Return type:

list[tuple]

getSolver()

Obtain the problem solver currently in use.

Example

>>> solver = OptimizedBacktrackingSolver()
>>> problem = Problem(solver)
>>> problem.getSolver() is solver
True
Returns:

Solver currently in use

Return type:

instance of a Solver subclass

reset()

Reset the current problem definition.

Example

>>> problem = Problem()
>>> problem.addVariable("a", [1, 2])
>>> problem.reset()
>>> problem.getSolution()
>>>
setSolver(solver)

Change the problem solver currently in use.

Example

>>> solver = OptimizedBacktrackingSolver()
>>> problem = Problem(solver)
>>> problem.getSolver() is solver
True
Parameters:

solver (instance of a Solver) – New problem solver

class constraint.Variable(name)

Helper class for variable definition.

Using this class is optional, since any hashable object, including plain strings and integers, may be used as variables.

Initialization method.

Parameters:

name (string) – Generic variable name for problem-specific purposes

class constraint.Domain(set)

Class used to control possible values for variables.

When list or tuples are used as domains, they are automatically converted to an instance of that class.

Initialization method.

Parameters:

set – Set of values, comparable by equality, that the given variables may assume.

hideValue(value)

Hide the given value from the domain.

After that call the given value won’t be seen as a possible value on that domain anymore. The hidden value will be restored when the previous saved state is popped.

Parameters:

value – Object currently available in the domain

popState()

Restore domain state from the top of the stack.

Variables hidden since the last popped state are then available again.

pushState()

Save current domain state.

Variables hidden after that call are restored when that state is popped from the stack.

resetState()

Reset to the original domain state, including all possible values.

Solvers

class constraint.Solver

Abstract base class for solvers.

getSolution(domains, constraints, vconstraints)

Return one solution for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutionIter(domains, constraints, vconstraints)

Return an iterator for the solutions of the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutions(domains, constraints, vconstraints)

Return all solutions for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.BacktrackingSolver(forwardcheck=True)

Problem solver with backtracking capabilities.

Examples

>>> result = [[('a', 1), ('b', 2)],
...           [('a', 1), ('b', 3)],
...           [('a', 2), ('b', 3)]]

>>> problem = Problem(BacktrackingSolver())
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> problem.addConstraint(lambda a, b: b > a, ["a", "b"])

>>> solution = problem.getSolution()
>>> sorted(solution.items()) in result
True

>>> for solution in problem.getSolutionIter():
...     sorted(solution.items()) in result
True
True
True

>>> for solution in problem.getSolutions():
...     sorted(solution.items()) in result
True
True
True

Initialization method.

Parameters:

forwardcheck (bool) – If false forward checking will not be requested to constraints while looking for solutions (default is true)

getSolution(domains, constraints, vconstraints)

Return one solution for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutionIter(domains, constraints, vconstraints)

Return an iterator for the solutions of the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutions(domains, constraints, vconstraints)

Return all solutions for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.OptimizedBacktrackingSolver(forwardcheck=True)

Problem solver with backtracking capabilities, implementing several optimizations for increased performance.

Optimizations are especially in obtaining all solutions. View https://github.com/python-constraint/python-constraint/pull/76 for more details.

Examples

>>> result = [[('a', 1), ('b', 2)],
...           [('a', 1), ('b', 3)],
...           [('a', 2), ('b', 3)]]

>>> problem = Problem(OptimizedBacktrackingSolver())
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> problem.addConstraint(lambda a, b: b > a, ["a", "b"])

>>> solution = problem.getSolution()
>>> sorted(solution.items()) in result
True

>>> for solution in problem.getSolutionIter():
...     sorted(solution.items()) in result
True
True
True

>>> for solution in problem.getSolutions():
...     sorted(solution.items()) in result
True
True
True

Initialization method.

Parameters:

forwardcheck (bool) – If false forward checking will not be requested to constraints while looking for solutions (default is true)

getSolution(domains, constraints, vconstraints)

Return one solution for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutionIter(domains, constraints, vconstraints)

Return an iterator for the solutions of the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutions(domains, constraints, vconstraints)

Return all solutions for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutionsList(domains, vconstraints)

Optimized all-solutions finder that skips forwardchecking and returns the solutions in a list.

Return type:

list[dict[Hashable, any]]

Parameters:

  • domains – Dictionary mapping variables to domains

  • vconstraints – Dictionary mapping variables to a list of constraints affecting the given variables.

Returns:

the list of solutions as a dictionary.

getSortedVariables(domains, vconstraints)

Sorts the list of variables on number of vconstraints to find unassigned variables quicker.

Return type:

list

Parameters:

  • domains – Dictionary mapping variables to their domains

  • vconstraints – Dictionary mapping variables to a list of constraints affecting the given variables.

Returns:

the list of variables, sorted from highest number of vconstraints to lowest.

class constraint.RecursiveBacktrackingSolver(forwardcheck=True)

Recursive problem solver with backtracking capabilities.

Examples

>>> result = [[('a', 1), ('b', 2)],
...           [('a', 1), ('b', 3)],
...           [('a', 2), ('b', 3)]]

>>> problem = Problem(RecursiveBacktrackingSolver())
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> problem.addConstraint(lambda a, b: b > a, ["a", "b"])

>>> solution = problem.getSolution()
>>> sorted(solution.items()) in result
True

>>> for solution in problem.getSolutions():
...     sorted(solution.items()) in result
True
True
True

>>> problem.getSolutionIter()
Traceback (most recent call last):
...
NotImplementedError: RecursiveBacktrackingSolver doesn't provide iteration

Initialization method.

Parameters:

forwardcheck (bool) – If false forward checking will not be requested to constraints while looking for solutions (default is true)

getSolution(domains, constraints, vconstraints)

Return one solution for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

getSolutions(domains, constraints, vconstraints)

Return all solutions for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

recursiveBacktracking(solutions, domains, vconstraints, assignments, single)

Mix the Degree and Minimum Remaing Values (MRV) heuristics.

Parameters:

  • solutions – _description_

  • domains – _description_

  • vconstraints – _description_

  • assignments – _description_

  • single – _description_

Returns:

_description_

class constraint.MinConflictsSolver(steps=1000, rand=None)

Problem solver based on the minimum conflicts theory.

Examples

>>> result = [[('a', 1), ('b', 2)],
...           [('a', 1), ('b', 3)],
...           [('a', 2), ('b', 3)]]

>>> problem = Problem(MinConflictsSolver())
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> problem.addConstraint(lambda a, b: b > a, ["a", "b"])

>>> solution = problem.getSolution()
>>> sorted(solution.items()) in result
True

>>> problem.getSolutions()
Traceback (most recent call last):
...
NotImplementedError: MinConflictsSolver provides only a single solution

>>> problem.getSolutionIter()
Traceback (most recent call last):
...
NotImplementedError: MinConflictsSolver doesn't provide iteration

Initialization method.

Parameters:

  • steps (int) – Maximum number of steps to perform before giving up when looking for a solution (default is 1000)

  • rand (Random) – Optional random.Random instance to use for repeatability.

getSolution(domains, constraints, vconstraints)

Return one solution for the given problem.

Parameters:

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

Constraints

class constraint.Constraint

Abstract base class for constraints.

forwardCheck(variables, domains, assignments, _unassigned=Unassigned)

Helper method for generic forward checking.

Currently, this method acts only when there’s a single unassigned variable.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • assignments (dict) – Dictionary mapping assigned variables to their current assumed value

Returns:

Boolean value stating if this constraint is currently broken or not

Return type:

bool

preProcess(variables, domains, constraints, vconstraints)

Preprocess variable domains.

This method is called before starting to look for solutions, and is used to prune domains with specific constraint logic when possible. For instance, any constraints with a single variable may be applied on all possible values and removed, since they may act on individual values even without further knowledge about other assignments.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.FunctionConstraint(func, assigned=True)

Constraint which wraps a function defining the constraint logic.

Examples

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> def func(a, b):
...     return b > a
>>> problem.addConstraint(func, ["a", "b"])
>>> problem.getSolution()
{'a': 1, 'b': 2}

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> def func(a, b):
...     return b > a
>>> problem.addConstraint(FunctionConstraint(func), ["a", "b"])
>>> problem.getSolution()
{'a': 1, 'b': 2}

Initialization method.

Parameters:

  • func (callable object) – Function wrapped and queried for constraint logic

  • assigned (bool) – Whether the function may receive unassigned variables or not

class constraint.AllDifferentConstraint

Constraint enforcing that values of all given variables are different.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(AllDifferentConstraint())
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]
class constraint.AllEqualConstraint

Constraint enforcing that values of all given variables are equal.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(AllEqualConstraint())
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 1)], [('a', 2), ('b', 2)]]
class constraint.MaxSumConstraint(maxsum, multipliers=None)

Constraint enforcing that values of given variables sum up to a given amount.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(MaxSumConstraint(3))
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 1)], [('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]

Initialization method.

Parameters:

  • maxsum (number) – Value to be considered as the maximum sum

  • multipliers (sequence of numbers) – If given, variable values will be multiplied by the given factors before being summed to be checked

preProcess(variables, domains, constraints, vconstraints)

Preprocess variable domains.

This method is called before starting to look for solutions, and is used to prune domains with specific constraint logic when possible. For instance, any constraints with a single variable may be applied on all possible values and removed, since they may act on individual values even without further knowledge about other assignments.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.ExactSumConstraint(exactsum, multipliers=None)

Constraint enforcing that values of given variables sum exactly to a given amount.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(ExactSumConstraint(3))
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]

Initialization method.

Parameters:

  • exactsum (number) – Value to be considered as the exact sum

  • multipliers (sequence of numbers) – If given, variable values will be multiplied by the given factors before being summed to be checked

preProcess(variables, domains, constraints, vconstraints)

Preprocess variable domains.

This method is called before starting to look for solutions, and is used to prune domains with specific constraint logic when possible. For instance, any constraints with a single variable may be applied on all possible values and removed, since they may act on individual values even without further knowledge about other assignments.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.MinSumConstraint(minsum, multipliers=None)

Constraint enforcing that values of given variables sum at least to a given amount.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(MinSumConstraint(3))
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)], [('a', 2), ('b', 2)]]

Initialization method.

Parameters:

  • minsum (number) – Value to be considered as the minimum sum

  • multipliers (sequence of numbers) – If given, variable values will be multiplied by the given factors before being summed to be checked

class constraint.MaxProdConstraint(maxprod)

Constraint enforcing that values of given variables create a product up to at most a given amount.

Instantiate a MaxProdConstraint.

Parameters:

maxprod – Value to be considered as the maximum product

preProcess(variables, domains, constraints, vconstraints)

Preprocess variable domains.

This method is called before starting to look for solutions, and is used to prune domains with specific constraint logic when possible. For instance, any constraints with a single variable may be applied on all possible values and removed, since they may act on individual values even without further knowledge about other assignments.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.MinProdConstraint(minprod)

Constraint enforcing that values of given variables create a product up to at least a given amount.

Instantiate a MinProdConstraint.

Parameters:

minprod – Value to be considered as the maximum product

preProcess(variables, domains, constraints, vconstraints)

Preprocess variable domains.

This method is called before starting to look for solutions, and is used to prune domains with specific constraint logic when possible. For instance, any constraints with a single variable may be applied on all possible values and removed, since they may act on individual values even without further knowledge about other assignments.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.InSetConstraint(set)

Constraint enforcing that values of given variables are present in the given set.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(InSetConstraint([1]))
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 1)]]

Initialization method.

Parameters:

set (set) – Set of allowed values

preProcess(variables, domains, constraints, vconstraints)

Preprocess variable domains.

This method is called before starting to look for solutions, and is used to prune domains with specific constraint logic when possible. For instance, any constraints with a single variable may be applied on all possible values and removed, since they may act on individual values even without further knowledge about other assignments.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.NotInSetConstraint(set)

Constraint enforcing that values of given variables are not present in the given set.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(NotInSetConstraint([1]))
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 2), ('b', 2)]]

Initialization method.

Parameters:

set (set) – Set of disallowed values

preProcess(variables, domains, constraints, vconstraints)

Preprocess variable domains.

This method is called before starting to look for solutions, and is used to prune domains with specific constraint logic when possible. For instance, any constraints with a single variable may be applied on all possible values and removed, since they may act on individual values even without further knowledge about other assignments.

Parameters:

  • variables (sequence) – Variables affected by that constraint, in the same order provided by the user

  • domains (dict) – Dictionary mapping variables to their domains

  • constraints (list) – List of pairs of (constraint, variables)

  • vconstraints (dict) – Dictionary mapping variables to a list of constraints affecting the given variables.

class constraint.SomeInSetConstraint(set, n=1, exact=False)

Constraint enforcing that at least some of the values of given variables must be present in a given set.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(SomeInSetConstraint([1]))
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 1)], [('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]

Initialization method.

Parameters:

  • set (set) – Set of values to be checked

  • n (int) – Minimum number of assigned values that should be present in set (default is 1)

  • exact (bool) – Whether the number of assigned values which are present in set must be exactly n

class constraint.SomeNotInSetConstraint(set, n=1, exact=False)

Constraint enforcing that at least some of the values of given variables must not be present in a given set.

Example

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2])
>>> problem.addConstraint(SomeNotInSetConstraint([1]))
>>> sorted(sorted(x.items()) for x in problem.getSolutions())
[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)], [('a', 2), ('b', 2)]]

Initialization method.

Parameters:

  • set (set) – Set of values to be checked

  • n (int) – Minimum number of assigned values that should not be present in set (default is 1)

  • exact (bool) – Whether the number of assigned values which are not present in set must be exactly n