Constraints in Prolog

Question

I am trying to generate 6 vectors of 0 and 1 of size 2N checking constraints written with the XOR operation, the lexicographic order and the symplectic product (close to the scalar product) defined by:

if u = (u1, ..., uN, u_{N+1}, ..., u_{2N}) and v = (v1, ..., vN, v_{N+1}, ... , v_{2N} ) then sigma(u,v)= u1vN + u2v_{N+1} + ... + u_{N}v_{2N} + u_Nv_1 + ... + u_{2N}*v_N

There are more or less 15 constraints and I know there are several solutions.

My problem is that Prolog gives me .false as soon as I put 3 or 4 constraints... so there is a problem in my code and I am totally stuck.

Here is the code:

% Appel automatique à CLP(fd)
:- use_module(library(clpfd)).


% ordre lexicographique
leq([0],[1]).

leq([X|C1],[X|C2]):-
    leq(C1,C2).

leq([0|_],[1|_]).
    
% liste de listes de taille N
lengthliste([X],N):-
    length(X,N).
    
lengthliste([X|L],N):-
    length(X,N),
    lengthliste(L,N).
    


% xor

xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).

xorListe([X1],[X2],[X]):-
    !,xor(X1,X2,X).
    
xorListe([X1|L1],[X2|L2],[X|L]):-
    xor(X1,X2,X),
    xorListe(L1,L2,L),
    !.
    

% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN

% on coupe L en un morceau de taille N et un autre
split(L,0,[],L).

split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).


% produit scalaire
ps([X1],[Y1],Res):-
    Res is X1*Y1.

ps([X1|L1],[X2|L2],Res):-
    ps(L1,L2,Res2),!,
    Res is xor(X1*X2, Res2).

% produit symplectique
sigma(O1,O2,N,Res):-
    split(O2,N,Moitie1,Moitie2),
    append(Moitie2,Moitie1,NewO2),
    ps(O1,NewO2,Res),!.
        





contraintes(O1,O2,O3,O4,O5,C, N):-
    NN is 2*N,
    length(O1,NN),
    length(O2,NN),
    length(O3,NN),
    length(O4,NN),
    length(O5,NN),
    length(C,NN),
    O1 ins {0,1},
    O2 ins {0,1},
    O3 ins {0,1},
    O4 ins {0,1},
    O5 ins {0,1},
    C ins {0,1},
    xorListeListe([O1,O2,O3,O4],O5),
    xorListe(C,O1,D1),
    xorListe(C,O2,D2),
    xorListe(C,O3,D3),
    xorListe(D3,O5,D4),
    xorListe(D3,O4,D5),
    xorListe(D2,O4,D6),
    xorListe(D2,O5,D7),
    xorListe(D1,O4,D8),
    xorListe(D1,O5,D9),
    leq(O1, C),
    leq(O1, O2),
    leq(O2, O3),
    leq(O3, O4),
    leq(O4, O5),
    leq(O1,D1),
    leq(O2,D2),
    leq(O2,D3),
    leq(O1,D4),
    leq(O1,D5),
    leq(O1,D6),
    leq(O1,D7),
    leq(O2,D8),
    leq(O2,D9),
    sigma(O1,O2,N,1),
    sigma(O1,O3,N,1),
    sigma(O1,O4,N,1),
    sigma(O1,O5,N,1),
    sigma(O2,O3,N,1),
    sigma(O2,O4,N,1),
    sigma(O2,O5,N,1),
    sigma(O3,O4,N,1),
    sigma(O3,O5,N,1),
    sigma(O4,O5,N,1),
    sigma(O4,C,N,1),
    sigma(O1,C,N,0),
    sigma(O2,C,N,0),
    sigma(O3,C,N,0),
    labeling([],[O1,O2,O3,O4,O5,C]).  

Thank you and happy Sunday

There is a problem in my code and I am totally stuck.

Answer 1

The following code gives me the only solution for N=2, I removed the cuts and I had to comment out the labeling instruction, I don't know why.

For N=3 the program has been running for several minutes but I still have no results...

I welcome any comments:

% Automatic call to CLP(fd)
:- use_module(library(clpfd)).


% lexicographic order
leq([0],[1]).

leq([X|C1],[X|C2]):-
    leq(C1,C2).

leq([0|_],[1|_]).
    
% list of length N lists
lengthliste([X],N):-
    length(X,N).
    
lengthliste([X|L],N):-
    length(X,N),
    lengthliste(L,N).
    


% xor

xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).

% xor for list
xorListe([X1],[X2],[X]):-
    xor(X1,X2,X).
    
xorListe([X1|L1],[X2|L2],[X|L]):-
    xor(X1,X2,X),
    xorListe(L1,L2,L),
    xorListe(L1, L2, L).

% xorListeListe(L,LL) is True if LL is xorListe(L)
xorListeListe([X1,X2],L):-
        xorListe(X1,X2,L).
        
xorListeListe([X1|X],L):-
        xorListeListe(X,LL),
        xorListe(X1,LL,L).
    

% we compute sigma(u,v) by computing the scalar product between u1,...,uN,uN+1,..U2N and vN+1,...,v2N,v1,...,vN

% we cur L in one piece of length N and one reminder piece
split(L,0,[],L).

split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).


% scalar product
ps([X1],[Y1],Res):-
    Res is X1*Y1.

ps([X1|L1],[X2|L2],Res):-
    ps(L1,L2,Res2),
    Res is xor(X1*X2, Res2).

% symplectic product sigma(u,v)
sigma(O1,O2,N,Res):-
    split(O2,N,Moitie1,Moitie2),
    append(Moitie2,Moitie1,NewO2),
    ps(O1,NewO2,Res),!.
        




% constraints
contraintes(O1,O2,O3,O4,O5,C, N):-
    NN is 2*N,
    length(O1,NN),
    length(O2,NN),
    length(O3,NN),
    length(O4,NN),
    length(O5,NN),
    length(C,NN),
    O1 ins {0,1},
    O2 ins {0,1},
    O3 ins {0,1},
    O4 ins {0,1},
    O5 ins {0,1},
    C ins {0,1},
    xorListeListe([O1,O2,O3,O4],O5),
    xorListe(C,O1,D1),
    xorListe(C,O2,D2),
    xorListe(C,O3,D3),
    xorListe(D3,O5,D4),
    xorListe(D3,O4,D5),
    xorListe(D2,O4,D6),
    xorListe(D2,O5,D7),
    xorListe(D1,O4,D8),
    xorListe(D1,O5,D9),
    leq(O1, C),
    leq(O1, O2),
    leq(O2, O3),
    leq(O3, O4),
    leq(O4, O5),
    leq(O1,D1),
    leq(O2,D2),
    leq(O2,D3),
    leq(O1,D4),
    leq(O1,D5),
    leq(O1,D6),
    leq(O1,D7),
    leq(O2,D8),
    leq(O2,D9),
    sigma(O1,O2,N,1),
    sigma(O1,O3,N,1),
    sigma(O1,O4,N,1),
    sigma(O1,O5,N,1),
    sigma(O2,O3,N,1),
    sigma(O2,O4,N,1),
    sigma(O2,O5,N,1),
    sigma(O3,O4,N,1),
    sigma(O3,O5,N,1),
    sigma(O4,O5,N,1),
    sigma(O4,C,N,1),
    sigma(O1,C,N,0),
    sigma(O2,C,N,0),
    sigma(O3,C,N,0).
    %labeling([],[O1,O2,O3,O4,O5,C]).