NuCS vs Choco: A Pure-Python Constraint Solver Meets a JVM Veteran

NuCS is a constraint solver written 100% in Python, developed by me, accelerated by NumPy and Numba. Choco is one of the reference open-source constraint solvers, written in Java and developed for more than two decades.

Comparing them looks lopsided: an interpreted language against a heavily optimized JVM solver with a rich catalog of arc-consistent global constraints. The reality is more interesting. When both solvers run the same model they are, for all practical purposes, the same speed — and on the largest instances NuCS actually pulls ahead, because once Numba has compiled the inner loops the Python tax is gone and only the cost-per-node remains. When the models differ the result is a genuine trade rather than a rout: on some problems Choco’s arc consistency is the right, fast tool; on others NuCS’s cheap bound consistency plus a little remodeling wins outright; and on at least one problem NuCS’s modeling freedom lets it solve instances that neither plain solver can.

This article walks through five benchmark problems, gives the exact NuCS command line for each, details the constraints and search strategy, draws the performance curves, and ends on the design decision that explains the whole picture: NuCS represents domains as min..max intervals and is therefore limited to bound consistency, while Choco can also represent domains with holes and run full arc consistency.

All NuCS code shown here lives in the NuCS repository under the MIT license.

NuCS

History

NuCS is a project I recently started. Its first public release date is from 2024, and it has iterated very quickly since — the version benchmarked here is 11.2.0. It was built around a deliberately unusual bet: write a competitive finite-domain constraint solver entirely in Python, and recover the performance normally lost to interpretation through just-in-time compilation rather than a C or C++ core. It is distributed on PyPI (pip install nucs), which keeps installation as simple as any other Python package — no native toolchain, no JVM.

Architecture

A Problem carries a NumPy array of variable domains — one (min, max) pair per variable, a variable being bound when min == max — together with a list of propagators. A propagator is a constraint’s filtering algorithm, registered under a numeric ALG_* identifier. Each propagator is three small functions:

• compute_domains_* — the actual filtering, returning inconsistency, consistency, or entailment;
• get_triggers_* — which domain events should re-wake the propagator;
• get_complexity_* — a cost estimate used to order the propagation queue.

The BacktrackSolver interleaves propagation-to-a-fixpoint with a branching decision, chosen by a variable heuristic (which unbound variable to branch on) and a domain heuristic (which value to try). A MultiprocessingSolver fans several backtracking searches out over a split of the search space.

What makes this fast despite being Python is that essentially every hot function is decorated with @njit(cache=True, fastmath=True). Numba compiles these to native code on first use and caches the result on disk, so a warm process runs compiled machine code, not interpreted bytecode. Domains are plain NumPy arrays mutated in place, and propagators exchange typed NDArrays and integers — never Python objects. The price is a cold-start compilation (mitigated by the cache) and a coding discipline inside jitted code: no dictionaries, no exceptions, no isinstance, no strings. The payoff is twofold: C-like throughput, and cheap, fast modeling — adding a redundant constraint, swapping a heuristic, or writing a problem-specific consistency algorithm is a handful of lines of ordinary Python. As we will see, that second property is where several of NuCS’s wins come from.

The single most consequential design choice is that a domain is always an interval. There is no representation for a hole in the middle of a domain, which is exactly what makes the whole engine expressible as operations on two NumPy arrays — and what limits NuCS to bound consistency. We will return to this at the end; it is the thread running through every result below.

Choco

History

Choco is a veteran of the constraint-programming world. It first appeared around the turn of the 2000s and has been through several full rewrites. The modern lineage — Choco 3, then 4, and now 6 — is a ground-up redesign developed largely at IMT Atlantique (the TASC / LS2N research group in Nantes) by Charles Prud’homme, Jean-Guillaume Fages and contributors. It is an open-source Java library, distributed under a BSD license, and is widely used in both research and industry. The version benchmarked here is 6.0.1, a current release.

Architecture

Choco is an event-based constraint solver on the JVM. A Model holds integer, boolean, set and real variables together with Constraints; each constraint delegates filtering to one or more propagators driven by a fine-grained event/propagation engine. On top sits a configurable search loop with a large library of branching strategies, restart policies, and — historically a distinctive feature — explanations (conflict-based learning).

Where Choco fundamentally differs from NuCS is in its domain representation: it supports both bounded domains (intervals, like NuCS) and enumerated domains (bitsets), which can represent arbitrary subsets — domains with holes. That richer representation is what unlocks the breadth and strength of its global-constraint catalog: allDifferent at several consistency levels (including Régin’s arc-consistent algorithm), cardinality and counting constraints, cumulative, circuit, automaton/regular constraints, and many more, most backed by carefully engineered, often arc-consistent, filtering.

A mature JVM solver brings two things a young Python project cannot match today: a JIT (HotSpot) tuned over twenty years, and a deep library of strong global constraints you can drop into a model and trust. The flip side is that those strong filters are also where Choco can become expensive: arc-consistent global constraints do a lot of work per node, and that work does not always pay for itself.

The comparison setup

A few honest caveats before reading any number:

• All timings are in milliseconds, measured on the same machine. Cross-language micro-benchmarks are always approximate; treat ratios and curve shapes, not absolute values, as the signal.
• NuCS timings are taken after the Numba JIT cache is warm — the one-off compilation cost is not what we want to measure. Even warm, NuCS pays a small fixed startup cost of a few hundred milliseconds (reading the cache, warming NumPy) that you can see as a floor on the smallest instances. It is paid once per process, not per search node, so it is noise for a long solve and dominant for a tiny one.
• Every NuCS run uses the cache directory and the same options pattern; the leading NUMBA_CACHE_DIR=.numba/cache and the trailing --no-display-solutions --no-display-stats --log-level ERROR (which just silence output) are elided from the command lines below for readability.
• Each problem shows the NuCS command line, the constraints and search strategy, a curve diagram (lower is better), the raw table, and a short analysis. In any “speedup” column, a value greater than 1 means NuCS is faster by that factor.

The five problems split naturally into two groups: those where both solvers run essentially the same model (so we are comparing engines) and those where the models differ (so we are comparing modeling strategies as much as engines).

Group1 — same model, comparing engines

Here both solvers post the same constraints with the same consistency level and a comparable search strategy. The only thing under test is the engine.

All-interval series (find one solution)

The problem (CSPLIB #7). An all-interval series is a permutation of the integers 0..n-1 such that the sequence of absolute differences between consecutive terms is itself a permutation of 1..n-1 — every interval appears exactly once. The name comes from twelve-tone music, where such a series sounds each interval once; combinatorially it is a compact, tightly coupled permutation problem that stresses an allDifferent over both the values and their differences. We look for a single solution.

Both solvers use bound consistency and a first-fail (smallest-domain) heuristic on the same formulation.

NuCS command line:

python ‐m nucs.examples.all_interval_series -n 500 --var-heuristic 3 --symmetry-breaking --cp-max-height 10000

Constraints and strategy. For each i, a SUM_EQ propagator defines diff_i = x_{i+1} - x_i and an ABS_EQ propagator defines |diff_i|; two ALLDIFFERENTs enforce that the values and the absolute differences are each a permutation; two LEQ_C propagators break the obvious reversal/complement symmetries. --var-heuristic 3 selects the smallest-domain variable heuristic (first-fail), branching only on the n series variables (decision_variables).

for i in range(n - 1):
    self.add_propagator(ALG_SUM_EQ, [n + i, i, i + 1])  # diff_i = x_{i+1} - x_i
    self.add_propagator(ALG_ABS_EQ, [n + i, 2 * n - 1 + i])  # |diff_i|
self.add_propagator(ALG_ALLDIFFERENT, range(n))
self.add_propagator(ALG_ALLDIFFERENT, range(2 * n - 1, 3 * n - 2))
if symmetry_breaking:
    self.add_propagator(ALG_LEQ_C, [0, 1], [-1])
    self.add_propagator(ALG_LEQ_C, [3 * n - 3, 2 * n - 1], [-1])

This is the most telling chart in the whole benchmark because nothing differs except the engine — and for the first five sizes the two curves sit on top of each other (within ~3%). Then at n=16000 they separate: Choco takes 120 s, NuCS 85 s — NuCS is 1.41× faster. A pure-Python solver not merely matching but beating Choco on an identical model is the headline result: once Numba has compiled the propagators, NuCS’s vectorized per-node work is genuinely competitive, and on the biggest instance its lower constant factor wins.

Schur’s lemma (prove no solution)

The problem (CSPLIB #15). Schur’s lemma asks whether the integers 1..n can be split into a given number of sum-free sets — sets containing no triple x, y, z with x + y = z (where x and y need not be distinct). With three sets there is a largest n for which a valid partition exists (tied to the Schur number S(3) = 13); beyond it the problem is infeasible. We use it here as an unsatisfiable instance, which forces the solver to exhaust the entire search tree to prove that no partition exists — a clean test of raw propagation throughput.

Both solvers use bound consistency, and to keep the models identical the run is done without symmetry breaking.

NuCS command line:

python ‐m nucs.examples.schur_lemma -n 100 --no-symmetry-breaking

Constraints and strategy. Each of the n numbers gets three 0/1 membership variables; a SUM_EQ_C forces it into exactly one set; for every valid triple (x, y, z = x+y+1) a SUM_LEQ_C forbids all three being in the same set (the sum-free condition). With --no-symmetry-breaking the LEXICOGRAPHIC_LEQ ordering constraint is dropped so the model matches Choco’s. The default variable heuristic drives the search.

for x in range(n):
    self.add_propagator(ALG_SUM_EQ_C, [x * 3, x * 3 + 1, x * 3 + 2], [1])
for k in range(3):
    for x in range(n):
        for y in range(n):
            z = x + y + 1
            if 0 <= z < n:
                self.add_propagator(ALG_SUM_LEQ_C, [3 * x + k, 3 * y + k, 3 * z + k], [2])

At the smallest size Choco is genuinely faster — about 2×. But watch the gap close monotonically as the tree grows: 0.47× → 0.61× → 0.67× → 0.87× → 1.22×. That shrinking deficit is NuCS’s roughly constant per-process overhead being amortized against a growing absolute runtime; by n=1600 it has not just vanished, it has reversed — NuCS proves infeasibility in 14.6 s against Choco’s 17.9 s. NuCS pays a setup cost here, not an algorithmic one, and once the search is large enough its cheaper per-node propagation comes out ahead.

Takeaway for Group 1. When the model is fixed, NuCS and Choco run at essentially the same asymptotic speed — and at the largest sizes NuCS edges in front on both problems. The only visible disadvantage is a small, constant NuCS startup cost that dominates tiny instances and is irrelevant on large ones. For a pure-Python solver against a two-decade-old JVM engine, that is a remarkable result.

Group 2 — different models, comparing strategies

On these three problems the two solvers do not run the same algorithm, so we are comparing modeling strategies as much as engines. Choco reaches for strong, arc-consistent global constraints or enumerated domains; NuCS reaches for cheap bound consistency plus redundant constraints, channeling, or a hand-written filter. The results are mixed — and that is the honest, interesting part.

Latin square (find one solution)

The problem. A Latin square of order n is an n×n grid filled with n symbols so that each symbol occurs exactly once in every row and exactly once in every column — equivalently, every row and every column is a permutation of 0..n-1. It is the abstract structure behind Sudoku (which adds box constraints) and underlies many combinatorial designs. Latin squares exist for every n, so finding one is easy in principle; the interest here is how well a constraint model’s propagation scales as n grows. We look for a single solution.

The straightforward model, used by both solvers, posts a bound-consistent allDifferent per row and per column.

NuCS command lines:

# plain bound-consistent model
python -m nucs.examples.latin_square \
  -n 20 --cp-max-height 10000

# redundant (row/column) model
python -m nucs.examples.latin_square \
  -n 20 --model-rc --cp-max-height 10000

Constraints and strategy. The plain model is just 2n ALLDIFFERENT propagators (one per row, one per column) over the n² cell variables, with the default first-not-instantiated branching:

for i in range(self.n):
    self.add_propagator(ALG_ALLDIFFERENT, self.row(i))
    self.add_propagator(ALG_ALLDIFFERENT, self.column(i))

The redundant model (--model-rc, class LatinSquareRCProblem) adds two extra views of the same grid — one indexed by (color, column) → row, one by (row, color) → column — each with its own row/column ALLDIFFERENTs, and links the three views with channeling (PERMUTATION_AUX) constraints, so that pruning found in one view immediately propagates to the others:

# row[c,j]=i  <=>  color[i,j]=c
self.add_propagator(ALG_PERMUTATION_AUX, [*self.column(j), *self.column(j, M_ROW)])
# row[c,j]=i  <=>  column[i,c]=j
self.add_propagator(ALG_PERMUTATION_AUX, [*self.row(c, M_ROW), *self.column(c, M_COLUMN)])
# color[i,j]=c  <=>  column[i,c]=j
self.add_propagator(ALG_PERMUTATION_AUX, [*self.row(i), *self.row(i, M_COLUMN)])

Two things to read here. First, on the same plain-BC model, Choco is faster than NuCS on the small solvable instances — the familiar constant-overhead gap, with NuCS sitting on its ~376 ms floor while Choco starts near 105 ms. Second, and more important: both plain-BC models fall off a cliff at order 50 and fail to finish. The plain formulation simply does not prune enough, and that is an algorithmic wall, not an engine one — Choco hits it too.

The NuCS redundant model walks straight past that wall. Its curve is almost flat (412 → 728 ms while the order grows from 20 to 50) because the channeled views prune so much that search barely expands. The win here is not a tidy speedup ratio; it is qualitative — NuCS solves, in well under a second, an instance that neither plain-BC solver can finish at all. And the thing that made it possible is not the engine but the ease of remodeling: a couple of extra propagator loops in ordinary Python./h

Magic sequence (find one solution)

The problem (CSPLIB #19). A magic sequence of length n is a self-descriptive sequence x_0, …, x_{n-1} of non-negative integers in which each x_i counts exactly how many times the value i appears in the whole sequence. The twist is that every variable both contributes to and depends on the counts, which makes this a classic stress test of counting and cardinality constraints. We look for a single solution.

Choco’s natural model uses a strong arc-consistent global constraint. NuCS uses only simple count constraints plus redundant linear constraints.

NuCS command lines:

# count + one redundant linear constraint
python -m nucs.examples.magic_sequence \
  -n 100 --var-heuristic 3 --model-r1

# adds a second, weighted-sum redundant constraint
python -m nucs.examples.magic_sequence \
  -n 100 --var-heuristic 3 --model-r1 --model-r2

Constraints and strategy. For each i, a COUNT_EQ propagator ties x_i to the number of cells equal to i. The first redundant constraint (--model-r1, a SUM_EQ_C) states that the values must sum to n; the second (--model-r2, an AFFINE_EQ) is a weighted-sum identity Σ i·x_i = n. Both runs use the smallest-domain (first-fail) heuristic via --var-heuristic 3.

for i in range(n):
    self.add_propagator(ALG_COUNT_EQ, list(range(n)) + [i], [i])
if model_r1:
    self.add_propagator(ALG_SUM_EQ_C, range(n), [n])            # redundant: values sum to n
if model_r2:
    self.add_propagator(ALG_AFFINE_EQ, range(n), range(n + 1))  # redundant: weighted-sum identity

This is the most dramatic crossover of the set. Choco’s arc-consistent filtering is excellent on small instances: at n=100 it is ~2.5× faster than the best NuCS model. But its curve climbs much faster — Choco grows ~12× from n=100 to n=400 (149 → 1783 ms), while the two-redundant NuCS model grows only ~2.4× (387 → 942 ms). The lines cross around n=250, and by n=400 NuCS is 1.89× faster — 942 ms against Choco’s 1783 ms. The second redundant constraint is what does it: comparing the orange and green curves, adding Σ i·x_i = n cuts the n=400 time from 2913 ms to 942 ms. The reading is not “AC is wasteful” — it clearly pays on small instances — but “cheap BC plus the right pair of redundant constraints has a far flatter cost-per-node, and overtakes decisively as the instance grows.”

Golomb ruler (minimize)

The problem (CSPLIB #6). A Golomb ruler is a set of n integer marks placed on a ruler such that all n(n-1)/2 pairwise distances between marks are distinct. An optimal Golomb ruler is one of minimal total length for a given number of marks. It is a deceptively small optimization problem that becomes very hard as the number of marks grows, and a staple benchmark for both pruning strength and the payoff of representing holes in domains. We minimize the length.

Golomb is the most interesting comparison because it leans hardest on domain representation: find n marks 0 = m_0 < m_1 < … < m_{n-1} whose pairwise distances are all different, minimizing m_{n-1}. Choco’s sample uses enumerated domains — effectively stronger consistency — which lets it prune values in the middle of the distance intervals. Plain NuCS bound consistency cannot do that, and it shows. So NuCS offers a problem-specific consistency algorithm: a few dozen lines of jitted Python (golomb_consistency_algorithm) that pre-prune the distance variables with a minimal-sum-of-distinct-integers argument before running standard bound consistency.

NuCS command lines:

# plain bound consistency (--consistency-algorithm 0 forces BC)
python -m nucs.examples.golomb \
  -n 9 --symmetry-breaking --consistency-algorithm 0

# custom Golomb consistency algorithm (the example's default)
python -m nucs.examples.golomb \
  -n 9 --symmetry-breaking

Constraints and strategy. Distance variables dist_ij are tied by SUM_EQ (dist_ij = m_j − m_i), a single ALLDIFFERENT enforces all distances distinct, redundant LEQ_C bounds relate each distance to the ruler length, and a LEQ_C breaks the mirror symmetry. The objective m_{n-1} is minimized with solver.minimize(...). The custom variant swaps the plain bound-consistency algorithm for golomb_consistency_algorithm, which tightens the distance lower bounds before delegating to bound_consistency_algorithm; --consistency-algorithm 0 overrides that back to plain BC for the comparison.

for i in range(1, mark_nb - 1):
    for j in range(i + 1, mark_nb):
        self.add_propagator(ALG_SUM_EQ, [index(mark_nb, 0, i), index(mark_nb, i, j), index(mark_nb, 0, j)])
self.add_propagator(ALG_ALLDIFFERENT, range(self.domain_nb))
# redundant length bounds + symmetry breaking omitted for brevity

Plain NuCS BC (orange) is about 2× slower than Choco across the board — exactly the penalty you would expect when the opponent can prune holes you cannot. But the custom-consistency variant (green) closes the gap almost perfectly: at 11 marks, 6791 ms vs Choco’s 6800 ms; at 12 marks, 67319 ms vs 65705 ms — within ~2%. NuCS does not need enumerated domains to recover the missing pruning; it needs a dedicated propagator that encodes the same logic. The cost is developer effort, not solver capability.

What the numbers say

• Equal models, equal speed — then NuCS edges ahead. When both solvers run the same algorithm, NuCS matches Choco through the mid sizes and wins on the largest instances of both problems (all-interval series and Schur’s lemma). The only visible gap is a small, constant NuCS startup overhead that vanishes as the search grows.
• Stronger consistency often pays — but its cost-per-node grows. On magic sequence Choco’s arc-consistent global constraint is faster on small instances, yet NuCS’s lightweight BC plus two redundant constraints has a far flatter slope and is nearly 2× faster by n=400.
• Modeling freedom can change feasibility, not just speed. On Latin square the plain BC model walls out at order 50 for both solvers; NuCS’s redundant channeling model solves it in 728 ms — because remodeling in Python is cheap.
• Sometimes AC really is decisive. On Golomb ruler, enumerated domains give Choco pruning that plain BC simply cannot reproduce — and NuCS only catches up by writing a custom propagator.

The root cause: domains and consistency

Step back from the individual problems and one design decision explains the whole picture.

NuCS represents each variable domain as a single min..max interval. A domain is two integers; binding a variable means min == max. This is compact, cache-friendly, and trivially vectorizable with NumPy — which is precisely what lets Numba make the propagators so fast. But it has a hard consequence: NuCS can only shrink the bounds of a domain. It cannot punch a hole in the middle. The strongest filtering it can express is therefore bound consistency (BC) — it guarantees the endpoints of each domain are supported, nothing more.

Choco represents domains with holes (bitset / enumerated representations alongside bounded ones). It can remove an arbitrary value from the middle of a domain. That is what makes arc consistency (AC) possible: a filtering algorithm can delete every unsupported value, not just trim the extremes. Choco’s catalog leans into this — allDifferent (AC), arc-consistent cardinality and counting constraints, enumerated-domain propagation — and these are exactly the constraints behind its results on magic sequence and Golomb above.

So the two solvers occupy genuinely different points in the design space:

And here is the nuance the benchmarks reveal. NuCS’s “weaker” consistency is rarely the disadvantage it looks like on paper. Because BC propagators are so cheap, and because remodeling in Python is so easy, the productive move in NuCS is to recover the missing pruning with redundant constraints, channeling, or a custom filter rather than with an expensive AC algorithm. On magic sequence that lower per-node cost lets BC pass Choco’s arc-consistent global constraint decisively once the instance is large; on Latin square it is the difference between solving order 50 and not solving it at all; and even on the identical models of Group 1, the lower constant factor is what puts NuCS ahead at the top end.

The flip side is just as real. When a problem genuinely needs values removed from the middle of domains, Choco’s arc-consistent globals and enumerated domains are the right tool out of the box — fast on small magic-sequence instances and ahead on Golomb until NuCS answers with hand-written code. Choco gives you that strength for free; NuCS makes you build it, but lets you build it in a few lines.

Conclusion

Reading the benchmark as “which solver is faster” misses the point. Two different things are being measured:

1. Same model, comparing engines (all-interval series, Schur’s lemma). The two are essentially tied through the mid range, separated only by a small constant NuCS startup cost — and on the largest instance of each problem NuCS pulls ahead (1.41× on all-interval at n=16000, 1.22× on Schur at n=1600). That a pure-Python solver runs within a hair of a mature, two-decade-old JVM solver and then overtakes it at scale is the most pleasantly surprising outcome. Numba does not just close the Python penalty; the resulting per-node cost is genuinely low.
2. Different models, comparing strategies (magic sequence, Golomb ruler, Latin square). Here it is a genuine trade. Choco’s arc consistency is fast and decisive on some instances (small magic sequences, Golomb); NuCS’s cheap BC plus redundant constraints has a flatter cost curve and wins big at scale on others (large magic sequences, ~1.9×), recovers parity where AC led (Golomb, with a custom propagator), and — thanks to how cheap remodeling is — solves a Latin square that neither plain-BC model can.

Underneath both observations lies one architectural fact. NuCS stores domains as min..max intervals and is therefore limited to bound consistency; Choco stores domains with holes and can run arc consistency. That is the honest, lasting difference between the two solvers. It is why Choco ships strong AC global constraints that NuCS cannot replicate directly, and it is also why NuCS’s cheap-BC-plus-redundant-constraints style can compete — and increasingly win — when a good redundant model exists. Neither approach dominates; they are different bets.

For someone who wants Choco’s breadth of battle-tested, arc-consistent global constraints, mature search infrastructure, and explanations, Choco remains the reference. For someone who wants to experiment with models in Python and still get native-code speed, NuCS makes a strong case: the language is no longer the bottleneck, and the freedom to reshape the model — adding redundancy, channeling, or a custom BC filter in a few lines — often matters as much as raw engine speed or raw consistency strength.

Some useful links to go further with NuCS: