NuCS: A Constraint Solver for Research, Teaching, and Production Applications

Blazing-fast constraint solving in pure Python

TLDR

and 

The 14200 solutions to the 12-queens problems are found in less than 2s on a MacBook Pro M2 running:

• Python 3.11,
• Numpy 2.0.1,
• Numba 0.60.0 and
• NuCS 3.0.0.

(venv) ➜  nucs git:(main) time NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12 --log_level=ERROR --processors=6
{
    'ALG_BC_NB': 262006,
    'ALG_BC_WITH_SHAVING_NB': 0,
    'ALG_SHAVING_NB': 0,
    'ALG_SHAVING_CHANGE_NB': 0,
    'ALG_SHAVING_NO_CHANGE_NB': 0,
    'PROPAGATOR_ENTAILMENT_NB': 0,
    'PROPAGATOR_FILTER_NB': 2269965,
    'PROPAGATOR_FILTER_NO_CHANGE_NB': 990435,
    'PROPAGATOR_INCONSISTENCY_NB': 116806,
    'SOLVER_BACKTRACK_NB': 131000,
    'SOLVER_CHOICE_NB': 131000,
    'SOLVER_CHOICE_DEPTH': 10,
    'SOLVER_SOLUTION_NB': 14200
}
NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12    6.65s user 0.53s system 422% cpu 1.699 total

What is constraint programming ?

Constraint programming is a paradigm for solving combinatorial problems. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints specify the properties of a solution to be found. The solver combines constraint propagation and backtracking to find the solutions.

As an example, here is a model for the for a complete list of propagator supported by NuCS. Note that most propagators in NuCS are global (aka n-ary) and implement state-of-art propagation algorithms.

Python

Python is the language of choice for data scientists: it has a simple syntax, a growing community and a great number of data science and machine learning libraries.

But on the other hand, Python is known to be a slow language : maybe 50 to 100 times slower than C depending on the benchmarks.

The choice of Python for developing a high performance constraint programming library was not so obvious but we will see that the combined use of Numpy (high performance computing package) and Numba (Just-In-Time compilation for Python) helps a lot.

Many attempts have been made to write constraint solvers in Python, but these are either slow or are only wrappers and depend on external solvers written in Java or C/C++.

Numpy

In NuCS, everything is a Numpy array.

This allows to leverage Numpy's indexing and broadcasting capabilities and to write compact propagators such as Max_i x_i <= y

def compute_domains_max_leq(domains: NDArray, parameters: NDArray) -> int:
  x = domains[:-1]
  y = domains[-1]
  if np.max(x[:, MAX]) <= y[MIN]:
      return PROP_ENTAILMENT
  y[MIN] = max(y[MIN], np.max(x[:, MIN]))
  if y[MIN] > y[MAX]:
      return PROP_INCONSISTENCY
  for i in range(len(x)):
      x[i, MAX] = min(x[i, MAX], y[MAX])
      if x[i, MAX] < x[i, MIN]:
          return PROP_INCONSISTENCY
  return PROP_CONSISTENCY

Numba

Numba is an open source Just-In-Time compiler that translates a subset of Python and NumPy code into fast machine code.

for the list of propagators implemented in NuCS),

Thanks to Numpy and Numba, NuCS achieves performance similar to that of solvers written in Java or C/C++.

Note that, since the Python code is compiled and the result cached, performance will always be significantly better when you run your program a second time.

Examples

NuCS comes with many , the bible for anything CSP related.

Statistics and Logging

When solutions are searched for, NuCS also aggregates some

If you enjoyed this article about NuCS, please clap 50 times !

on Medium, where people are continuing the conversation by highlighting and responding to this story.