1. About This Tutorial
1.1. Who Should Do This Tutorial
This tutorial is for reasonably experienced SWIProlog programmers who want to use clp(fd).
Additionally, this tutorial will be useful for Prolog programmers using other versions of Prolog who want to use clp(fd).
The emphasis of this tutorial is not on the theory. The author is not a mathematician and the tutorial will probably not be of much use to competent mathematicians who can approach the material via the academic literature.
This tutorial should give you a grasp of the fundamentals of constraint systems on finite domains.
A certain minimal amount of practical wisdom is covered.
But mostly this tutorial is a translation of the SWIProlog documentation of the clp(fd) predicates from the rather terse, math laden documentation to a more approachable level of English.
1.2. What Is clp(fd) good for?
clp(fd) is a library included in the standard SWIProlog distribution. It solves problems that involve sets of variables, where relationships among the variables need satisfied.
clp(fd) is also useful for replacing many of the guard functions provided by getters and setters in OO languages. For example, if we don’t know a person’s actual height yet, we can still assert that it’s more than 21 and less than 108 inches (shortest/tallest people known). When we eventually do find a solution, unreasonable values will be rejected.
clp(fd) is useful for optimizing search problems by reducing search spaces. Constraints can trim away entire subtrees of the search space.
clp(fd) is useful for solving a wide variety of find values for these variables problems. Here are some broad categories of problems that clp(fd) can address:

Scheduling problems, like, when should we do what work in this factory to make these products?

Optimization problems, like which mix of products should we make in this factory to maximize profits?

Satisficing problems, like finding an arrangement of rooms in a hospital that meets criteria like having the operating theater near the recovery rooms, or finding a set of vacation plans the whole family can agree on.

Sequence problems, like finding a travel itinerary that gets us to our destination.

Labeling problems, like Sudoku or Cryptarithm puzzles

Problems of belief and intention, like detective puzzles and NPC’s in games

Allocation problems, like finding an assignment of flight crews to aircraft that meets union requirements for maximum time away from home

finding acceptable solutions to linked sets of variables, for example, working out who’se going to the party among a group of jealous teenage girls when A will only go if B goes, but B won’t go if C goes, and so on

Creating lists of acceptable alternatives for multiple interacting variables. For example, a caterer might want to see different offerings for a banquet menu that meet some criteria of cost, scheduling of cooks and waiters, ovens, and so on, then decide for themeselves which to select.

Geometric constraints for graphics, eg. a CAD system, where two lines must be perpendicular, another two parallel, others 30 inches apart, and so on.
1.3. Prerequisites
Competence in the basics of SWIProlog.
A level of mathematical sophistication comparable to that of an upper level standing in a computer science undergrad program.
A working SWIProlog installation.
There is no set of additional code for this tutorial. You can cut and paste many of the examples.
1.4. What You Can Expect From This Tutorial
If you read through this tutorial and work all the exercises you can expect to:

understand the basic concept of constraint programming

be able to write programs that find solutions to unknown values

be able to formulate real world problems using the clp(fd) library predicates

be able to select appropriate solutions to constraint system problems.

understand how to use clp(fd) in real world SWIProlog programs.
1.5. Time to Complete
Unknown as yet. When the first few people complete this tutorial I’ll ask them.
2. The CLP(FD) Library
The clp(fd) library for SWIProlog was written by Markus Triska for his PhD thesis. clp(fd) stands for Constraint Logic Programming over Finite Domains.
clp(fd) is one of several constraint solvers available in SWIProlog. The others are clp(b), clp(qr) and CHR. clp(b) handles booleans. clp(qr) handles rationals and reals. CHR approaches constraint programming differently, using rewrite rules.
The clp(fd) library can be activated by simply
: use_module(library(clpfd)).
This installs a compiletime hook that optimizes some clp(fd) constraints, and loads a runtime library.
3. Variables
We use the term variable rather loosely in computer science.
3.1. Replacement Variables
In imperative languages like Java variables are mutable. Their values change over time.
In C, a variable like x
int x;
... what about here? ...
x = 5;
always has a value. Before we assign 5 to it, the value is whatever happened to be in that memory location (a source of delight for security programmers everywhere).
3.2. Logic Variables
Variables in a logic language are different. They are much more like variables or unknowns in high school algebra.
In Prolog a variable can be bound or unbound. An unbound variable will unify with any value. A bound variable unifies only with one template.
In effect, we either know, or don’t know, the value of the variable.
When we try to unify, we are, effectively, asking, "is what we know about the answer on the left compatible with what we know about the answer on the right?" Bob claims to be good friends with the Mayor of Maintown. If Bob’s the editor of the Maintown Daily, that’s entirely believable. If Bob also claims to have never set foot in Maintown, it’s inconsistent.
In Prolog we have only two possibilities, for an atomic result. Know absolutely nothing, or know exactly. Obviously we might have unbound variables within a list or term, but for each variable there are only these two states.
3.3. Constrained Variables
But in the real world we can say more about a variable.
We might not know the exact value, but we know it is one of a set of possible values.
We might know it’s value is, say, greater than the value of some other variable, whose value we also don’t know. We say the variable is constrained.
As we begin to accumulate constraints, we start to be able to reason about the constraints. Suppose we have two variables, X and Y, which are integers.
Now I tell you that X is in the range 0 to 10.
Further I tell you that Y is in range 4 to 8.
And finally that X is more than Y.
You can infer that X is within the narrower range 5 to 10, since the lowest value Y can have is 4, and X must be one more than Y.
Here’s how it looks in clp(fd). Don’t worry if you don’t understand all of this yet
: use_module(library(clpfd)).
test(X, Y) :
X in 0..10,
Y in 4..8,
X #> Y.
14 ? test(X, Y).
X in 5..10,
Y#=<X+ 1,
Y in 4..8.
include the clp(fd) library  
constrain X to be in 0 through 10 using the in operator  
constrain Y to be in 4 through 8 using the in operator  
constrain X to be greater than Y using the #> operator  
X is now constrained to 5 through 10  
Y is now constrained to be =< X  1 (same as X > Y), and in the range 4 through 8. 
When we have constrained a variable to a single value, something rather magical happens  we now know the value of the variable, so we can bind the variable. And in clp(fd) this is indeed what happens! Suppose I constrain X to the range 0 to 5, and Y to 4 to 8, and X > Y, then suddenly X is now in bound to 5. ground(X) succeeds, and X is a perfectly ordinary bound variable.
: use_module(library(clpfd)).
test2(X, Y) :
X in 0..5,
Y in 4..8,
X #> Y.
16 ? test2(X,Y).
X = 5,
Y = 4.
X is bound just like normal Prolog  
Notice that Y is bound too. Further, it’s lost it’s original constraints 
3.4. Implementation
SWIProlog has the ability to add attributes to variables. This is additional metadata attached to the variable. If you’re interested, you can read more about attributed variables at The SWIProlog website.
clp(fd) uses this attribute data to decorate the variables with constraints. Then clp(fd) implements constraint programming as an expansion of the normal Prolog unification.
3.5. Domains
The (fd) in clp(fd) stands for finite domain. This domain could have millions of values, but it must be a finite list.
We’re only concerned with variables with a finite domain, the finite domain of the name. For our purposes that means we want to reason about domains that are sets of integers.
You do need to give variables a domain before you try to label them! If not, you’ll get a baffling ERROR: Arguments are not sufficiently instantiated
exception.
Any finite list of possibilites can be mapped into a finite subset of the integers.
At first this can seem awkward, but it’s really no different than using array indices. A bigger issue can be debugging  lists of integers can be pretty meaningless. Writing some debug code to extract the data and print it can help.
4. An Example
I’m always annoyed by discussions that blather on, ungrounded in reality. So here’s a classic constraint program, with brief descriptions of the parts. You may not understand all the parts yet.
The SEND + MORE = MONEY cryptoarithmetic puzzle is a classic "hello world" for constraint programming. The puzzle is to assign the digits 0 thru 9 to letters such that they spell out SEND MORE MONEY and when read as base 10 numbers create a true mathematical formula. Leading zeros are not permitted on numbers.
: use_module(library(clpfd)).
puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :
Vars = [S,E,N,D,M,O,R,Y],
Vars ins 0..9,
all_different(Vars),
S*1000 + E*100 + N*10 + D +
M*1000 + O*100 + R*10 + E #=
M*10000 + O*1000 + N*100 + E*10 + Y,
M #\= 0, S #\= 0,
label(Vars).
9 ? puzzle(X).
X = ([9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2]) ;
false.
include the clp(fd) library  
note the clp(fd) is not an embedded DSL like pce or quasiquotes. clp(fd) rides along with Prolog, adding semantics.  
for convenience make a list of all the variables we’ll constrain  
restrict each variable in Vars to the range 0..9 inclusive  
add the constraint that they must all be different  
add the arithmetic constraint that defines the puzzle  
M and S start words, and hence cannot be zero  
attempt to ground as many variables as possible.  
notice that there’s no funny attribution outside, it just returns the solution 
5. Labeling
Attaching constraints is nice, but ultimately of little use until we can get back to simply grounding the variables. A solution with all the variables ground is called a ground solution.
There are a few minor mechanisms for doing so. If you reduce the domain to a single value, the variable will be ground.
Obviously you can simply ground the variable normally X = 3
And the predicate indomain/1
successively binds a single variable to it’s possible values on backtracking.
But usually we call label/1
or labeling/2
to find a single ground solution. label/1
and labeling/2
are nondeterministic, binding a different set of values on each backtracking.
Of course our constraint system may not be powerful enough to express every constraint. If so, we must fall back on the generate and test search strategy familiar to all Prolog programmers. With constraint systems, generate and test becomes

constrain

generate (by labeling)

test
and indeed most clp(fd) programs follow a general pattern of constrain followed by label.
It’s a good practice to set up the model and do the labeling and any remaining searching in separate predicates. This makes it easier to inspect the model before labeling is applied. 
labeling/2
has a wealth of options that affect the variable selection strategy. Since most of the time taken by a clp(fd) program is usually in the labeling, we’ll cover these in detail later. For now we’ll use label/1
, which has reasonable defaults.
The options in labeling/2
are also used with optimization problems of the make the most profit type.
6. Simple Constraints
clp(fd) provides a basic set of primitive constraints.
Remember that clp(fd) works with integers.
X #>= Y
X #=< Y
X #= Y
X #\= Y
X #> Y
X #< Y
You can use #= as a declarative version of is , in what is otherwise not a clp(fd) program. X is 3+Y requires Y to be ground, while X #= 3+Y works if X is ground and Y is not. 
X #< Y is useful to get rid of uninteresting symmetries. For example, if players 1 and 3 are matched in a tournament then there’s no point considering the match 3 and 1. Consider this example taken from the SWIProlog documentation that finds all the ways to pair up 4 people: 
? Vs = [A,B,C,D], Vs ins 1..4,
all_different(Vs),
A #< B, C #< D, A #< C,
findall(pair(A,B)pair(C,D), label(Vs), Ms).
Ms = [ pair(1, 2)pair(3, 4),
pair(1, 3)pair(2, 4),
pair(1, 4)pair(2, 3)].
7. Constraining to a Domain
Clp(fd) is concerned with the domains of variables.
The domain of a variable is simply the set of values it can take on.
In clp(fd) every variable must be restricted to a "finite domain" in order to reason about it.
X in 5..10,
Y in 1..10,
Y #> X
Set a domain for X  in this case 5 through 10  
Set a domain for Y  1 through 10  
Now constraint Y to be more than X. So we can reason about Y’s domain. Y must be one of the values 6,7,8,9, or 10. 
7.1. In and Ins
You can restrict the domains of variables with the in
and ins
operators.
Both in
and ins
take a domain on the right side.
A domain is a simple range or a union of simple ranges with the
\/ operator
A simple domain can be a single integer or a pair of bounds connected with double dots. The bounds can be integers, or inf
for the least member or sup
for the greatest member. Any of these can be a ground variable, like N=3, X in 1..N
.
7.2. The \/
operator
Domains can be unioned together with the \/
operator
1..3 \/ 5..7
Here’s an example of a more complex domain.
V in inf.. 2 \/ 0 \/ 2..16 \/ 18..sup
in
constrains a single variable.
ins
constrains a list of variables to the same values, the equivilent of maplist over the list with in.
7.3. Domain From Data
What if your domain data comes from input data? Assemble your domain as a term and use X in MyDomain. Here’s an example
% Bases is a list of ints. Constrain Var to be within B..B+2 for B
% a member of Bases
two_domains(Bases, Var) :
make_two_domains(Bases, Term),
Var in Term.
make_two_domains([H], H..HT) :
HT is H + 2.
make_two_domains([H  T], '\\/'(H .. HT, TDomain)) :
HT is H + 2,
make_two_domains(T, TDomain).
25 ? two_domains([1, 8, 16], V).
V in 1..3\/8..10\/16..18 ;
8. Arithmetic Operators
You can do a lot of constraint work with the arithmetic constraints.
Constraints can take infix arithmetic expressions.
X + 2 #= Y * 3
The available operators are

unary ,

+,

,

*,

/ (truncated integer division),

^ (exponentiation),

min,

max,

mod,

rem,

abs
9. Logical Operators
9.1. #\
Negation
#\
Unary. Inverts the contained constraint.
9.2. #/\
And
#/\
Constrains both sides to hold. Useful on left side of a
operator (below).#==>
9.3. #\/
Or
#\/
Constrains at least one side to hold. Useful on left side of a
operator (below).#==>
10. Reification
Reification is the process of using constraints to control other constraints. clp(fd) includes two operators for reification.
10.1. #<==>
Equivalency
#<==>
Each side may be a boolean variable (a 0 or 1) or a constraint. The constraints are modified so they both hold, or their negations both hold.
10.2. #==>
Implication
#==>
If the left side holds, then the right side must hold. If the left side does not hold, then the right side is ignored.
In a chemical plant there is a reaction vessel. The temperature in the vessel is constrained to be less than a certain value, and to be more than another value, except when in startup mode.
chem_tank(Temp, Startup) :
Temp #< 800,
#\+ Startup #==> Temp #> 300.
We can define startup mode as lasting for 10 minutes after some StartTime.
chem_demo(Temp, TimeNow, StartTime) :
chem_tank(Temp, TimeNow  StartTime #< 10).
11. Commonly Useful Constraints
We now turn to looking at the more convenience predicates provided in the clp(fd) library. Most establish a large number of simple constraints at the same time.
As well as introducing the convenience predicates, it’s also a good way to develop a facility with using constraints.
Here are a few constraints that are useful in a wide variety of constraint situations.
11.1. length(List, Length)
This of course is good ol' length. It’s useful in the length(, +) mode to generate a list of unbound variables.
length_(Length, List) : length(List, Length). is sometimes handy to make lists of unbound variables in call + 1 situations.
length(List, 9), maplist(length_(9), List) gives a 2D array of
unbound variables, for example. 
11.2. all_different(List)
This predicate is used frequently. It constrains the members of List to different values.
? length(List, 4),List ins 1..4, all_different(List), List = [1,_,3,4].
List = [1, 2, 3, 4].
all_different/1
is useful in conjunction with the pigeonhole principle, which says that if you have N variables each an element of 1..M , and N > M, then there must be two variables with the same value. In the above example, List must always be a permutation of [1, 2, 3, 4] for this reason.
All_distinct works like all_different, but tries harder to detect when all are different.
For example,
24 ? X in 1..2, Y in 1..2, Z in 1..2, all_different([X,Y,Z]).
X in 1..2,
all_different([X, Y, Z]),
Y in 1..2,
Z in 1..2.
25 ? X in 1..2, Y in 1..2, Z in 1..2, all_distinct([X,Y,Z]).
false.
26 ?
In the above, all_different fails to detect that there are only two possible values for X, Y, and Z, so two of them must be the same.
all_distinct does more work to analyze the domains of it’s variables, and does detect this condition. The cpu cost of using all_distinct is higher, however  so this needs balanced against performance gains from pruning the search tree earlier.
If you are having performance issues it might be worth investigating using one or the other.
11.3. tuples_in(+ListOfVariableTuples, +ListOfAcceptedTuples)
It’s fairly common to have a list of acceptable combinations of a few variables. A common situation would be ordering American style meals, where you order a full meal, whose price includes an entree and two sides, but you only get one side if you get the pie, etc. You have to enumerate all the various combinations.
The SWIProlog documentation contains this cool demo of selecting trains for a journey.
: use_module(library(clpfd)).
trains([[1,2,0,1], % from station, to station, departs at, arrives at
[2,3,4,5],
[2,3,0,1],
[3,4,5,6],
[3,4,2,3],
[3,4,8,9]]).
threepath(A, D, Ps) :
Ps = [[A,B,_T0,T1],[B,C,T2,T3],[C,D,T4,_T5]],
T2 #> T1,
T4 #> T3,
trains(Ts),
tuples_in(Ps, Ts).
? threepath(1, 4, Ps).
Ps = [[1, 2, 0, 1], [2, 3, 4, 5], [3, 4, 8, 9]].
Beyond the sheer coolness of this as a path finding method, notice that we didn’t have to do any labeling. There’s only one solution.
If you find yourself with tuples that look like [[1,2], [2,7], [3,8]…]
consider using element/3
instead.
11.4. Sudoku
OK, this isn’t really the Sudoku predicate, but transpose(+Matrix, ?Transpose)
is useful when
the variables are naturally expressed as a 2D grid.
Represent the grid as a list of lists. Each list is one row.
Many constraint predicates work on adjacency of elements in a list. If you need to operate on rows you can just use maplist. To operate on columns, transpose the matrix and they’re now rows.
No, you don’t need to transpose back. The new transposed matrix shares with the original. Any constraints on it are constraints on the original. 
Here, for example, is a program to solve the "quarreling children" problem. It’s made considerably simpler by only dealing with rows
/*
much shorter quarreling children
16 children are to be seated in a
4 x 4 array of chairs.
the children are 8 girls (numbered 1..8) and
8 boys (numbered 9..16).
1,3,5,8 think boys are ucky
9,10,11,14 think girls are gross
these pairs are enemies
[[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]
*/
length_(Length, List) : length(List, Length).
child_row(X) : X ins 1..16 .
ww(X) :
write(X),
write('/').
print_row(Row) :
maplist(ww, Row),
nl.
children(Class) :
length(Class, 4),
maplist(length_(4), Class),
maplist(child_row , Class),
maplist(row_compatible, Class),
transpose(Class, TransClass),
maplist(row_compatible, TransClass),
flatten(Class, FlatClass),
all_different(FlatClass),
maplist(label, Class),
maplist(print_row, Class).
row_compatible([A,B,C,D]) :
compatible(A, B),
compatible(B, C),
compatible(C, D).
compatible(A, B) :
not_enemy(A, B),
not_enemy(B, A),
sex_compatible(A, B),
sex_compatible(B, A).
not_enemy(A, B) :
NotA #\= A #\/ NotB #\= B,
tuples_in([[NotA, NotB]],
[[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]).
sex_compatible(A, B) :
A in 1\/3\/5\/8 #==> B #=< 8,
A in 9..11\/14 #==> B #> 8.
11.5. zcompare(?Order, ?A, ?B)
zcompare is useful when you need to know the relationship between the domains of two unlabeled variables.
10 ? X in 0..10, Y in 11..20,zcompare(C, X, Y).
C = (<),
X in 0..10,
Y in 11..20.
11 ? X in 0..11, Y in 11..20,zcompare(C, X, Y).
X in 0..11,
zcompare(C, X, Y),
freeze(C, clpfd:zcompare_(C, X, Y)),
Y in 11..20.
I’ll admit, that second one puzzled me a bit. C, it turns out, is still unbound, since we can’t really tell the relationship between X and Y when their domains overlap. But if C becomes bound later, then it will go back and constrain X and Y!
15 ? X in 0..11, Y in 11..20,zcompare(C, X, Y),C = <, writeln(C).
<
C = (<),
X in 0..11,
X#=<Y+ 1,
zcompare(<, X, Y),
Y in 11..20.
Annie is here, looking like this =8cO trying to imagine debugging code that uses lots of zcompares 
12. Resources
clp(fd) is great with resource constrained problems.
Scheduling problems are often a repeated series of resource constraint problems.
Most such problems can be worked with the primitive constraints, but a couple built in clp(fd) constraints are useful.
sum/3
and scalar_product/4
are fairly straightforward.
The use of scalar_product/4
might not be obvious. It’s useful for defining relationships where different things have different costs (in time, money, or something else).
%
% penny candy example
% Timmy has 25 cents
% gumballs cost a penny
% snickers cost 10 cents
% toffees are 2 cents
% licorice costs 5 cents
%
% what are Timmys alternatives?
% assume Timmy spends the entire 25 cents
scalar_test(Candy) :
Candy = [_Gumball, _Snickers, _Toffee, _Licorice],
Candy ins 0..sup,
scalar_product([1, 10, 2, 5], Candy, #=, 25),
label(Candy).
6 ? scalar_test([Gumball, Snickers, Toffee, Licorice]).
Gumball = Snickers, Snickers = Toffee, Toffee = 0,
Licorice = 5 ;
Gumball = Snickers, Snickers = 0,
Toffee = 5,
Licorice = 3 ;
Gumball = Snickers, Snickers = 0,
Toffee = 10,
Licorice = 1 ;
Gumball = Toffee, Toffee = 0,
Snickers = 1,
Licorice = 3 ;
Gumball = 0,
Snickers = Licorice, Licorice = 1,
Toffee = 5 ;
...
Try the penny candy example without the Candy ins 0..sup line.
What will happen? 
13. Sequences
We often need things to be in a specific sequence.
These constraints help establish sequences.
13.1. chain(+List, +Relation)
Chain establishes the Relation constraint between each pair of adjacent elements in List.
chain_example([A,B,C,D]) :
chain([A,B,C,D], #>=).
? chain_example(X).
X = [_G4676, _G4679, _G4682, _G4685],
_G4676#>=_G4679,
_G4679#>=_G4682,
_G4682#>=_G4685.
13.2. lex_chain(+Lists)
lex_chain/1
is more interesting. It takes a list of lists.
It constrains the inner lists to be lexicographically nondecreasing. This means they should be sorted by columns starting on the left. This is the normal way we sort text
andy
babble < below andy because a is less than b
beef < below babble because a is less than e
been < below beef because f is less than n
Besides the obvious use of sorting text, lex_chain has other sorting uses.
13.3. element(?Index, +List, ?Element)
Element is the constraint equivilent of nth1/3
.
It constrains an element of a list by it’s location in the list. Element must be the Indexth member of List, counting from 1.
%
% Suzy wants to flirt with Nathan
% But not when her old boyfriend John is around
%
% Suzy, Nathan, and John all must take classes 1..6
%
% How can Suzy arrange her schedule so she can flirt
% in at least 3 classes?
flirt_constraint(Suzy, Nathan, John, FlirtPeriods) :
length(Suzy, 6),
length(Nathan, 6),
length(John, 6),
Suzy ins 1..6,
Nathan ins 1..6,
John ins 1..6,
all_different(Suzy),
all_different(Nathan),
all_different(John),
FlirtPeriods = [A,B,C],
FlirtPeriods ins 1..6,
A #< B, % remove unwanted symmetry
B #< C,
flirty_period(A, Suzy, Nathan, John),
flirty_period(B, Suzy, Nathan, John),
flirty_period(C, Suzy, Nathan, John),
label(Suzy),
label(FlirtPeriods).
flirty_period(Period, Suzy, Nathan, John) :
Class in 1..6,
DiffClass #\= Class,
element(Period, Suzy, Class),
element(Period, Nathan, Class),
element(Period, John, DiffClass).
A very important use of element is in helping to constrain different facts.
For example, suppose we have a group of people, and we’ve numbered them by the alphabetic order of their names. Now we want to constrain a pair to be likely romantic partners. Being heterosexist and ageist, lets say we want to constrain them to be of opposite sexes and within 10 years difference in age.
This example also shows getting from index numbers to what we finally want  the names. It violates a rule of style for clp(fd)  set up your model in one predicate, label it in another  for pedagogic reasons.
: use_module(library(clpfd)).
names([amy,bill,charley,deanna,eric,frieda,george,harley]).
% women are 1, men are 0
genders([1,0,0,1,0,1,0,0]).
ages([22,19,73,65,40,38,25,27]).
% maps compatible names
romance(A, B) :
names(Names),
length(Names, NameLength),
AIndex in 1..NameLength,
BIndex in 1..NameLength,
genders(G),
element(AIndex, G, AG),
element(BIndex, G, BG),
AG #\= BG,
ages(Ages),
element(AIndex, Ages, AAge),
element(BIndex, Ages, BAge),
AAge #< BAge #==> AAge + 10 #>= BAge,
AAge #>= BAge #==> BAge + 10 #>= AAge,
AIndex #< BIndex, % remove unwanted symmetry and reflexiveness
label([AIndex, BIndex]),
nth1(AIndex, Names, A),
nth1(BIndex, Names, B).
7 ? romance(A,B).
A = amy,
B = bill ;
A = amy,
B = george ;
A = amy,
B = harley ;
A = charley,
B = deanna ;
A = eric,
B = frieda ;
false.
13.4. circuit(+List)
The documentation for this is more confusing than enlightening.
circuit/1
takes a list of variables and constrains them to form a circuit  a sequence where each number after the first is Vn+1 = Vn mod L + 1 . Where Vn is an element, Vn+1 is the next element, and L is the length of the list.
So this is clock arithmetic.
? length(Vs, _), circuit(Vs), label(Vs).
Vs = [] ;
Vs = [1] ;
Vs = [2, 1] ;
Vs = [2, 3, 1] ;
Vs = [3, 1, 2] ;
Vs = [2, 3, 4, 1] .
13.5. automaton
Automaton is the 900 lb gorilla of sequencing.
Automaton comes from automata theory , the study of abstract machines. automaton/3
constrains it’s first argument to be an element of a language that can be recognized by a finite acceptor. automaton/8
constrains it’s first argument to be an element of a language that can be recognized by a pushdown acceptor.
Do what? (Mathematicians avert your eyes, I’m going to explain finite automata while playing fast and loose).
A finite automaton is a bit like a hopscotch game. You have a (finite) set of states and directional arcs between them. Each arc is associated with an input. Here’s a typical automaton.
Start on the green state. Read the first element in the sequence, and if there’s an arc labeled with it, go to that state. If not, your sequence is not in the language. If there is, repeat in the new state  read the next element, and try to follow the arc. If you are in a blue state what you’ve read so far is part of the language.
Our language accepts one or more 0’s, followed by a 1, then a 2.
The green states are called source states, the blue ones sink states. A state could be both a sink and a source.
And here’s how to encode it in SWIProlog:
single_source_automaton(Vs) :
automaton(Vs, [source(a), sink(d)],
[arc(a,0,b),
arc(b,0,b),
arc(b,1,c),
arc(c,2,d)
]).
demo_single_source(Vs) :
length(Vs, 4),
single_source_automaton(Vs),
label(Vs).
Here’s a variation on our first automaton that accpets the same as the first automaton, but allows you to add 10 to all the numbers, so it accepts sequences like 10,10,10,10,11,12.
multi_source_automaton(Vs) :
automaton(Vs, [source(a),source(e), sink(d), sink(h)],
[arc(a,0,b),
arc(b,0,b),
arc(b,1,c),
arc(c,2,d),
arc(e,10,f),
arc(f,10,f),
arc(f,11,g),
arc(g,12,h)]).
demo_len(Vs) :
length(Vs, 4),
multi_source_automaton(Vs),
label(Vs).
automaton/3 example  certain employees can’t work at night, others on weekends, we encode this with an automaton that reads a list of who’se on shift. Maybe enough with the employee examples  how about valid messages?
Automaton/8  on hold til I understand it
example for counters  extend the employee example so employees get a max and min number of shifts
14. Scheduling
Scheduling is something we do every day. Bob can only meet from 2 to 3, you need a couple uninterrupted hours to think about the data base, mom’s coming by for lunch. It’s also a major economic constraint  the factory can make tractor parts from march to july but has to convert to making beanie babies for christmas.
14.1. serialized
Serialized expresses the common constraint of not being in two places at once. It takes two lists of the same length, the first is start times and the second durations. It constrains them that intervals defined by the starts and durations don’t overlap. Notice that the starts don’t have to be in order  that is, serialized([4,0,2], [1,1,1]) succeeds.
: use_module(library(pairs)).
my_schedule_today(Starts, Durations) :
% unordered list of stuff to do today
% in a real problem we'd probably use minutes, these are hours in 24 hour format
Starts = [PrepForSmith, MeetWithSmith, _WriteDBInstaller, Lunch, _CallAlice, _ReadDocs],
% and how long they'll take
Durations = [2, 1, 2, 1, 1, 1],
% make all of them start in 9am to 5pm
Starts ins 9..17,
% and make sure lunch happens at noon or 1pm
Lunch in 12 \/ 13,
% Meeting with Smith is planned for 1pm
MeetWithSmith #= 13,
% have to do the prep before the meeting
PrepForSmith #< MeetWithSmith,
% enforce being serialized
serialized(Starts, Durations).
demo_my_schedule(Starts, Durations) :
my_schedule_today(Starts, Durations),
append(Starts, Durations, Vars),
label(Vars),
pairs_keys_values(NameDurs ,
['Prep for Smith', 'Meet With Smith', 'Write DB Installer', 'Lunch', 'Call Alice', 'Read Flubbercalc Docs'], Durations),
pairs_keys_values(Pairs, Starts, NameDurs),
keysort(Pairs, Sorted),
pairs_keys_values(Sorted, SortStarts, SortNameDurs),
print_sched(SortStarts, SortNameDurs).
print_sched([], _).
print_sched([Start  ST], [NameDuration  T]) :
format('~w: ~w (~w hr)~n', [Start, Name, Duration]),
print_sched(ST, T).
8 ? demo_my_schedule(Starts, Durations).
9: Prep for Smith (2 hr)
11: Call Alice (1 hr)
12: Lunch (1 hr)
13: Meet With Smith (1 hr)
14: Write DB Installer (2 hr)
16: Read Flubbercalc Docs (1 hr)
Starts = [9, 13, 14, 12, 11, 16],
Durations = [2, 1, 2, 1, 1, 1] ;
9: Prep for Smith (2 hr)
11: Call Alice (1 hr)
12: Lunch (1 hr)
13: Meet With Smith (1 hr)
14: Write DB Installer (2 hr)
17: Read Flubbercalc Docs (1 hr)
Starts = [9, 13, 14, 12, 11, 17],
Durations = [2, 1, 2, 1, 1, 1]
14.2. global_cardinality/3
global_cardinality/3
counts the number of occurances of each value in it’s first argument.
Here’s an example. Suppose we have a list of employees for the shifts in a 24/7 convenience store.
shifts([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,5,6,4,5,3]).
we want to find out how many shifts each employee gets.
shifts([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,5,6,4,5,3]).
count_shifts(Counts) :
shifts(Shifts),
bagof(X, between(1,6,X), Keys),
length(Values, 6),
pairs_keys_values(Counts, Keys, Values),
global_cardinality(Shifts, Counts, []).
Remember, we’re in constraint land, so this works even if you don’t know shifts ahead of time
post_shifts(Counts) :
length(UnknownShifts, 21),
bagof(X, between(1,6,X), Keys),
length(Values, 6),
pairs_keys_values(Counts, Keys, Values),
global_cardinality(UnknownShifts, Counts, []),
% at this point I have Counts and UnknownShifts constrained,
% though I don't know UnknownShifts
shifts(UnknownShifts). % now it's bound
global_cardinality/3
has two options

consistency(value)
 presents a weaker consistency. I don’t know what this is, if you find out let me know 
cost(Cost, Matrix)
 given a matrix of values for key i in position j, constrain the total cost to Cost
14.3. cumulative/2
and cumulative/1
cumulative/2
takes a list of tasks and constrains them to not exceed a limit at any time during the tasks.
Tasks can be specified flexibly, by any combination of two of start, duration, and end. Each task also has an amount of resources it uses, and a task identifier.
cumulative/1
just defaults the limit to 1.
%
% We have 3 mechanics, and a number of repair jobs to do
% Transmission jobs take two mechanics
%
% Find a set of start times for the jobs during a 10 hour day
%
task_names([
transmission, brake_job_1, brake_job_2, diagnosis_1,
diagnosis_2, fuel_injection]).
tasks([
task(S1,3,_,2,1),
task(S2,1,_,1,2),
task(S3,1,_,1,3),
task(S4,3,_,1,4),
task(S5,3,_,1,5),
task(S6,2,_,1,6)], [S1, S2, S3, S4, S5, S6]).
find_task_starts(S) :
length(S, 6),
S ins 0..9,
tasks(Tasks, S),
cumulative(Tasks, [limit(3)]),
label(S).
2 ? find_task_starts(S).
S = [0, 0, 1, 2, 3, 3] ;
S = [0, 0, 1, 2, 3, 4] ;
S = [0, 0, 1, 2, 3, 5] ;
S = [0, 0, 1, 2, 3, 6] ;
S = [0, 0, 1, 2, 3, 7] .
15. Optimization
We frequently need not only to satisfy a set of constraints, but to find the optimal solution. Problems like "Which of these products should this factory make to maximize profit?" and "Using 3 mechanics, how fast can we repair all these cars?" are optimization problems.
label/1
has an arity two version with a slightly different name, labeling/2
.
The options are the first argument. The options are important for optimization problems, and for increasing the efficiency of the labeling process.
The two we’re concerned with right now are max/1
and min/1
. Adding one of them to the options causes the solutions to be presented in order, with the variable in the leftmost max or min sorted first, then proceeding down the list.
max terms sort decreasing order, min terms sort increasing order.
7 ? [X,Y] ins 1..3, labeling([max(X), min(Y)], [X,Y]).
X = 3,
Y = 1 ;
X = 3,
Y = 2 ;
X = Y, Y = 3 ;
X = 2,
Y = 1 ;
X = Y, Y = 2 ;
X = 2,
Y = 3 ;
X = Y, Y = 1 ;
X = 1,
Y = 2 ;
X = 1,
Y = 3 ;
false.
16. Making Labeling Fast
Internally, labeling/2
attempts to assign values to variables one at a time. Each time a value is chosen, a subtree of possibilities is removed. You want to make those subtrees as large as possible.
16.1. How To Label Efficiently
Start by ordering your variables for labeling. Place the variables that will reduce the search tree by the largest value first. Knowing which these are depends on knowledge of the domain, but you can accumulate data in use if necessary.
Often, within a variable you have latitude how to assign labels. Suppose you’re working on a medical treatment recommending system. Here’s the items:

treat for radiation exposure

prescribe antibiotics

provide hyperbaric repressurization

intubate to provide airway

prescribe painkillers

prescribe anticobra venom

prescribe blood pressure regulators
Common sense is that, hopefully, radiation exposure will be less common than sniffles, so we’ll be matching prescribe antibiotics more often than treat for radiation exposure. So examining items in this order is likely to be faster:

prescribe painkillers

intubate to provide airway

prescribe blood pressure regulators

prescribe antibiotics

provide hyperbaric repressurization

prescribe anticobra venom

treat for radiation exposure
In Prolog this will look something like
treatments([painkillers,
intubate,
bp_regulators,
antibiotics,
hyperbaric_chamber,
anti_cobra_venom,
radiation_exposure
]).
16.2. settings
There are 3 settings in the first argument of labeling/2
; variable selection strategy, value order, and branching strategy. Choose one value for each setting (or use the defaults).
At most one option of each category can be specified, and an option must not occur repeatedly.
To some extent, picking the best settings is a matter of experiment.
Parts of this section are copied from the documentation.
16.2.1. variable selection strategy
The variable selection strategy lets you specify which variable of Vars is labeled next and is one of:

leftmost
 Label the variables in the order they occur in Vars. This is the default. 
ff
First fail. Label the leftmost variable with smallest domain next, in order to detect infeasibility early. This is often a good strategy when there are small domains for the subsequent variables when a first variable is chosen. 
ffc
Of the variables with smallest domains, the leftmost one participating in most constraints is labeled next. Applying a constraint has to remove a subtree, so this can be a good strategy. 
min
Label the leftmost variable whose lower bound is the lowest next. note that this ismin/0
, different thanmin/1
, which determines solution order and is discussed in the previous section above. This is a good tactic if you’re trying to minimize some global value that is likely to be lower if various variables are (e.g. a minimum cost solution). 
max
Label the leftmost variable whose upper bound is the highest next. This too is different thanmax/1
. And the advice formin
applies tomax
when trying to maximize a global value.
16.2.2. value order
The value order is one of:

up
Try the elements of the chosen variable’s domain in ascending order. This is the default. 
down
Try the domain elements in descending order.
Obviously, if you’ve got an assymmetric distribution, like we demonstraed in how to label efficiently above, try elements in most common first order.
16.2.3. branching strategy
The branching strategy is one of:

step
For each variable X, a choice is made between X = V and X #\= V, where V is determined by the value ordering options. This is the default. 
enum
For each variable X, a choice is made between X = V_1, X = V_2 etc., for all values V_i of the domain of X. The order is determined by the value ordering options. 
bisect
For each variable X, a choice is made between X #=< M and X #> M, where M is the midpoint of the domain of X. Choose this option if many variables are selections among a range of integers, a value, rather than one among a set of enumerated values (e.g. percentages, vs a=0, b=1, c=2)
17. Debugging and Testing
Isolating the portion of the program that sets up the constraints allows you to see the constrained domains in the top level.
Here are some predicates that are useful for debugging and for interfacing clp(fd) with the rest of the Prolog environment.
fd_var(+Var)
True iff Var is a CLP(FD) variable.
fd_inf(+Var, Inf)
Inf is the infimum of the current domain of Var.
fd_sup(+Var, Sup)
Sup is the supremum of the current domain of Var.
fd_size(+Var, Size)
Determine the size of a variable’s domain. Size is the number of elements of the current domain of Var, or the atom sup if the domain is unbounded.
fd_dom(+Var, Dom)
Dom is the current domain of Var. This predicate is useful if you want to reason about domains. If you just want to display domains for debugging, use the graphic debugger or toplevel.
indomain/1
binds it’s argument to members of it’s domain on backtracking.
For example, to implement a custom labeling strategy, you may need to inspect the current domain of a finite domain variable. With the following code, you can convert a finite domain to a list of integers:
dom_integers(D, Is) : phrase(dom_integers_(D), Is).
dom_integers_(I) > { integer(I) }, [I].
dom_integers_(L..U) > { numlist(L, U, Is) }, Is.
dom_integers_(D1\/D2) > dom_integers_(D1), dom_integers_(D2).
Example:
? X in 1..5, X #\= 4, fd_dom(X, D), dom_integers(D, Is).
D = 1..3\/5,
Is = [1,2,3,5],
X in 1..3\/5.
Consider clp(fd) for writing mocks.
call_residue_vars/2
calls a predicate, then reports all unresolved constraints or frozen variables. Since usually a proper program resolves all it’s variables, this is useful for finding things not resolved.
Beware that it may be buggy.
18. Applying Constraints in Stages
Being able to hang on to a system of of constrained variables, apply more, and then back up and remove the later constraints is useful.
For example, suppose you have a constraint based drawing program  the sort of program where you draw pieces, and if one is nearly aligned with the other, the program 'realizes' you want them vertically or horizontally aligned. If you then drag one of the blocks, they all move to maintain the constraint.
To resolve the actual position of the blocks, you’re going to have to constrain one of them to the position it was dragged to, causing everything to constrain to single values. But now you’ve lost all your constraints!
There are two solutions to this. The first, backtracking, can work in many situations, but of course enforces a certain structure on the program. So this is more appropriate for situations like a mixed searchconstraint strategy, where you set up some constraints, then search, adding different constraints, and backtracking if the problem becomes overconstrained.
The second solution is copy_term/2
.
copy_term/2
copies a term (often a list of domain variables) and makes a new term with the same shape but with new variables. The copy includes the attributes (and hence the constraints).
By the same shape, we mean:

atomic items match identical items

variables match variables

lists match lists of the same length whose items are the same shape.

compound terms match compound terms of the same functor and arity, whose arguments are the same shape.
10 ? copy_term(foo([bar, A, meep(B, [1,2])], 3), Copy).
Copy = foo([bar, _G2450, meep(_G2456, [1, 2])], 3).
So what happens with constraints?
3 ? X in 0..10, Y in 0..5, X #< Y, copy_term(foo(X,Y), foo(XA, YA)), YA = 3.
YA = 3,
X in 0..4,
X#=<Y+ 1,
Y in 1..5,
XA in 0..2.
Copying half of the constrained variables is generally not a great idea, you’ll end up with links outside your constraint system. Not strictly forbidden, but do it only deliberately, since usually you want the constraint system in a stable place you can come back to.
5 ? X in 0..10, Y in 0..5, X #< Y, copy_term([Y], [YA]), YA = 3.
YA = 3,
X in 0..4,
X#=<Y+ 1,
Y in 1..5.
19. Making Your Own Constraints
First, you often don’t need to make a custom constraint, you need a custom convenience predicate. If you need sort of near to, which constrains X and Y to be N to M spaces from each other, then you can write a normal predicate that applies all the constraints. This is what you’ve been doing all along in this tutorial.
sort_of_near_to(X, Y, N, M) :
X #> Y #==> X  N #>= Y #/\ X  M  1 #< Y,
X #=< Y #==> Y  N #>= X #/\ Y  M  1 #< X.
If you do actually need to write a constraint, here’s how.
First, you’ll need some setup
: use_module(library(clpfd)).
: multifile clpfd:run_propagator/2.
then you need to define the predicate the user uses to apply your constraint.
There are three steps to complete in this predicate.

Convert the constraint to an internal form, the propagator, by calling
clpfd:make_propagator/2
. 
Attach each variable to the propagator by calling
clpfd:init_propagator/2

Trigger the propagator so the initial state is set, we fail if we’re overconstrained, and the initial domain is set, using
clpfd:trigger_once/1
.
% constrain X to be even
even(X) :
clpfd:make_propagator(even(X), Prop),
clpfd:init_propagator(X, Prop),
clpfd:trigger_once(Prop).
Convert the constraint into an internal form Prop , the propagator .
 
Attach each variable (only X here) to the internal propagator.  
Trigger the Propagator once to add the initial state to the system. 
Finally, you need to define the conditional check that’s called when the constraint is evaluated. This requires adding a clause to clpfd:run_propagator/2
.
The first argument of clpfd:run_propagator/2
must match the declaration in make_propagator/2
.
The second argument is a mutable state maintained by clp(fd). It can be used to kill a constraint if it need no longer be triggered, if the constraint has failed or the variable is bound to a valid value, or if it’s domain is now reduced to only values that meet the constraint.
% constrain X to be even
clpfd:run_propagator(even(X), MState) :
( integer(X) > clpfd:kill(MState), 0 is X mod 2
; true
).
And now we can use our new constraint.
[debug] 26 ? even(1).
false.
[debug] 27 ? even(2).
true.
[debug] 28 ? even(X),X = 2.
X = 2.
[debug] 29 ? even(X),X = 3.
false.
Notice that run_propagator is nondeterministic. It can fail (signaling that there is no solution for X). For example, even(X),X = 3.
Fun fact  the Julian library uses clp(fd) extensively. 
20. Conclusion
Remember, constraint programming is something you should consider any time you have several varaibles and need to solve for a compatible solution among all of them.
SWIProlog ships with a number of constraint libraries. If you’re truly inspired, make a tutorial similar to this one for clp(b) or clp(qr) or CHR. If you’re inspired to do this, drop me a line, as we’re trying to get a nice library of these tutorials together, with a common format so we can automate parts of the process downstream.
I hope you’ve enjoyed this tutorial. If you notice any mistakes, or want to suggest improvements, or just are totally stumped, email annie66us (at) yahoo_(dotcom) and let me know.
You can often find me as Anniepoo on ##prolog channel on freenode.net IRC.
Thanks to Markus Triska for the clp(fd) library. Hoot Markus! Thanks to Alan Baljeu for helping with some confusing points. Thanks to Michael Richter for some of the software pipeline setup that produces these tutorials.