From Generate-and-Test to Constraint Propagation
Plain Prolog solves combinatorial problems by generating candidate values and testing them against constraints one at a time, which wastes enormous effort exploring branches that were doomed from the start. Constraint logic programming extends Prolog with constraint domains — most commonly CLP(FD) for finite domains of integers, alongside CLP(Q) and CLP(R) for rationals and reals — where constraints are declared up front and propagated immediately to prune impossible values from variables' domains, often before any search happens at all, so the eventual search explores a dramatically smaller space.
Cricket analogy: It's like a team-selection process that first rules out every player who's injured or suspended before even considering batting order combinations, rather than drafting a full XI and then discovering afterward that three players were ineligible — CLP(FD) prunes invalid values before search, not after.
Domains and Arithmetic Constraints in CLP(FD)
In SWI-Prolog's library(clpfd), a variable's domain is declared with X in 1..10 (or a set like X in {1,3,5}), and relations between variables are expressed with reified arithmetic operators like #=, #\=, #<, #>=, and all_different/1, all of which are constraints rather than one-shot tests — they stay attached to the variables and re-trigger propagation every time any linked variable's domain shrinks, so writing X #= Y + 1 lets Prolog narrow Y's domain the instant X's domain narrows, and vice versa, in either direction.
Cricket analogy: It's like a required-run-rate constraint that updates live as both the target score and overs remaining change — declaring X #= Y + 1 keeps the relationship between two variables permanently enforced, the way a required run rate recalculates automatically whenever either runs scored or overs bowled changes, in either direction.
:- use_module(library(clpfd)).
send_more_money(Letters) :-
Letters = [S,E,N,D,M,O,R,Y],
Letters ins 0..9,
S #\= 0, M #\= 0,
all_different(Letters),
1000*S + 100*E + 10*N + D
+ 1000*M + 100*O + 10*R + E
#= 10000*M + 1000*O + 100*N + 10*E + Y,
label(Letters).
?- send_more_money(L).
L = [9, 5, 6, 7, 1, 0, 8, 2].
% SEND=9567, MORE=1085, MONEY=10652Propagation, Labeling, and Search
Declaring constraints alone narrows each variable's domain through propagation but doesn't commit to specific values; label/1 (or labeling/2 with a strategy like ff for first-fail, which picks the most constrained variable first) performs the actual backtracking search, trying concrete values for each variable within its already-narrowed domain and re-triggering propagation after every assignment, so failures are detected — and backtracked from — as early as possible rather than only at the very end of a full candidate assignment.
Cricket analogy: It's like a bowling coach narrowing a bowler's line-and-length options through analysis (propagation) before the bowler actually commits to a specific delivery (labeling) — and picking the most constrained decision first, like choosing the field placement before the run-up, catches a bad plan early rather than after the ball is bowled.
Reified constraints like #= and #\= are declarative and direction-agnostic: X #= Y + 1 can be used to compute Y from a known X, X from a known Y, or simply to record the relationship for propagation before either variable is known, unlike Prolog's plain is/2 which requires its right-hand side to already be fully evaluable.
A Worked Example: SEND + MORE = MONEY
The classic verbal arithmetic puzzle SEND + MORE = MONEY, where each letter stands for a distinct digit and leading letters can't be zero, is a canonical CLP(FD) demonstration: you declare Letters = [S,E,N,D,M,O,R,Y], constrain each to 0..9, forbid S and M from being 0, enforce all_different(Letters), state the arithmetic relation as a single #= equation over place-value sums, and finally call label(Letters) — the propagation from all_different/1 alone eliminates most of the 10! naive possibilities before any labeling occurs, which is why this runs in milliseconds despite looking like a brute-force search problem.
Cricket analogy: It's like solving a fantasy-league puzzle where each of eight players must be assigned a distinct shirt number from 1-9 satisfying several numeric constraints simultaneously — the all_different/1 rule alone eliminates most invalid number assignments before you ever have to actually try combinations, the way a well-run auction avoids duplicate bids up front.
- CLP(FD) extends Prolog with finite-domain integer constraints that propagate immediately rather than being tested after full instantiation.
- X in 1..10 declares a variable's domain; all_different/1, #=, #\=, #<, and #>= declare relations that stay attached and re-propagate.
- Constraints are direction-agnostic: X #= Y + 1 narrows Y from X's domain and X from Y's domain, unlike plain is/2.
- label/1 (or labeling/2 with a strategy) performs the actual search, trying concrete values within already-narrowed domains.
- First-fail labeling strategies pick the most constrained variable first, detecting failures as early as possible.
- SEND + MORE = MONEY is a canonical demonstration where all_different/1 propagation prunes nearly the entire naive search space before labeling.
- CLP(Q) and CLP(R) provide analogous constraint solving over rationals and reals for problems outside the integer domain.
Practice what you learned
1. What is the main advantage of declaring constraints with library(clpfd) instead of generating candidates and testing them afterward?
2. What does X in 1..10 do in a CLP(FD) program?
3. Why is X #= Y + 1 different from the plain Prolog goal X is Y + 1?
4. What does label/1 do that declaring constraints alone does not?
5. In the SEND + MORE = MONEY puzzle, what makes the CLP(FD) solution run in milliseconds despite looking like a brute-force problem?
Was this page helpful?
You May Also Like
findall, bagof, and setof
The three built-in all-solutions predicates that collect every proof of a goal into a list, each with different rules for failure, grouping, and duplicates.
Higher-Order Predicates in Prolog
How Prolog treats goals as ordinary data, enabling call/N, maplist, foldl, include, exclude, and partition to parameterize control flow.
DCGs (Definite Clause Grammars)
How Prolog's --> notation compiles grammar rules into difference-list predicates, enabling parsing, generation, and embedded computation in one syntax.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics