Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 40 ยท Constraint Logic Programming

Constraint Logic Programming with CLP(FD)

Learn constraint logic programming over finite domains in Prolog. Use library(clpfd) with #=, in, ins and label/1, understand propagation, reversible arithmetic and reification.

In the arithmetic lesson you met the main weakness of is/2: it only runs one way, and every variable on its right must already have a value. Constraint logic programming removes that limit. Instead of computing answers, you state relations between integer variables, and the system narrows each variable's set of possible values until the answer is known. The library for integers is CLP(FD), "constraint logic programming over finite domains", and in SWI-Prolog it replaces is/2 and the arithmetic comparisons in nearly all new code that deals with integers.

PROLOG
:- use_module(library(clpfd)).

Prolog is not available on this site, so the runnable examples use a small Python stand-in solver that works like CLP(FD) for tiny problems: variables with domains, constraints, propagation and labeling.

Constraints instead of calculations

The CLP(FD) arithmetic operators all start with #:

Constraint Meaning
X #= Y equal (both sides may be expressions)
X #\= Y not equal
X #< Y, X #> Y less, greater
X #=< Y, X #>= Y less or equal, greater or equal
X in L..H X is an integer from L to H
Xs ins L..H every variable in the list Xs is in L..H
label(Xs) enumerate concrete values for the variables

The first big difference: #= works in every direction.

PROLOG
?- X #= 3 + 4.
X = 7.

?- 7 #= X + 4.
X = 3.

?- X in 0..9, Y in 0..9, X + Y #= 18.
X = 9,
Y = 9.

The third query is not a lookup; the solver reasoned: both variables are at most 9, their sum is 18, so both must be exactly 9. This reasoning is called propagation: each constraint removes values from the domains that cannot be part of any solution.

Domains and residual goals

When a constraint cannot fix a variable, the answer shows the narrowed domain instead:

PROLOG
?- X #> 3, X #< 6.
X in 4..5.

?- X in 1..5, X #\= 3.
X in 1..2\/4..5.

?- X in 1..10, X #> 7, fd_dom(X, D).
X in 8..10,
D = 8..10.

\/ means "or" (union of ranges). A variable without a declared domain ranges over inf..sup, the whole integers. Reading these answers is a skill in itself: they are residual constraints, the part of the problem that is still open.

The stand-in below does the same narrowing in Python. Each post call adds a constraint, propagate prunes domains, and show prints them in the toplevel's notation.

Python Propagation narrows domains (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Labeling: from domains to values

Propagation alone often leaves choices. label/1 (or the more flexible labeling/2, covered in the next lesson) tries each value in turn, propagating after every choice, and backtracks as usual:

PROLOG
?- X in 1..10, X #> 7, label([X]).
X = 8 ;
X = 9 ;
X = 10.

?- length(L, 3), L ins 1..3, all_different(L), label(L).
L = [1, 2, 3] ;
L = [1, 3, 2] ;
L = [2, 1, 3] ;
L = [2, 3, 1] ;
L = [3, 1, 2] ;
L = [3, 2, 1].

The recipe for almost every CLP(FD) program is the same:

  1. Declare the variables and their domains.
  2. Post all constraints.
  3. Label the variables.

This is the "constrain and generate" style. It contrasts with "generate and test", where you pick values first and check afterwards. Constrain and generate can be exponentially faster, since the constraints prune the search before the labeling begins.

The CLP(FD) recipe

  1. Domains
X in 1..9, Xs ins 0..9
  1. Constraints
#=, #=, #<, all_different
  1. Labeling
label(Xs) picks the values

Constrain first, search last.

1 / 2

Arithmetic that runs backwards

With #=, a recursive predicate often becomes reversible. This is the standard example:

PROLOG
n_factorial(0, 1).
n_factorial(N, F) :-
    N #> 0,
    N1 #= N - 1,
    F #= N * F1,
    n_factorial(N1, F1).
PROLOG
?- n_factorial(5, F).
F = 120.

?- n_factorial(N, 120).
N = 5 ;
false.

The second query asks "which N has a factorial of 120?", and the program terminates with the answer. With is/2, this direction is impossible. The key is that N #> 0 and the other constraints make the recursion stop as soon as the numbers become inconsistent.

The next stand-in shows the same idea in a smaller form. A relation like X * Y = 12 is posted once, and it can then be read in several directions: find all factor pairs, or fix one number and find the other.

Python One relation, many directions (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reification: constraints as truth values

A constraint can itself be turned into a 0/1 value with #<==> (equivalence), #==> (implication), #\/ (or), #/\ (and) and #\ (not). This is reification and it lets you count and branch on conditions.

PROLOG
?- X in 0..10, B #<==> (X #> 5), X = 7.
X = 7,
B = 1.

Adding up reified constraints counts how many conditions hold, a technique used constantly in scheduling and counting puzzles, for example "exactly two of these five people are late".

PROLOG
count_big(Xs, Count) :-
    Xs ins 0..9,
    maplist([X, B]>>(B #<==> (X #> 5)), Xs, Bs),
    sum(Bs, #=, Count).

Practical advice

  • Always post constraints before labeling. If you label first, you throw away the pruning power.
  • Use #= and friends for integer work throughout a program; mixing is/2 into the same variables defeats the purpose.
  • Give every variable a finite domain before you label. label/1 on a variable with an infinite domain raises an instantiation error.
  • Read answers carefully: X in 4..5 is a legitimate answer, not an error.
  • CLP(FD) integers are unbounded, so there is no overflow, but large domains slow the search. Keep ranges as small as the problem allows.
  • For real arithmetic on floats use ordinary is/2; CLP(FD) is for integers (see CLP(R) and CLP(Q) for reals and rationals).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does ?- 7 #= X + 4. answer?

    CLP(FD) arithmetic is relational, so the constraint can solve for the unknown on the right.
  2. 2. What is the answer to X in 1..5, X #\= 3.?

    Propagation removes 3 from the domain, leaving two ranges joined by the union operator.
  3. 3. What is the usual order of steps in a CLP(FD) program?

    Constrain first so that propagation prunes the search space; label last.
  4. 4. What does B #<==> (X #> 5) do?

    Reification turns the truth of a constraint into a 0/1 variable that can be counted or constrained.

Summary

  • CLP(FD) adds integer constraints: #=, #\=, #<, #>, #=<, #>=, in, ins.
  • Constraints propagate: they remove impossible values from variables' domains, and answers may be domains like X in 4..5.
  • label/1 enumerates concrete values; the standard shape is declare, constrain, label.
  • #= runs in any direction, so predicates become reversible.
  • Reified constraints (#<==>, #==>) give constraints a 0/1 truth value for counting and branching.

Next: Puzzles and Labeling Strategies