Prolog combinations with constraints

2
votes

I am looking for a way to find all possible solutions given a certain set of constraints. I had prolog in school but it has been a while so consider me fairly new. What I want to achieve is something like this:

fC(U,V,X,Y,Z):- 
    (U*2 + V - Y -(2*Z)) =< -5,
    (U*2 + V - Y -(2*Z)) >= -108,
    (U+V+X+Y+Z) =:= 54.

U, V, X, Y, and Z are non negative numbers. They only have 2 rules to compute them: be between -5 and -108 (when multiplied with certain weight which I tried to formulate in the code above) and added together be exactly 54.

I tried generating 5 lists of 0 to 54, find all combinations and then go over them to check my 'constraints', I quickly ran out of memory so I must be doing something wrong.

Kind regards,

Jelle

2
prologcombinations

2 Answers

2
votes

For integers, it is easy with constraints. For example, in SICStus Prolog or SWI:

:- use_module(library(clpfd)).

fC(U,V,X,Y,Z):- 
    U*2 + V - Y -2*Z #=< -5,
    U*2 + V - Y -2*Z #>= -108,
    U+V+X+Y+Z #= 54.

You already obtain residual goals with the most general query:

?- fC(U, V, X, Y, Z).
X+U+V+Z+Y#=54,
2*Z+Y#=<2*U+V+108,
2*U+V+5#=<2*Z+Y.

This of course does not help much by itself in this case.

To get concrete solutions, use labeling/2. For example:

?- fC(U, V, X, Y, Z), Vs = [U,V,X,Y,Z], Vs ins 0..sup, label(Vs).

The constraint Vs ins 0..sup states that all variables are non-negative. In SICStus Prolog, use domain(Vs, 0, sup).

Sample solutions:

U = V, V = X, X = Y, Y = 0,
Vs = [0, 0, 0, 0, 54],
Z = 54 ;
U = V, V = X, X = 0,
Vs = [0, 0, 0, 1, 53],
Y = 1,
Z = 53 ;
etc.

For constraints over rational numbers, check out constraints and library(clpq).

0
votes

a 'low-tech' alternative... but really, use library(clpfd)

?- maplist(between(0,54),[U,V,X,Y,Z]),fC(U,V,X,Y,Z).
U = V, V = X, X = Y, Y = 0,
Z = 54 ;
U = V, V = X, X = 0,
Y = 1,
Z = 53 ;
U = V, V = X, X = 0,
Y = 2,
Z = 52 ;
...