Prolog/Constraint Logic Programming

We've seen that in Prolog, a variable can be either bound (have a value, possibly another variable) or free (have no value). Constraint logic programming (CLP) extends the notion of a logical variable by allowing variables to have a domain rather than a specific value. Variables can also be constrained, which means that their value must abide by certain rules specified by the programmer. Constraint logic programming makes it possible to solve complex combinatorial problems with a minimum amount of code.

Introduction: the dif/2 constraint

Often, Prolog programming revolves around constraints on the values of variables, embodied in the notion of unification. For example, the goal X = f(1) can be said to constrain the variable X to take on the value f(1). Unification is of course more general than this, since X = Y constrains two variables to take on the same value, while X = f(_) constrains X in yet a third way: it may take on any of an infinite set of values that includes f([]) and f(hamburger), but the value it takes on must match the "template" f(_).

Standard unification is limited, though, in that it can only put a "positive" constraint on a variable. If we want to state that X may be bound to any value other than those matching f(_), then we can use unification together with negation, but we have to be very careful. As we've seen in an earlier chapter, we can sometimes use negation as failure to express inequality, but this is not always reliable:

?- X = 1, \+ X == 1.
false.

?- \+ X == 1, X = 1.
true

This non-monotonic property of \+ forces us to reorder goals to get variables bound at just the right time, making code harder to read, write and understand.

Exercise. Write a predicate that succeeds when its input is a list containing only unique values. E.g. unique([1,2]) should succeed, but unique([foo,foo,1]) should fail because foo appears twice. How does your predicate deal with unique([X,X])? How about unique([A,B,C,D])?

Enter the dif predicate. This predicate, available in SWI and SICStus (but not strictly standard Prolog) allows us to constrain two variables to be different. The following SWI-Prolog session shows its operation:

?- dif(X,Y).
dif(X,Y).

?- dif(X, Y), member(X, [foo, bar]), member(Y, [foo, bar]).
X = foo,
Y = bar ;
X = bar,
Y = foo ;
false.

Contrast this with the result of the other inequality predicates \= and \==.

Exercise. Implement the unique/1 predicate again, but this time use dif/2. What is Prolog's response to the query unique([A,B,C,D,E])? How many constraints does it report?

Exercise. Write a predicate not_f1/1 that constrains its argument to not be of the form f(_), i.e. not a one-argument term with functor f Hint: use the =.. ("univ") operator.

Finite-domain constraints

We now turn to a much more powerful constraint handling system: constraint logic programming on finite domains, also known as CLP(fd). To use this, we must load a library. In SWI-Prolog, that's:

?- use_module(library(clpfd)).

Do you remember how arithmetic in Prolog fails when used with insufficiently instantiated variables? Try this for a starter:

?- X > Y, member(X,[1,2,3]), Y=2.

Even though there is logically one possible answer to this query (X=3), Prolog cannot infer it. We can get the right answer by rearranging the conjuncts of the query:

?- member(X,[1,2,3]), Y=2, X > Y.

CLP(fd) is a lot smarter than Prolog when it comes to arithmetic. Try this (note: ECLiPSe users should replace in by ::):

?- X #> Y, X in 1..3, Y=2.

This succeeds with the only correct answer, X=3. The predicate #>/2, when given two variables, posts the constraint that it left argument should be greater than its right argument. CLP(fd) holds this constraint in its constraint store until it knows enough about the variables' possible values to infer further information from it. The moment that Y gets the value 2, CLP(fd) infers that X can only have the value 3.

What happens when we bind Y to 1 instead?

?- X #> Y, X in 1..3, Y=1.
Y = 1,
X in 2..3.

Rather than start backtracking over the possible values of X, CLP(fd) constrains X to a smaller domain and stops. To have CLP(fd) search for possible assignments to variables, we must tell it do so explicitly. The simplest way to do that is with the predicate label/1:

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

What we've seen so far isn't very interesting, because there was only one constraint variable. Let's have a look at a problem with eight variables.

Send more money

The send more money puzzle is the quintessential example of a constraint problem. It amount to assigning different digits 0 through 9 to the variables [S,E,N,D,M,O,R,Y] such that the sum

   SEND
+  MORE
= MONEY

is solved; S and M should both be greater than zero. Instead of typing to the Prolog prompt, let's make a proper Prolog module.

:- use_module(library(clpfd)).

sendmoremoney(Vars) :-
    Vars = [S,E,N,D,M,O,R,Y],
    Vars ins 0..9,
    S #\= 0,
    M #\= 0,
    all_different(Vars),
                 1000*S + 100*E + 10*N + D
    +            1000*M + 100*O + 10*R + E
    #= 10000*M + 1000*O + 100*N + 10*E + Y.

ins/2 is the same as in/2, except that it sets the domains of several variables at the same time. (ECLiPSe: use ::, SICStus: use domain(Vars,0,9)). all_different (which may be called all_distinct in some implementations) is logically equivalent to posting disequality constraints (#\=) on all pairs of variables in Vars, but is shorter and possibly more efficient. Note that we can express the sum as one constraint over all eight variables at the same time. Let's try this out:

?- sendmoremoney([S,E,N,D,M,O,R,Y]).
S = 9,
M = 1,
O = 0,
E in 4..7,
all_different([E, N, D, R, Y, 0, 1, 9]),
1000*9+91*E+ -90*N+D+ -9000*1+ -900*0+10*R+ -1*Y#=0,
N in 5..8,
D in 2..8,
R in 2..8,
Y in 2..8.

Even without labeling variables, CLP(fd) has inferred the values of three variables, has simplified the sum and put tighter bounds on the remaining five variables. Ofcourse, we want values for all our variables:

?- Vars=[S,E,N,D,M,O,R,Y], sendmoremoney(Vars), label(Vars).
Vars = [9, 5, 6, 7, 1, 0, 8, 2],
S = 9,
E = 5,
N = 6,
D = 7,
M = 1,
O = 0,
R = 8,
Y = 2

This should run instantly. Exercise: implement the puzzle in Prolog without CLP(fd), and notice how long it takes to run.