Difference between matrix column and use of all_different

Question

I'm trying to express a relation on transition from one element in a list-of-lists, to another element. What I want to be able to do, is to say that there should exist a certain difference between two arbitrary elements.

If we have the list

X=[X1,X2,X3,...Xn] 

where all elements are lists of length Y.

I now want to express that there should a difference from Xa->Xb where all elements in Xa is equal or less but one, and Xa and Xb is any given element of X (a!=b)

Ex: If Xa=[1,1,1,1] then Xb could be [1,1,1,2] since all elements are equal or decrease expect one, the last, which goes from 1->2.

I have written the following predicate to do this:

ensure_atleast_n_patterns( ListOfLists, DiffPattern, NoOfAtLeastEqualPatterns ) :-
    ( 
    %Loop through the list to set up the constraint between first
    %element and the rest, move on to next element and and set
    %up constraint from second element on on etc.
    %Ex: if ListOfLists=[X1,X2,X3,X4], the following 'loops' will run:
    %X1-X2, X1-X3,X1-4,X2-X3,X2-X4,X3,X4
    fromto(ListOfLists, [This | Rest], Rest,[_]),
    fromto(0,In1,Out1,PatternCount),
    param([DiffPattern])
    do
        (
            %Compare the difference between two elements:
            foreach( X, Rest ),
            fromto(0,In2,Out2,Sum2),
            param([DiffPattern,This])
            do
                This=[X1,X2,X3,X4,X5],
                X=[Y1,Y2,Y3,Y4,Y5],
                DiffPattern=[P1,P2,P3,P4,P5],
                X1 #< Y1 #<=> R1,
                X2 #< Y2 #<=> R2,
                X3 #< Y3 #<=> R3,
                X4 #< Y4 #<=> R4,
                X5 #< Y5 #<=> R5,
                Result in 0..1,
                (R1 #= P1) #/\ (R2 #= P2) #/\ (R3 #= P3) #/\ (R4 #= P4) #/\ (R5 #= P5) #<=> (Result #=1),
                Out2 #= In2 + Result
        ),
        Out1 #= In1 + Sum2
    ),
    %Count up, and require that this pattern should at least be present
    %NoOfAtLeastEqualPatterns times
    PatternCount #>= NoOfAtLeastEqualPatterns.

This seams to work ok. My problems occurs if I also try to use all_different() on the rows. Ex: I would guess that a solution could be:

 0,0,0,0,0
 2,2,2,2,1
 1,1,1,1,2
 4,4,4,3,4
 3,3,3,4,3
 etc...

But labeling hangs 'forever'

Is my approach wrong? Any better way to solve this?

Test code:

  mytest( X ):-
   Tlen = 10,
   Mind = 0,
   Maxd = 20,
   length( X1,Tlen),
   length( X2,Tlen),
   length( X3,Tlen),
   length( X4,Tlen),
   length( X5,Tlen),
   domain(X1, Mind, Maxd),
   domain(X2, Mind, Maxd),
   domain(X3, Mind, Maxd),
   domain(X4, Mind, Maxd),
   domain(X5, Mind, Maxd),

   all_different( X1 ),
   all_different( X2 ),
   all_different( X3 ),
   all_different( X4 ),
   all_different( X5 ),

   X=[X1,X2,X3,X4,X5],

   transpose( X, XT ),

   ensure_atleast_n_patterns( XT, [0,0,0,0,1],1),
   ensure_atleast_n_patterns( XT, [0,0,0,1,0],1),
   ensure_atleast_n_patterns( XT, [0,0,1,0,0],1),
   ensure_atleast_n_patterns( XT, [0,1,0,0,0],1),
   ensure_atleast_n_patterns( XT, [1,0,0,0,0],1).

And I run it like this:

mytest(X),append(X, X_1), labeling( [], X_1 ).                    

Answer 1

There is one thing that makes me suspect that your code doesn't express what you have in mind. You say: "I now want to express that there should a difference from Xa->Xb where all elements in Xa is equal or less but one, and Xa and Xb is any given element of X (a!=b)". But in your code, you don't consider all pairs of elements. You only consider pairs where Xb is somewhere to the right of Xa (Xb is an element of Rest). This asymmetry likely makes it hard to find solutions.

Nevertheless, here's a solution with Tlen = Maxd = 5:

| ?- mytest([[0,3,4,1,2],[1,2,4,0,3],[1,4,2,0,3],[3,1,4,2,0],[3,4,1,2,0]]).
yes

But due to the asymmetry, the following fails:

| ?- mytest([[0,1,2,3,4],[1,0,3,2,4],[1,0,3,4,2],[3,2,0,1,4],[3,2,0,4,1]]).
no

If you fix your code so that it considers all pairs (Xa,Xb), then from any solution you could get another solution by permuting the elements of ListOfLists (the rows of XT). It's usually a good idea to reduce the search space by breaking this kind of solution symmetry. You can do that with:

lex_chain(XT),

By the way, I recommend all_distinct/1 instead of all_different/1.