Constraint Logic Programming

Analogy categoryAnalogies

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.

prolog

:- 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=10652

Propagation, 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.