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 to use (default isBacktrackingSolver
)
- 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"]) >>> solutions = problem.getSolutions() >>>
- Parameters:
constraint (instance of
Constraint
or function to be wrapped byFunctionConstraint
) – Constraint to be included in the problemvariables (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.
- getSolutionsOrderedList(order=None)
Returns the solutions as a list of tuples, with each solution tuple ordered according to order.
- getSolver()
Obtain the problem solver currently in use.
Example
>>> solver = BacktrackingSolver() >>> 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() >>>
- 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.
- getSolutionIter(domains, constraints, vconstraints)
Return an iterator for the solutions of the given problem.
- getSolutions(domains, constraints, vconstraints)
Return all solutions for the given problem.
- 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.
- getSolutionIter(domains, constraints, vconstraints)
Return an iterator for the solutions of the given problem.
- getSolutions(domains, constraints, vconstraints)
Return all solutions for the given problem.
- 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.
- getSolutionIter(domains, constraints, vconstraints)
Return an iterator for the solutions of the given problem.
- getSolutions(domains, constraints, vconstraints)
Return all solutions for the given problem.
- getSolutionsList(domains, vconstraints)
Optimized all-solutions finder that skips forwardchecking and returns the solutions in a list.
- getSortedVariables(domains, vconstraints)
Sorts the list of variables on number of vconstraints to find unassigned variables quicker.
- Return type:
- 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.
- getSolutions(domains, constraints, vconstraints)
Return all solutions for the given problem.
- 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)
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)
- getSolution(domains, constraints, vconstraints)
Return one solution for the given problem.
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:
- Returns:
Boolean value stating if this constraint is currently broken or not
- Return type:
- 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.
- 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.