Solving Puzzles with CLP(FD) Constraints in SWI-Prolog: Domains, Posting, and Labeling

Arithmetic in plain Prolog breaks the moment you stop knowing values up front. X is Y + 2 fails with an instantiation error unless Y is already ground, which makes bidirectional puzzles — cryptarithmetic, scheduling, magic squares — painful to write. CLP(FD), the constraint logic programming library over finite domains, fixes this: you declare what values variables may take, state the relationships between them, and let the solver search. This guide walks through that workflow in SWI-Prolog and shows how to debug the two problems that bite beginners most: residual goals and slow labeling.

What you need before starting

You need SWI-Prolog installed (version 7.x or later is assumed throughout; the CLP(FD) library by Markus Triska has been bundled for many years). You should be comfortable with basic Prolog: writing predicates, running queries at the ?- prompt, and reading unification results. No other setup is required — CLP(FD) ships with the standard distribution.

Load the library at the top of your file or at the prompt:

:- use_module(library(clpfd)).

From this point on, commit to constraint operators. Mixing is/2 with constrained variables is the single most common beginner error: once a variable participates in CLP(FD) constraints, use #=, #\=, #<, #=<, #>, #>= instead of is, =:=, and friends. The constraint versions work in any direction; is/2 demands a ground right-hand side and will throw an instantiation error otherwise.

Step 1: Declare variables and their domains

A finite domain is the set of integer values a variable may take. Declare it with ins/2:

Vars = [A, B, C],
Vars ins 0..9

This says each of A, B, and C is an integer between 0 and 9. Domains can also be written as unions, e.g. X in 1..5 \/ 8. Keep domains as tight as your problem allows — domain size directly controls search cost later.

Step 2: Post constraints

Constraints are posted like ordinary goals, but they propagate: each one immediately removes impossible values from domains rather than waiting to be tested. A complete small example, the classic SEND + MORE = MONEY puzzle:

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

Three things to note. First, all_different(Vars) forces pairwise-unequal values — essential for alphametic puzzles. Second, leading-digit constraints (S #\= 0) are posted explicitly; the domain alone doesn't know about place value. Third, the arithmetic is written declaratively with #=; the solver, not you, figures out how to use it.

Run it at the SWI-Prolog top level (no special permissions needed):

?- send_more_money(S, E, N, D, M, O, R, Y).

You should get the single known solution, S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2, and no further answers on backtracking. If you get more than one answer, a constraint is missing; if none, one is wrong or over-restrictive.

Step 3: Label — turn constraints into concrete answers

label/1 enumerates values for the listed variables, one solution per backtrack. Without it, the top level shows residual goals instead of numbers:

?- X in 1..3, Y in 1..3, X #< Y.
X in 1..2,
X#<Y,
Y in 2..3.

This is not an error. It means the constraints are consistent and the solver has narrowed the domains, but no concrete values were chosen. Add label([X, Y]) to get ground answers:

?- X in 1..3, Y in 1..3, X #< Y, label([X, Y]).
X = 1, Y = 2 ;
X = 1, Y = 3 ;
X = 2, Y = 3.

When you see residual goals at the top level unexpectedly, the fix is almost always to label the remaining variables.

Step 4: Control the search when performance matters

Plain label/1 tries variables left-to-right and values smallest-first. For harder problems this can be catastrophically slow. labeling/2 accepts strategies; the most useful is ff (first-fail), which labels the variable with the smallest current domain first:

labeling([ff], Vars)

Because propagation shrinks domains as constraints are posted, first-fail tends to hit dead ends early instead of deep in the search tree. On scheduling-style problems with dozens of variables, the difference between default and ff ordering is often the difference between seconds and effectively never finishing. Other useful options include min(Expr)/max(Expr) for optimization, e.g. labeling([min(Cost)], Vars) to find a lowest-cost solution.

Two cautions. First, unbounded or huge domains make naive labeling non-terminating in practice — if a variable could be any integer, constrain it before labeling. Second, all_different/1 propagates weakly (it only reacts when a variable becomes ground); all_distinct/1 prunes much more aggressively but costs more per step. For small puzzles either works; for larger all-different subproblems, try all_distinct/1 and measure.

Checking your work and recovering from failures

Three quick diagnostics cover most problems:

• Unexpected failure. If a query fails instantly, your constraints are jointly infeasible. Binary-search the bug: comment out half the constraints, re-run, and narrow to the conflicting pair. Infeasibility detected before labeling is a feature — it means propagation worked.
• Unexpected residual goals. You forgot to label, or you labeled a different variable list than the one you constrained. Label exactly the variables you want ground.
• Instantiation errors. Somewhere an is/2 or =:=/2 is touching a constrained variable. Replace it with the #-operator equivalent.

For deeper inspection, trace/0 at the prompt lets you step through constraint posting, though output is verbose on large problems. A lighter check is to query domains mid-program, e.g. add a goal like fd_dom(X, D), writeln(D) during development to confirm propagation is narrowing values as expected (remove it in final code).

Since constraint posting is pure and stateless within a query — everything is undone on backtracking — there is nothing to roll back. The only recovery you need is editing constraints and re-running.

Portability note

SICStus Prolog, GNU Prolog, and YAP all provide CLP(FD) libraries with similar syntax, but operator details, labeling options, and propagation strength differ between systems. Code written for SWI-Prolog's library usually ports with small changes, but verify labeling strategy names and any library-specific predicates before assuming identical behavior.