Stop Writing Backtracking Loops: CLP(FD) in SWI-Prolog for Real Scheduling and Puzzle Problems

If you've ever written a scheduling allocator, a shift roster, or a puzzle generator by hand, you know the shape of the code: nested loops, partial-state checks, backtracking bookkeeping, and a growing pile of edge cases. The uncomfortable truth is that most of that code exists only to search — the actual problem statement ("no two meetings share a room", "every digit is distinct") is a few sentences long.

Constraint Logic Programming over Finite Domains — CLP(FD) — is a standard SWI-Prolog library that lets you state those sentences directly and let a built-in solver do the searching. This post shows the pattern, a complete worked example you can run, and the honest trade-offs.

The pattern: constrain, then label

Load the library with ?- use_module(library(clpfd)). in the SWI-Prolog top level (or put that directive at the top of a file). Every CLP(FD) program then follows two phases:

1. Constrain. Declare each variable's domain (X in 1..9) and the relationships between variables (all_different/1, arithmetic constraints like #=, #\=, #<). At this point nothing is "computed" — the solver just records the constraints and prunes values that can never work.
2. Label. Call label/1 or labeling/2 to trigger the actual search that assigns concrete values.

The separation is the engineering win. When a requirement changes — "oh, and room 3 is unavailable on Fridays" — you add one constraint line. You never touch the search code, because you never wrote any.

Why this beats generate-and-test

The naive alternative is to enumerate candidate assignments and check each one. CLP(FD) instead propagates: as soon as a constraint is posted, the solver removes impossible values from every variable's domain. If A #= B + C and B and C are both at least 5, then values below 10 vanish from A's domain immediately, before any guessing. Pruning before guessing is why a dozen lines of CLP(FD) routinely outrun pages of hand-rolled backtracking.

One caveat worth internalizing early: propagation is incomplete. The solver prunes locally per constraint, so search is still needed, and the order in which variables are tried matters a lot. That's what the options to labeling/2 are for — ff (first-fail: try the most constrained variable first) is the classic heuristic and can change runtime by orders of magnitude on some models.

Worked example: SEND + MORE = MONEY

The classic cryptarithmetic puzzle: assign distinct digits to the letters S, E, N, D, M, O, R, Y so that SEND + MORE = MONEY, with no leading zeros. Here is the entire solver:

:- use_module(library(clpfd)).

send_more_money(Vs) :-
    Vs = [S,E,N,D,M,O,R,Y],
    Vs ins 0..9,
    all_different(Vs),
    S #\= 0, M #\= 0,
    1000*S + 100*E + 10*N + D
  + 1000*M + 100*O + 10*R + E
  #= 10000*M + 1000*O + 100*N + 10*E + Y,
    labeling([ff], Vs).

Run it from the SWI-Prolog top level (no special permissions needed — it's an ordinary query):

?- send_more_money(Vs).
Vs = [9, 5, 6, 7, 1, 0, 8, 2] .

That is S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2 — i.e. 9567 + 1085 = 10652. Note that the arithmetic constraint uses #=, not is/2: is/2 requires a fully instantiated right-hand side, while #= works in both directions over partially known variables, which is what makes declarative modeling possible.

Verifying and stress-testing your model

Three practical checks before you trust a model:

• Run it. Confirm the query above returns the stated solution on your installed version. Predicate names and operators in library(clpfd) are stable in SWI-Prolog, but check the manual for your release if you adapt the code.
• Ask for another solution. Press ; at the top level after the first answer. For this puzzle there is exactly one solution, so the query should fail after the first result — a cheap way to confirm your constraints aren't under-specified. If you expected uniqueness and get a second answer, a constraint is missing.
• Compare labeling strategies. Try label(Vs) versus labeling([ff], Vs) on your own model and time both with time/1. On larger models the difference is often dramatic, and ff is not always the winner — measure, don't assume.

The honest trade-offs

CLP(FD) is not a universal solver. Keep these limits in mind:

• Performance cliffs are real. Constraint models can go from instant to hopeless with one added constraint or a slightly larger instance. Prototype early with realistic data sizes.
• It's not an industrial MILP/CP toolkit. For large production optimization (thousands of variables, tight SLAs), dedicated solvers with mature heuristics and benchmarking are usually the right call. CLP(FD) shines for modeling clarity, prototyping, and small-to-medium combinatorial problems.
• Portability is partial. SICStus and GNU Prolog have similar constraint libraries, and the modeling ideas transfer, but predicate names and options differ — expect to adjust code when moving systems.
• Debugging is different, not easier. When a model is unexpectedly slow or returns no solution, you inspect residual goals (clpfd:dump/3 and the top-level's residual output help) rather than stepping through loops. It's a learnable skill, but budget for it.

Where to start

Pick one small problem you currently solve with nested loops — a seating plan, a test-data generator, a roster — and rewrite it as domains plus constraints plus one labeling/2 call. Keep the model under fifty lines, verify the answer against a known case, and time two labeling strategies. That single exercise teaches you more about whether CLP(FD) fits your work than any amount of reading, and it usually takes less than an afternoon.