Geek Answers Handbook

Why is the clpfd variable assigned to the actual value in reification?

I am working on a (SWI-) Prolog program that uses CLP (FD) constraints to find a solution for a specific problem. To do this, I need what I call the “non-positioned” overlap of the two lists. I.e:

  • The list Lahas length A
  • The list Lbhas length B
  • A> B
  • A non-positional, overlapping list La+Lbwhere items are added alternately.

However, I need to Lbhave a variable offset (i.e. the first element of each list is not in the same position to add La+Lb. However, the list is Lbalways within the width La. For example:

Be La = [0,1,1,1,1,0,1,1,1]and Lb = [1,2,2].

Possible case 1

(Lb) 1 2 2 . . . . . . ---> offset = 0
(La) 0 1 1 1 1 0 1 1 1
( +) 1 3 3 1 1 0 1 1 1

Possible case 2

(Lb) . . . 1 2 2 . . . ---> offset = 3
(La) 0 1 1 1 1 0 1 1 1
( +) 0 1 1 2 3 2 1 1 1

Possible case 3

(Lb) . . . . . 1 2 2 . ---> offset = 5
(La) 0 1 1 1 1 0 1 1 1
( +) 0 1 1 1 1 1 3 3 1

I want to define offsetas a clpfd variable with a specific domain associated with it. For calculation, La+LbI wrote a predicate overlap/6that looks like this:

overlap([],[],_,_,_,[]) :- !.
overlap([],_, _,_,_,[]) :- !.
overlap(A, [],_,_,_, A) :- !.
overlap(A, _,Os,_,_, A) :- length(A,L), L =< Os, !.
overlap([A|As],[B|Bs],0,Os,S,[A|Ls]) :-  % Os is the actual Offset 
    A #= B #<== S #= Os,                 % S is a clpfd variable
    overlap(As,Bs,0,Os,S,Ls),!.
overlap([A|As],Bs,Acc,Os,S,[A|Ls]) :-
    Acc > 0,
    Acc0 is Acc-1,
    overlap(As,Bs,Acc0,Os,S,Ls),!.

The idea is to find La+Lbby calling overlap/6, and then indomain(S), so that the numbers converge to a particular solution to the addition. My problem is that when Prolog reaches the line A #= B #<==> S #= Os, it is Sassigned Os(offset value), instead of holding back Awith the reified condition.

Am I crazy and that makes no sense? Is there a proper way to do what I'm trying? Thanks in advance!

: , overlap/6 S S.

:

?- S in 0..2,
   L0 = [0,0,0,0],
   overlap(L0, [1,2], 0, S, L1),
   overlap(L1, [1,2], 1, S, L2),
   overlap(L2, [1,2], 2, S, L).
L = [_G1, _G2, _G3, _G4]

_G1 in 0\/1
_G2 in 0\/1\/2
_G3 in 0\/1\/2
_G4 in 0\/2

_G1 #= 1 #<== S #= 0
_G1 #= 0 #<== S #> 0

_G2 #= 2 #<== S #= 0
_G2 #= 1 #<== S #= 1
_G2 #= 0 #<== S #> 2

_G3 #= 0 #<== S #= 0
_G3 #= 2 #<== S #= 1
_G3 #= 1 #<== S #< 2

_G1 #= 0 #<== S #= 0
_G4 #= 0 #<== S #= 1
_G4 #= 2 #<== S #= 2

:

?- S in 0..2,
   L0 = [0,0,0,0],
   overlap(L0, [1,2], 0, S, L1),
   overlap(L1, [1,2], 1, S, L2),
   overlap(L2, [1,2], 2, S, L),
   indomain(S).
S = 0
L = [1, 2, 0, 0]
+4
1

S, , . :

:- use_module(library(clpfd)).

overlap_at(As, Bs, S, ABs) :-
        length(As, L),
        L1 #= L - 1,
        S in 0..L1,
        overlap_at_(As, Bs, S, 0, ABs).

overlap_at_([], _, _, _, []).
overlap_at_([A|As], Bs, S, N0, [AB|ABs]) :-
        overlap_here(Bs, [A|As], [AB|ABs], Conj),
        S #= N0 #==> Conj,
        S #> N0 #==> AB #= A,
        N1 #= N0 + 1,
        overlap_at_(As, Bs, S, N1, ABs).

overlap_here(_, [], _, 1) :- !.
overlap_here([], _, _, 1).
overlap_here([B|Bs], [A|As], [AB|ABs], (AB #= A + B #/\ Rest)) :-
        overlap_here(Bs, As, ABs, Rest).

, overlap_here/4.

:

?- overlap_at([0,1,1,1,1,0,1,1,1], [1,2,2], 3, ABs).
ABs = [0, 1, 1, 2, 3, 2, _G909, _G912, _G915],
_G909 in inf..sup,
_G912 in inf..sup,
_G915 in inf..sup.

: . , : , ,

?- overlap_at([0,1,1,1,1,0,1,1,1], [1,2,2], S, ABs), 
   indomain(S), writeln(ABs), false.

- :

[1,3,3,_,_,_,_,_,_]
[0,2,3,3,_,_,_,_,_]
[0,1,2,3,3,_,_,_,_]
[0,1,1,2,3,2,_,_,_]
[0,1,1,1,2,2,3,_,_]
[0,1,1,1,1,1,3,3,_]
[0,1,1,1,1,0,2,3,3]
[0,1,1,1,1,0,1,2,3]
[0,1,1,1,1,0,1,1,2]

: , , A. , , .

+3

More articles:


All Articles