~/Building Constraint Solvers in Python

Mar 15, 2019


Constraint solvers are key in fields such as operations research, artificial intelligence, scheduling, and resource allocation. This article outlines how to implement constraint satisfaction problem (CSP) solvers using Python.

Constraint solvers handle a set of variables and domains, subject to constraints. The solver finds assignments that satisfy all constraints.

Constraint Representation

A CSP defines variables X, domains D for each variable, and constraints C. For example, Sudoku can be represented as a CSP. Common constraint types include unary, binary, and global constraints.

Python Libraries

There are multiple libraries for CSP in Python such as python-constraint, Numberjack, OR-Tools, and PyCSP.

Core Algorithm

The backtracking search algorithm is a fundamental technique. Enhancements include forward checking and arc consistency.

Basic Backtracking Example

Here is a simple Python backtracking search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def is_consistent(assignment, var, value, constraints):
    for constraint in constraints:
        if not constraint(assignment, var, value):
            return False
    return True

def backtrack(variables, domains, constraints, assignment={}):
    if len(assignment) == len(variables):
        return assignment
    unassigned = [v for v in variables if v not in assignment]
    var = unassigned[0]
    for value in domains[var]:
        if is_consistent(assignment, var, value, constraints):
            assignment[var] = value
            result = backtrack(variables, domains, constraints, assignment)
            if result:
                return result
            assignment.pop(var)
    return None

Defining Constraints

A constraint is a function that checks if an assignment is valid. Example for not-equal constraint:

1
2
3
4
5

def not_equal(assignment, var, value):
    for k, v in assignment.items():
        if v == value:
            return False
    return True

Solving N-Queens Problem

The N-Queens problem is a classic CSP. See N-Queens explanation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def queen_constraint(assignment, var, value):
    for k, v in assignment.items():
        if abs(var - k) == abs(value - v) or value == v:
            return False
    return True

n = 8
variables = list(range(n))
domains = {i: list(range(n)) for i in variables}
constraints = [queen_constraint]
solution = backtrack(variables, domains, constraints)
print(solution)

Advanced Features

Efficient solvers employ techniques like arc consistency (AC-3), domain reduction, path consistency and heuristics for variable and value ordering.

Using python-constraint Library

A higher-level interface is available via python-constraint:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from constraint import Problem, AllDifferentConstraint

problem = Problem()
problem.addVariables(range(8), range(8))
problem.addConstraint(AllDifferentConstraint())
problem.addConstraint(
    lambda *args: len(set(args[i] + i for i in range(8))) == 8
)
problem.addConstraint(
    lambda *args: len(set(args[i] - i for i in range(8))) == 8
)
solutions = problem.getSolutions()
print(solutions)

Applications

Constraint solvers are used in scheduling, configuration, resource allocation, timetabling, and AI planning.

See Google OR-Tools documentation and MiniZinc for more on constraint solvers in practice. For theoretical concepts, refer to Russell and Norvig’s AI textbook.

Tags: [python] [constraints] [solver] [programming]