Stop Writing Generate-and-Test Loops: CLP(FD) in SWI-Prolog

Say you need to solve a small combinatorial puzzle in Prolog — assign digits to letters so that SEND + MORE = MONEY, or fill a Sudoku grid. The classic beginner approach is generate-and-test: permute candidate values, then check the constraints. It works, but the search is blind. Prolog happily enumerates thousands of assignments that violate a constraint it could have spotted after fixing just two variables.

The useful takeaway: SWI-Prolog's library(clpfd) lets you state constraints over integer variables up front, and the solver prunes impossible values before search begins. Your program becomes a readable description of the problem, plus one line that triggers the search.

What CLP(FD) actually gives you

CLP(FD) stands for Constraint Logic Programming over Finite Domains — integer variables with bounded ranges. You load it in SWI-Prolog with:

:- use_module(library(clpfd)).

Instead of computing with is/2, which needs fully instantiated arguments and throws errors otherwise, you post constraints like X #= Y + 1 or X in 1..9. These constraints are active: as soon as one variable's domain shrinks, the solver narrows the others. This is the crucial difference from plain arithmetic — propagation happens while variables are still partially unknown.

The library also provides global constraints such as all_distinct/1, which enforces uniqueness across a list far more efficiently than posting every pairwise #\=.

A worked example: SEND + MORE = MONEY

Here is the full model. Run it in the SWI-Prolog top level (swipl) after loading the library; no special permissions needed.

send_more_money(Vs) :-
    Vs = [S,E,N,D,M,O,R,Y],
    Vs ins 0..9,
    all_distinct(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).

Query it with ?- send_more_money(Vs). and you should get the classic solution Vs = [9,5,6,7,1,0,8,2]. Notice the structure: everything except the last line is the model — a declarative statement of the problem. Only labeling/1 performs search.

The real engineering decision: model vs. search

That separation is the practical lesson. The constraint-posting part is deterministic and can be read, reviewed, and unit-tested independently. The search part is a knob you can tune without touching the model.

The knob matters. labeling([ff], Vs) uses first-fail ordering: branch on the variable with the smallest remaining domain first. On structured problems this often cuts the search tree dramatically. Pick a poor strategy and a solvable instance can appear to hang. Other options, like bisect, change how values within a domain are tried. It's worth benchmarking two or three strategies on real instances before shipping.

Trade-offs and limitations

• Integers only. Floats and rationals need CLP(Q)/CLP(R) or another tool entirely.
• Propagation is incomplete. Posting constraints alone may not detect unsatisfiability; you still need labeling/1 to get concrete answers.
• Portability. Syntax and labeling options differ slightly between SWI, SICStus, and GNU Prolog. Check the docs for your installed version.
• No magic. Huge domains or weakly constrained models still explode exponentially. CLP(FD) rewards modelling skill, it doesn't replace it.

Try it yourself

Take a puzzle you've solved with generate-and-test — Sudoku is a good next step — and rewrite it as a CLP(FD) model. Verify the declarative version returns identical answers, then run it with and without ff and compare time/1 results. That single experiment will teach you more about constraint propagation than any tutorial.