Why a clpfd variable is assigned to an actual value in a reification?

Viewed 255

I'm working on a (SWI-)Prolog program that uses CLP(FD) constraints to find a solution for a particular problem. To do so, I happen to need what I call an "unpositioned" overlapping of two lists. That is:

  • List La has length A
  • List Lb has length B
  • A > B
  • The unpositioned overlapping list is La+Lb, where elements are added in a one-by-one fashion.

However, I need Lb to have a variable offset (i.e. each lists' first element are not in the same position for the La+Lb addition. However, list Lb is always within the width of La. For instance:

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   

What I want is to define the offset as a clpfd variable with a particular domain associated to it. In order to compute La+Lb I've written the predicate overlap/6, which is the following:

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+Lb by calling overlap/6 then, with indomain(S), make the numbers converge to a particular solution of the addition. My problem is that when Prolog reaches the line A #= B #<==> S #= Os, S is assigned to Os (a case offset value), rather to constrain A with a reified condition.

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

Edit: The idea is to call overlap/6 for every point within S's domain, and use this constraining list to label a proper S afterwards.

Example of unification:

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

Or:

?- 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]
1 Answers
Related