Prolog constraint logic programming - Check if elements of list are different (list of lists)

Question

I'm stuck on this exercise for some time. What I am trying to accomplish is:

Given a List of Lists, check if all elements are different. For example:

Ex1 -

L=[[1,2,3],[3,2,1],[2,1,3]], check_diff(L).
%must return true

Ex2 -

L=[[1,2,3],[2,3,1],[2,1,3]], check_diff(L).
%must return true

Ex3 -

L=[[1,2,3],[1,2,3],[3,1,2]], check_diff(L).
%must return false

My goal is, after knowing a solution to this, apply it to Prolog constraint logic programming in order to restrict the possibility of the elements of any list L (list of lists) being the same.

In other words: Apply all_different predicate on Sicstus Prolog but this time, for List of Lists.

Since list difference here seems to be defined by their inability to be unified, which is not same elements, or same elements in a different order for lists, then solve it for simple atoms and you should be able to apply the results. Don't get hung up on the elements themselves being lists for now. — lurker
You can use the reification predicates, as P#<==>Q, and boolean variables. For each combination of lists (L1,...,Ln), for each element (L1E1,...,LnEn), L1E1 #= L2E1 #<==> B1 ecc, where Bk is a boolean variable, then constraint the sum of the list with all the Bk relative a certain combination, to be less than the number of element into each list. BTW this method doesn't do a lot of propagation... — damianodamiano

damianodamiano damianodamiano · Accepted Answer · 2017-12-10T20:26:39

Here the solution using boolean variables (i wrote it using ECLiPSe prolog, sholud't be difficult translate it in another prolog...)

:-lib(fd).

allListsDifferent2([],[],[]).
allListsDifferent2([H1|T1],[H2|T2],[HB|TB]):-
    H1 #= H2 #<=> HB,
    allListsDifferent2(T1,T2,TB).

allListsDifferent1(_,[]).
allListsDifferent1(HA,[HB|T]):-
    length(HA,N),
    length(LB,N),
    LB::0..1,
    fd_global:sumlist(LB,S),
    S #< N,
    allListsDifferent2(HA,HB,LB),
    allListsDifferent1(HA,T).

allListsDifferent([_]).
allListsDifferent([HA,HB|T]):-
    allListsDifferent1(HA,[HB|T]),
    allListsDifferent([HB|T]).

?- allListsDifferent([[1, 2, 3], [3, 2, 1], [2, 1, 3]]).
Yes (0.02s cpu, solution 1, maybe more)
No (0.03s cpu)
?- allListsDifferent([[1, 2, 3], [3, 2, 1], [3, 2, 1]]).
No (0.00s cpu)

Prolog constraint logic programming - Check if elements of list are different (list of lists)

1 Answers