Prolog/Constraint Logic Programming

From Wikibooks, the open-content textbooks collection

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.

Before we see the first example of constraint logic programming, it must be noted that there are several 'flavors' of CLP, depending on the allowed domains. In CLP(Q) and CLP(R), variables have rational and real-valued domains, respectively. What we cover here is CLP(fd), where variables have finite, integral domains. Not all Prolog implementations support CLP, but SWI-Prolog, SICStus and ECLiPSe do.

[edit] Getting started

Instead of going through a lot of theory, let's fire up a Prolog interpreter and type some interactive queries to it. First, load the CLP(fd) library. In SWI-Prolog or SICStus:

?- 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.

[edit] 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.