Skip to main content

A simple constraints satisfaction solver

Project description


A simple, constraints satisfaction problem solver. Used for the [YACS][] course
scheduler project.



The Problem is the primary interface:

>>> from pyconstraints import Problem

And then specify your problem to solve with various constraints:

>>> p = Problem()
>>> p.add_variable('x', range(4)) # variable-name, domain
>>> p.add_variable('y', range(4))
# give constraint function and list of variables used
>>> p.add_constraint(lambda x, y: x != y, ['x', 'y'])
>>> p.add_constraint(lambda x: x % 2 == 0)

Then get your solutions:

>>> p.get_solutions()
# => ({'y': 0, 'x': 2},
# {'y': 1, 'x': 0},
# {'y': 1, 'x': 2},
# {'y': 2, 'x': 0},
# {'y': 3, 'x': 0},
# {'y': 3, 'x': 2})

Or iteratively:

>>> p.iter_solutions().next()
# => {'y': 0, 'x': 2}

And that's it!

Using Another Solver

Simply pass the solver to the Problem constructor:

>>> from pyconstraints import BruteForceSolver, BacktrackingSolver
>>> p = Problem(BacktrackingSolver()) # BruteForceSolver is default

Because the BruteForceSolver uses itertools, there may be cases where it is
faster than the BacktrackingSolver.

Writing Your Own Solver

For convinence, there is a ``pyconstraints.SolverInterface`` Abstract-Base Class if you want to
implement all the features manually:

def solutions_seen(self):
"Returns the number of solutions currently seen by the solver."

def solutions_at_points(self):
"""Returns a dictionary of {iteration_index: solution} of all known
solutions while iterating.

def set_conditions(self, variables, constraints):
"""Called by the Problem class to assign the variables and constraints
for the problem.

variables = {variable-name: list-of-domain-values}
constraints = [(constraint_function,

def restore_point(self, starting_point=None):
"Restores the iteration state to a given starting point."

def save_point(self):
"""Returns data to indicate a way to restore to the current iteration

def __iter__(self):
"Yields solutions."

But for convinence, you can inherit from the ``pyconstraints.SolverBase`` class
which provides a primitive implementation for all the interface methods except
for ``__iter__`` and ``set_conditions``.


- Speed up backtracking solver
- Add more solvers?

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution (8.6 kB view hashes)

Uploaded source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page