NUCS 2.0.0

A Numpy and Numba based Python library for solving Constraint Satisfaction Problems over finite domains

TLDR

NuCS is a Python library for solving Constraint Satisfaction and Optimization Problems. Because it is 100% written in Python, NuCS is easy to install and use. NuCS is also very fast because it is powered by Numpy and Numba.

Installation

pip install nucs

Documentation

Check out NUCS documentation.

With NuCS, in a few seconds you can ...

Find all 14200 solutions to the 12-queens problem

NUMBA_CACHE_DIR=.numba/cache PYTHONPATH=. python -m nucs.examples.queens -n 12

{
    'OPTIMIZER_SOLUTION_NB': 0,
    'PROBLEM_FILTER_NB': 262011,
    'PROBLEM_PROPAGATOR_NB': 3,
    'PROBLEM_VARIABLE_NB': 36,
    'PROPAGATOR_ENTAILMENT_NB': 0,
    'PROPAGATOR_FILTER_NB': 2269980,
    'PROPAGATOR_FILTER_NO_CHANGE_NB': 990450,
    'PROPAGATOR_INCONSISTENCY_NB': 116806,
    'SOLVER_BACKTRACK_NB': 131005,
    'SOLVER_CHOICE_NB': 131005,
    'SOLVER_CHOICE_DEPTH': 10,
    'SOLVER_SOLUTION_NB': 14200
}

Compute the 92 solutions to the BIBD(8,14,7,4,3) problem

NUMBA_CACHE_DIR=.numba/cache PYTHONPATH=. python -m nucs.examples.bibd -v 8 -b 14 -r 7 -k 4 -l 3 --symmetry_breaking

{
    'OPTIMIZER_SOLUTION_NB': 0,
    'PROBLEM_FILTER_NB': 2797,
    'PROBLEM_PROPAGATOR_NB': 462,
    'PROBLEM_VARIABLE_NB': 504,
    'PROPAGATOR_ENTAILMENT_NB': 5273,
    'PROPAGATOR_FILTER_NB': 562130,
    'PROPAGATOR_FILTER_NO_CHANGE_NB': 531724,
    'PROPAGATOR_INCONSISTENCY_NB': 1307,
    'SOLVER_BACKTRACK_NB': 1398,
    'SOLVER_CHOICE_NB': 1398,
    'SOLVER_CHOICE_DEPTH': 41,
    'SOLVER_SOLUTION_NB': 92
}

Demonstrate that the optimal 10-marks Golomb ruler length is 55

NUMBA_CACHE_DIR=.numba/cache PYTHONPATH=. python -m nucs.examples.golomb -n 10 --symmetry_breaking

{
    'OPTIMIZER_SOLUTION_NB': 10,
    'PROBLEM_FILTER_NB': 22886,
    'PROBLEM_PROPAGATOR_NB': 82,
    'PROBLEM_VARIABLE_NB': 45,
    'PROPAGATOR_ENTAILMENT_NB': 98080,
    'PROPAGATOR_FILTER_NB': 2843257,
    'PROPAGATOR_FILTER_NO_CHANGE_NB': 1806240,
    'PROPAGATOR_INCONSISTENCY_NB': 11406,
    'SOLVER_BACKTRACK_NB': 11405,
    'SOLVER_CHOICE_NB': 11470,
    'SOLVER_CHOICE_DEPTH': 9,
    'SOLVER_SOLUTION_NB': 10
}
[1, 6, 10, 23, 26, 34, 41, 53, 55]