Re: [eclipse-clp-users] Query reformulation to achieve better propagation

Thank you very much, Marco. I tried your suggestion and it works
as you describe, as far as the constraint propagation is concerned.

However, my original problem was to implement an ic-based (or
gfd-based) solution for the puzzle here:
https://www.puzzle-skyscrapers.com/

I got a solution, quite easily, which works well for small and medium
size instances, but is very inefficient for larger ones (N > 7). When
I injected your propia-based suggestion, the program was even more
inefficient. My assumption is - might be wrong, though - that propia
introduces an overhead which does not pay off, despite the fact that
we have more propagation. I 'll try some more alternatives that I
have in mind and see if things get better. As far as the heuristics
in the search is concerned, it seems that most_constrained/indomain__max
is the best combination for variable/value selection.

Anyway, thank you very much again for your time. If there is any
suggestion on a way to express more efficiently, compared to the
approach that can be inferred from the query in my previouw message,
the constraints of the problem above that refer to the numbers of
visible skyscrapers from the side points, I would be glad to hear it.

Best Regards,
Panagiotis

On 20-Feb-23 1:54 PM, Marco Gavanelli wrote:
> Hi,
> 
> On 20/02/2023 11:27, Panagiotis Stamatopoulos wrote:
>> Hello Everybody,
>>
>> After having loaded libraries ic and ic_global, we give the query:
>>
>> ?- N = 4, Count = 0, length(L, N), L #:: 1..N, 
>> ic_global:alldifferent(L), L = [X1,X2,X3,X4], (X2 #> X1) + (X3 #> 
>> max([X1,X2])) + (X4 #> max([X1,X2,X3])) #= Count.
>>
>> N = 4
>> Count = 0
>> L = [X1{1 .. 4}, X2{1 .. 4}, X3{1 .. 4}, X4{1 .. 4}]
>> X1 = X1{1 .. 4}
>> X2 = X2{1 .. 4}
>> X3 = X3{1 .. 4}
>> X4 = X4{1 .. 4}
>> There are 6 delayed goals.
>> Yes (0.00s cpu)
>>
>> As we may see, from the query we can infer that X1 = 4. Is there
>> any alternative way to pose the query in order to get this result?
>> Note that Count might be anything between 0 and 3 (if we assign it
>> the value 3, we get the answer X1 = 1, X2 = 2, X3 = 3, X4 = 4,
>> as we might expect). But what if Count is less than 3? How could
>> we get the most propagation possible?
> 
> With Count=0 the solver infers that
>      (X2 #> X1) #= 0
> i.e.
>       X2 #=< X1
> 
> I guess you would like to combine that information with the alldifferent 
> constraint, and obtain the stronger constraint
> 
>      X2 #< X1.
> 
> One way to achieve this propagation could be to use, instead of the #< 
> /3 constraint, a constraint that excludes the possibility of having X2 = 
> X1 (i.e., either X1 < X2 or X2 > X1). For example:
> 
> :- lib(propia).
> mygt(X,Y,B):- mygt1(X,Y,B) infers most.
> mygt1(A,B,1):- A #> B.
> mygt1(A,B,0):- A #< B.
> 
> Now this constraint can be used instead of #< /3 :
> 
> ?- N=4, Count=0, L = [X1,X2,X3,X4], length(L, N), L #:: 1..N, 
> ic_global:alldifferent(L), mygt(X2,X1,B1), M12 #= max([X1,X2]), 
> mygt(X3,M12,B2), M123 #= max([X1,X2,X3]), mygt(X4,M123,B3), 
> sumlist([B1,B2,B3]) #= Count.
> 
> N = 4
> Count = 0
> L = [4, X2{1 .. 3}, X3{1 .. 3}, X4{1 .. 3}]
> X1 = 4
> X2 = X2{1 .. 3}
> X3 = X3{1 .. 3}
> X4 = X4{1 .. 3}
> B1 = 0
> M12 = 4
> B2 = 0
> M123 = 4
> B3 = 0
> 
> 
> Delayed goals:
>      mygt1(X2{1 .. 3}, 4, 0) infers most
>      mygt1(X3{1 .. 3}, 4, 0) infers most
>      mygt1(X4{1 .. 3}, 4, 0) infers most
>      alldifferent([X2{1 .. 3}, X3{1 .. 3}, X4{1 .. 3}], 1)
> Yes (0.00s cpu)
> 
> Cheers,
> Marco
>