CLP(FD): Prolog's Most Persuasive Declarative Feature

Solving a puzzle like SEND+MORE=MONEY by hand in Prolog usually starts as generate-and-test: enumerate digit permutations, then check the arithmetic. It works, but the program mixes what a valid answer is with how to search for it. CLP(FD) — Constraint Logic Programming over Finite Domains — flips that around. You declare domains, exclusions, and equations; the engine prunes impossible values before they are ever chosen and supplies the search itself.

Write the spec, get the solver

A CLP(FD) program builds a constraint store: each variable has a finite integer domain, and posting a constraint immediately narrows those domains (propagation). When propagation alone cannot fix values, labeling/2 enumerates the remaining choices using Prolog's ordinary backtracking. The key predicates in SWI-Prolog's library(clpfd) are ins/2 for domains, arithmetic constraints like #= and #<, the global constraint all_distinct/1, and labeling/2 for search. The same program also works as a checker: call it with digits bound and it succeeds or fails on a claimed answer.

Worked example: SEND+MORE=MONEY

The following targets SWI-Prolog (tested on a recent 9.x release; other systems use different names — see the portability note below).

:- use_module(library(clpfd)).

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

Run it at the top level with ?- send_more_money(Vars).. The query should yield exactly one solution, the classic S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2 — but verify this on your install rather than trusting the listing. Forgetting all_distinct/1 or the nonzero constraints on S and M produces spurious or multiple solutions.

Labeling strategy is a real engineering decision

Propagation is incomplete: after posting constraints, many domains stay wide, so labeling/2 does genuine search, and its options matter. [ff] (first-fail) picks the variable with the smallest domain first; step vs enum and variable-ordering heuristics can change runtime dramatically on larger models, and worst-case exponential behavior remains. CLP(FD) is also not part of ISO Prolog — predicate names differ across systems: SWI's all_distinct/1 is fd_all_different/1 in GNU Prolog. Check your system's documentation before publishing code.

Try it on your next rule

Before writing a hand-rolled search for scheduling, rostering, packing, or validation, prototype the rules as constraints. Small CLP(FD) models often replace dozens of lines of imperative branching, and rule changes become edits to the spec rather than the search.