Prolog

CLP(FD)

---

intro

CLP(FD) is a library that help us use constraints over integer values.

• CLP = Constraint Logic Programming.
• FD = Finite Domains.

usage

in order to use CLP(FD), write the following in the REPL:

use_module(library(clpfd)).

…or write the following at the top of a file:

:- use_module(library(clpfd)).

---

comparison operators

The comparison operators are almost the same but prefixed by #

X #> Y.
X #< Y.
X #>= Y.
X #=< Y.
X #= Y.
X #\= Y.

comparison operators

X and Y can be any arithmetic expression:

• An integer value.
• A variable.
• -Expr
• Expr1 @ Expr2 where @ is replaced by + * - ^ // div mod rem
• abs(Expr)
• min(Expr1,Expr2)
• max(Expr1,Expr2)

comparison operators

How are these different from the regular comparison operators?

?- X + 2 =:= Y + X.

?- X + 2 #= Y + X.
% Y = 2, X in inf..sup.

The #-operators don’t require that any of the variables are instantiated

---

domains

CLP(FD) can give a domain as a solution:

?- 0 #< X, X #< 5.
% X in 1..4.

domains

In a domain, sup is for supremum and inf is for infimum.

?- 0 #< X.
% X in 1..sup.

?- X #< 5.
% X in inf..4.

domains

We can use the in operator in our code.

?- X in 1..5.

domains

\/ is used for domains union

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

?- X in 1\/2\/3.
% X in 1..3.

labeling

indomain(X) is used to successively bind X to all integers of its domain:

?- X in 1..3, indomain(X).

labeling

indomain must always terminate:

?- X in 0..sup, indomain(X).

labeling

label is just like indomain but for a list of variables:

?- 0 #=< N, N #< 17, 0 #< A, 0 #< B, N * N #= A * A + B * B, label([N, A, B]).

---

question

Implement the predicate change/2. change(S, L) is true iff:

• S is a positive integer
• L is a sorted (descending) list made of the integers 1, 5, 10
• S is the sum of the numbers in L

(assume S is concrete)

?- change(21, [10, 5, 1, 1, 1, 1, 1, 1]).

Hint - you can use a helper predicate repeat/3. repeat(N, C, L) is true iff:

• N is a conrete non-negative integer.
• L is a list of N Cs.

Another Hint - you can use a helper predicate build/2. build(Ls, L) is true iff:

• Ls is a list of pairs [N, C] where N is a concrete non-negative integer.
• L is a list containing Ni Cis, for each i in range.

...

repeat(0, _, []).
repeat(N, C, [C|Xs]) :-
	N #> 0,
	Ns #= N - 1,
	repeat(Ns, C, Xs).

build([], []).
build([[N,C]|T], L) :- repeat(N, C, Xs), build(T, Ys), append(Xs, Ys, L).

change(S, L) :-
    S #= A1 + A5 * 5 + A10 * 10,
    A1 #>= 0, A5 #>= 0, A10 #>= 0,
    label([A1, A5, A10]),
    build([[A10, 10], [A5, 5], [A1, 1]], L)
.