CLP(FD) labeling/2 predicate

Help! Predicate
1

Hi,

I cannot figure out how the ff option works for the labeling/2 predicate

X in 1..5, Y in 1..2, X + Y #= 6, labeling([ff],[X,Y]).
X = 4,
Y = 2
X = 5,
Y = 1

I would have expected solution X=5 and Y=1 to come up first. There is no difference if I use lefmost instead of ff

2

You could check the code: https://github.com/SWI-Prolog/swipl-devel/blob/06aed1f8902aaba51ae6818e18999bd99da2ec46/library/clp/clpfd.pl#L1724

3

So one of the benefits of constraints, are that as you add new constraints, they can further constrain existing variables via constraint propagation. Prior to X+Y #= 6, X had 5 possible values and Y had 2 possible values. Labeling with ff at that point would try and restrict values for Y first as it has the smallest domain. However, once you added the constraint X+Y #= 6, clpfd is smart enough to reduce the domain of X to just 2 possible values. If you run your statement without labeling you will see:

?- X in 1..5, Y in 1..2, X + Y #= 6.
Y in 1..2,
X+Y#=6,
X in 4..5

So now both variables have the same domain size of two possible values. X is 4 or 5, Y is 1 or 2.

Now if you look at the help for labeling options:

First fail . Label the leftmost variable with smallest domain next, in order to detect infeasibility early. This is often a good strategy

Then you should see why it try the values of X first rather than Y.

HTH.

4

Oh yes of course, labeling takes place after constraints propagation. It was a stupid question.

Thank you very much for your answer.