- 1. About This Tutorial
- 2. The CLP(FD) Library
- 3. Variables
- 4. An Example
- 5. Labeling
- 6. Simple Constraints
- 7. Constraining to a Domain
- 8. Arithmetic Operators
- 9. Logical Operators
- 10. Reification
- 11. Commonly Useful Constraints
- 12. Resources
- 13. Sequences
- 14. Scheduling
- 15. Optimization
- 16. Making Labeling Fast
- 17. Debugging and Testing
- 18. Applying Constraints in Stages
- 19. Making Your Own Constraints
- 20. Conclusion
This tutorial is for reasonably experienced SWI-Prolog 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 SWI-Prolog documentation of the clp(fd) predicates from the rather terse, math laden documentation to a more approachable level of English.
clp(fd) is a library included in the standard SWI-Prolog 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:
-
Ensuring program correctness by constraining variables to reasonable ranges
-
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.
Make up another example for each of the categories above.
Try to expand the domain of the problem as much as you can.
For example, we usually think of sequencing as time, but it could be some other dimension. Given a set of train cars, putting them in an order that makes sense and obeys some rules like no tank cars next to the engine, the caboose has to be on the back, etc. is a sequence problem.
Don’t worry if you have trouble with this one - it’s OK to punt some.
Competence in the basics of SWI-Prolog.
A level of mathematical sophistication comparable to that of an upper level standing in a computer science undergrad program.
A working SWI-Prolog installation.
There is no set of additional code for this tutorial. You can cut and paste many of the examples.
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 SWI-Prolog programs.
The clp(fd) library for SWI-Prolog 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 SWI-Prolog. There are others: clp(b), clp(qr). clp(b) handles booleans. clp(qr) handles rationals and reals. CHR is a tool for making your own constraint systems (among other things).
The clp(fd) library can be activated by simply
:- use_module(library(clpfd)).
This installs a compile-time hook that optimizes some clp(fd) constraints, and loads a run-time library.
We use the term variable rather loosely in computer science.
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).
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.
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 call this it’s domain.
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)). (1)
test(X, Y) :-
X in 0..10, (2)
Y in 4..8, (3)
X #> Y. (4)
14 ?- test(X, Y).
X in 5..10, (5)
Y#=<X, (6)
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, (1)
Y = 4. (2)
-
X is bound just like normal Prolog
-
Notice that Y is bound too. Further, it’s lost it’s original constraints
Type in and try the two examples above. Step into them with the graphic debugger to see the constraints listed.
:- use_module(library(clpfd)). foo(X) :- X in 1..3 . foo(X) :- X in 5..7 . foo(X) :- X in 8..12 .
What will happen if you query foo(X) and get all the solutions by backtracking? Predict what will happen, and then try it. Was your prediction correct?
SWI-Prolog has the ability to add attributes to variables. This is additional meta-data attached to the variable. If you’re interested, you can read more about attributed variables at The SWI-Prolog 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.
More on this at the end of the tutorial.
Extra credit -
Think up another use for attributes on variables besides constraints
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.
clp(fd) works with a domain like [air, land, sea], but can’t optimize well. Better to map air=0, land=1, sea=2 and then say the domain is 0..2 .
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.
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)). (1)
puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :- (2)
Vars = [S,E,N,D,M,O,R,Y], (3)
Vars ins 0..9, (4)
all_different(Vars), (5)
S*1000 + E*100 + N*10 + D + (6)
M*1000 + O*100 + R*10 + E #=
M*10000 + O*1000 + N*100 + E*10 + Y,
M #\= 0, S #\= 0, (7)
label(Vars). (8)
9 ?- puzzle(X).
X = ([9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2]) ; (9)
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
1) Solve the cryptarithm FORTY + TEN + TEN = SIXTY by modifying the program
2) are there more solutions to SEND+MORE=MONEY if you allow leading zeros? Modify the program to find out.
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.
You can simply ground the variable normally. The usual X = 3 constrains the variable to a single value.
And the predicate indomain/1 successively binds a single variable to it’s possible values on backtracking.
But mostly 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.
|
Tip
|
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.
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
|
Tip
|
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.
|
|
Tip
|
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 SWI-Prolog 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)].
Write a predicate increase/1 that takes a list and constrains it to be strictly increasing.
First record what result you expect from each query below. Then test that your predicate does what you expect.
?- increase([1, X, 3]). ?- increase([1, X, 4]). ?- increase([1,X, Y, 4]). ?- increase([1,2]). ?- increase([1,X]).
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.
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.
X in 5..10, (1) Y in 1..10, (2) Y #> X (3)
-
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.
Oddly, for all the talk of finite domains, it’s allowed to constrain a variable to a domain like 4..sup - 4 through infinity. inf is negative infinity.
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 .
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.
Try the above Complex Domain example, and
then change the last range to 16 .. sup.
Notice that it simplifies the domain.
What if your domain data comes from input data? Suppose we get a data structure from somewhere and need to constrain to it in some way.
Assemble your domain as a term MyDomain 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 ;
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
Reification is the process of using constraints to control other constraints. clp(fd) includes two operators for reification.
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.
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).
Notice that StartTime is passed in as a constraint , and used to apply
to the logical operators.
This means you can build up constraints and pass them around, applying them later, or building up more complex constraints using them.
Write a small system that matches people with jobs. The jobs have requirements for education level, weight they can lift, age, distance from home. Be able to record special constraints in the individual’s record - eg. Bob’s on parole and can’t work more than 20 miles from home. Sally wants a helper, but has had problems with workers hanging around when not working, she wants someone who lives more than 10 miles away.
People have funny situations, so try to make it general.
For this exercise you can make the (unrealistic) assumption that users know Prolog.
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.
This of course is good ol' length. It’s useful in the length(-, +) mode to generate a list of unbound variables.
|
Tip
|
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.
|
?- length(X, 5).
Now try
?- length(X, Y).
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, let’s try constraining 3 variables to be different values from 1..2 - an impossibility.
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.
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 SWI-Prolog 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.
no 1. Modify the Train Journey program so it finds routes with any number of trains, not just 3.
no 2. You are asked to produce a table of employees who are eligible for promotion. You have this list of lists. Each inner list is a record for a single employee. The fields are employee #, last review score, # of safety violations, time in grade, required time for promotion
employees([ [1, 75, 0, 30, 25], [2, 83, 0, 45, 25], [3, 90, 1, 45, 50], [4, 45, 3, 75, 25], [5, 89, 0, 52, 50] ]).
To be eligible for promotion an employee must have a last review score of 80 or above, no more than one safety violation, and their time in grade must be more than the required time for promotion.
no 3. The last column, time required for promotion, isn’t normalized. Employees are either team members or team leaders. Team members need 25 weeks in grade, team leaders need 50. The cheif architect has decided to abstract these into a second table so these numbers can be changed easily.
employees([ [1, 75, 0, 30, 1], [2, 83, 0, 45, 1], [3, 90, 1, 45, 2], [4, 45, 3, 75, 1], [5, 89, 0, 52, 2] ]). time_in_grade([[1,25], [2,50]]).
Update exercise 2 to use the new data format.
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.
|
Tip
|
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.
Write a predicate that will be part of a roguelike game.
Your game board is a 2D array (list of lists). Each square contains one of the following
-
0 - floor
-
1 - walls
-
2 - monster
-
3 - the player
write a predicate, can_move(+Board, -Moves) Board will be a board as defined above SafeMoves will be a list of lists, with a 1 where the player can move and a 0 where they cannot. Enforce these rules:
-
The player can move 0,1,2, or 3 spaces, connected horizontally and vertically, not diagonally.
-
The player cannot pass through or end on walls
-
the player cannot pass through or end adjacent to monsters
-
The player cannot move off the board
Sample run (some liberties taken for readability):
board([ [1,1,1,1,1,1,1,1], [1,0,2,0,0,0,0,0], [0,1,0,0,0,2,0,0], [0,0,1,0,0,0,0,3], [0,0,0,1,0,0,2,0], [0,0,0,0,1,0,0,0], [0,0,0,0,0,1,0,0], [0,0,0,0,0,0,1,0], [0,0,0,0,0,0,0,1] ]). ?- board(B), can_move(B, M), writeq(M). M = [ [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0] ]
Hint: write a predicate to print out M in a more readable format Extra credit: use the terminal coloring library to make that fancy
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.
|
Tip
|
Annie is here, looking like this =8cO trying to imagine debugging code that uses lots of zcompares |
create a constraint same_side_of_line/4 , whose arguments are dicts of the form
point{x:12.34, y:56.78}
The first two arguments are points on a line, the next two are two test points. The predicate succeds if both test points are on the same side of the line, or both are on the line, the constraint holds.
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 ; ...
|
Tip
|
Try the penny candy example without the Candy ins 0..sup line.
What will happen?
|
We often need things to be in a specific sequence.
These constraints help establish sequences.
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.
lex_chain/1 is more interesting. It takes a list of lists.
It constrains the inner lists to be lexicographically non-decreasing. 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.
Patients in a hospital have a coded set of information as a term.
patient(ID, Name, YearAdmitted, MonthAdmitted, DayAdmitted, HourAdmitted, MinuteAdmitted, Status, Payment)
Status is either 0 (normal) or 1 (emergency).
Payment is either 0 (private), 1 (insurance), or 2 (medicaid).
here’s some patients
patient(1, 'Bob Jones', 2014, 10, 1, 4, 55, 0, 2). patient(2, 'Sally Smith', 2014, 9, 29, 5, 15, 1, 0). patient(3, 'Ted Overton', 2014, 9, 30, 14, 15, 0, 0). patient(4, 'Arnold Abouja', 2014, 10, 1, 5, 0, 0, 0). patient(5, 'Seth Humbolt', 2014, 10, 1, 5, 10, 0, 0).
constrain the patients to be seen acording to these rules:
-
See all emergency cases first, before any normal cases.
-
for patients with same status (emergency/normal), see patients in the order they arrived, except
-
If a private or insurance patient arrived up to an hour after a medicaid patient, see them first.
Hint: use lex_chain
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.
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] .
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 SWI-Prolog:
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
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.
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], [Name-Duration | 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]
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
Design an exercise that covers the cost/2 option of global_cardinality. Include a solution.
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] .
1) It looks like the mechanics aren’t very busy. Add a few more tasks.
2) Mechanic 3 only works the first 3 hours of the day. Modify the example to take this into account.
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.
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.
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 anti-cobra 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 anti-cobra 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 ]).
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. If you get desperate, there’s an undocumented random_value(Seed) (props to adbenitez for pointing
this out) or random_variable .
Parts of this section are copied from the documentation.
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. -
ffFirst 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. -
ffcOf 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. -
minLabel 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). -
maxLabel the leftmost variable whose upper bound is the highest next. This too is different thanmax/1. And the advice forminapplies tomaxwhen trying to maximize a global value.
The value order is one of:
-
upTry the elements of the chosen variable’s domain in ascending order. This is the default. -
downTry 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.
The branching strategy is one of:
-
stepFor 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. -
enumFor 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. -
bisectFor 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)
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.
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 search-constraint 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.
Write a small graphics program, using whatever graphics environment you’re comfortable with, that draws a set of dots on the screen. If you move one of the dots to be aligned withanother, vertically or horizontally, within a few pixels, then the two should be linked, and move together. Holding down shift always just moves one dot.
Extra Credit Expand your program into a small diagram editor.
(Note, you’re near the end of the tutorial, you might want to read to the end at the same time you’re working this problem).
Implement a constraint shell decision support system. This should allow the user to define constraints one at a time using some simple command language (not programming) and see the domains of variables. The user should be able to remove any of the constraints they have entered.
Sample run
?-decision_support. Decision Support (type h for help) ds=h l = list all variables and constraints <variable name> in <integer> thru <integer> = define new variable <variable name> <operator> <integer or variable name> = define new constraint r <number> = retract constraint <number> q = quit ds=a in 1 thru 10 a in 1..10 ds=b in 1 thru 10 b in 1..10 ds=a < b #1: a < b ds=b < 5 #2: b < 5 ds=l variables a in 1..3 b in 1..4 constraints #1: a < b #2: b < 5 ds=r 2 retracting #2: b < 5 ds=b < 8 #3: b < 8 ds=l variables a in 1..6 b in 1..7 constraints #1: a < b #3: b < 8 ds=q ?-
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), (1)
clpfd:init_propagator(X, Prop), (2)
clpfd:trigger_once(Prop). (3)
-
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.
Put a spy point on clpfd:run_propagator/2 and query even(X), X = 3.
How many times is run_propagator called?
|
Tip
|
Fun fact - the Julian library uses clp(fd) extensively. |
Remember, constraint programming is something you should consider any time you have several variables and need to solve for a compatible solution among all of them.
SWI-Prolog 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.