/* Generer et tester */

tousDifferent([]).
tousDifferent([X|R]) :- not(member(X, R)) , tousDifferent(R).

carre(S) :-
S = [ A0, A1, A2, B0, B1, B2, C0, C1, C2],
Domaine = [1, 2, 3, 4, 5, 6, 7, 8, 9],
/* On genere */
member(A0, Domaine), member(A1, Domaine), member(A2, Domaine),
member(B0, Domaine), member(B1, Domaine), member(B2, Domaine),
member(C0, Domaine), member(C1, Domaine), member(C2, Domaine),
/* on teste */
tousDifferent(S),
LigneA is A0+A1+A2,
LigneB is B0+B1+B2,
LigneC is C0+C1+C2,
Colonne0 is A0+B0+C0,
Colonne1 is A1+B1+C1,
Colonne2 is A2+B2+C2,
Diag0 is A0+B1+C2,
Diag1 is A2+B1+C0,
LigneA = LigneB, LigneB = LigneC,
LigneC = Colonne0,
Colonne0 = Colonne1, Colonne1 = Colonne2,
Colonne2 = Diag0,
Diag0 = Diag1.


/* Amélioration */

/* génère des valeurs différentes pour chaque variable */
valeurs([],_).
valeurs([X|R], D) :- member(X,D), enleve(X,D, Df), valeurs(R, Df).

enleve(_,[],[]).
enleve(X,[X|L],L) :- !.
enleve(X,[Y|L],[Y|L1]) :- enleve(X,L,L1).

carreA(S) :-
S = [ A0, A1, A2, B0, B1, B2, C0, C1, C2],
Domaine = [1, 2, 3, 4, 5, 6, 7, 8, 9],
/* génère des valeurs différentes pour chaque variable */
valeurs(S,Domaine),
/* puis teste */
LigneA is A0+A1+A2,
LigneB is B0+B1+B2,
LigneC is C0+C1+C2,
Colonne0 is A0+B0+C0,
Colonne1 is A1+B1+C1,
Colonne2 is A2+B2+C2,
Diag0 is A0+B1+C2,
Diag1 is A2+B1+C0,
LigneA = LigneB, LigneB = LigneC,
LigneC = Colonne0,
Colonne0 = Colonne1, Colonne1 = Colonne2,
Colonne2 = Diag0,
Diag0 = Diag1.

/* Backtrack */

carreB(S) :-
S = [ A0, A1, A2, B0, B1, B2, C0, C1, C2],
Domaine = [1, 2, 3, 4, 5, 6, 7, 8, 9],
/* On genere partiellement, on teste avec retour arrière si conflit */
member(A0, Domaine),
member(A1, Domaine), not(member(A1, [A0])),
member(A2, Domaine), not(member(A2, [A0, A1])),
LigneA is A0+A1+A2,
member(B0, Domaine), not(member(B0, [A0, A1, A2])),
member(B1, Domaine), not(member(B1, [A0, A1, A2, B0])),
member(B2, Domaine), not(member(B2, [A0, A1, A2, B0, B1])),
LigneB is B0+B1+B2,
LigneA == LigneB,
member(C0, Domaine), not(member(C0, [A0, A1, A2, B0, B1, B2])),
member(C1, Domaine), not(member(C1, [A0, A1, A2, B0, B1, B2, C0])),
member(C2, Domaine), not(member(C2, [A0, A1, A2, B0, B1, B2, C1])),
LigneC is C0+C1+C2,
LigneB == LigneC,
Colonne0 is A0+B0+C0,
Colonne1 is A1+B1+C1,
Colonne2 is A2+B2+C2,
Diag0 is A0+B1+C2,
Diag1 is A2+B1+C0,
LigneC == Colonne0,
Colonne0 == Colonne1,
Colonne1 == Colonne2,
Colonne2 == Diag0,
Diag0 == Diag1.

/* Filtrage sur les valeurs disponibles */
carreF(S) :-
S = [ A0, A1, A2, B0, B1, B2, C0, C1, C2],
Domaine = [1, 2, 3, 4, 5, 6, 7, 8, 9],
/* On genere partiellement, on teste avec retour arrière si conflit */
member(A0, Domaine),
enleve(A0,Domaine,Domaine1),
member(A1, Domaine1),
enleve(A1,Domaine1,Domaine2),
member(A2, Domaine2),
enleve(A2,Domaine2,Domaine3),
LigneA is A0+A1+A2,
member(B0, Domaine3),
enleve(B0,Domaine3,Domaine4),
member(B1, Domaine4),
enleve(B1,Domaine4,Domaine5),
member(B2, Domaine5),
enleve(B2,Domaine5,Domaine6),
LigneB is B0+B1+B2,
LigneA == LigneB,
member(C0, Domaine6),
enleve(C0,Domaine6,Domaine7),
member(C1, Domaine7), 
enleve(C1,Domaine7,Domaine8),
member(C2, Domaine8),
LigneC is C0+C1+C2,
LigneB = LigneC,
Colonne0 is A0+B0+C0,
Colonne1 is A1+B1+C1,
Colonne2 is A2+B2+C2,
Diag0 is A0+B1+C2,
Diag1 is A2+B1+C0,
LigneC = Colonne0,
Colonne0 = Colonne1,
Colonne1 = Colonne2,
Colonne2 = Diag0,
Diag0 = Diag1.

/* ?- carre(S).
S = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
S = [2, 9, 4, 7, 5, 3, 6, 1, 8] ;
S = [4, 3, 8, 9, 5, 1, 2, 7, 6] ;
S = [4, 9, 2, 3, 5, 7, 8, 1, 6] ;
S = [6, 1, 8, 7, 5, 3, 2, 9, 4] ;
S = [6, 7, 2, 1, 5, 9, 8, 3, 4] ;
S = [8, 1, 6, 3, 5, 7, 4, 9, 2] ;
S = [8, 3, 4, 1, 5, 9, 6, 7, 2] ;
false. */

/* Comparaison des temps 
?- time(carre(S)).
% 1,123,556,464 inferences, 60.881 CPU in 61.192 seconds (99% CPU, 18455102 Lips)
S = [2, 7, 6, 9, 5, 1, 4, 3, 8] .

?- time(carreA(S)).
% 1,328,464 inferences, 0.139 CPU in 0.140 seconds (99% CPU, 9544592 Lips)
S = [2, 7, 6, 9, 5, 1, 4, 3, 8] 

?- time(carreB(S)).
% 613,540 inferences, 0.053 CPU in 0.053 seconds (100% CPU, 11668695 Lips)
S = [2, 7, 6, 9, 5, 1, 4, 3, 8] .

?- time(carreF(S)).
% 95,519 inferences, 0.013 CPU in 0.014 seconds (96% CPU, 7238481 Lips)
S = [2, 7, 6, 9, 5, 1, 4, 3, 8] 

*/


/* Generalisation Carre(S,N) */

sommeListe([],0).
sommeListe([X|R], S) :- sommeListe(R, S2), S is S2+X.

sommeColonne([[]|_], []):-!.
sommeColonne(ListeLigne, [S|ListeRes]) :-
    findall(X, member([X|R], ListeLigne), PremiereCol),
    findall(R, member([X|R], ListeLigne), ResteCol),
    sommeListe(PremiereCol, S),
    sommeColonne(ResteCol, ListeRes).

raccourcirLigne(L1,0,L1):-!.
raccourcirLigne(L1,N,L2) :-
    append([P],R, L1),
    NN is N-1,
    raccourcirLigne(R,NN,L2) .

creerDiag1([], _, []).
creerDiag1([Ligne|ResteCarre], N, [P|LR]) :-
    raccourcirLigne(Ligne, N, Ligne2),
    append([P], R, Ligne2),
    M is N+1,
    creerDiag1(ResteCarre, M, LR).

creerDiag2([], _, []).
creerDiag2([Ligne|ResteCarre], N, [P|LR]) :-
    length(Ligne, L),
    LN is L-N-1,
    raccourcirLigne(Ligne, LN, Ligne2),
    append([P], R, Ligne2),
    M is N+1,
    creerDiag2(ResteCarre, M, LR).

sommeDiagonale(Carre, [D1,D2]) :-
    creerDiag1(Carre, 0, Diag1),
    creerDiag2(Carre, 0, Diag2),
    sommeListe(Diag1, D1),
    sommeListe(Diag2, D2).

tousIdentique([]).
tousIdentique([X]).
tousIdentique([X,X|R]) :- tousIdentique([X|R]).

/* ---- */

variables(1,[A0]).
variables(2,[A0,A1,B0,B1]).
variables(3,[A0,A1,A2,B0,B1,B2,C0,C1,C2]).
variables(4,[A0,A1,A2,A3,B0,B1,B2,B3,C0,C1,C2,C3,D0,D1,D2,D3]).

contraintes(1, _).

contraintes(2, [A0,A1,B0,B1]) :-
    LigneA = [A0,A1],
    LigneB = [B0,B1],
    sommeListe(LigneA,SA),
    sommeListe(LigneB,SB),
    sommeColonne([LigneA, LigneB], [Col0, Col1]),
    sommeDiagonale([LigneA, LigneB], [Diag0, Diag1]),  writeln,
    tousIdentique([SA, SB, Col0, Col1, Diag0, Diag1]).

contraintes(3, [A0,A1,A2,B0,B1,B2,C0,C1,C2]) :-
    LigneA = [A0,A1,A2],
    LigneB = [B0,B1,B2],
    LigneC = [C0,C1,C2],
    sommeListe(LigneA,SA),
    sommeListe(LigneB,SB),
    sommeListe(LigneC,SC),
    sommeColonne([LigneA, LigneB, LigneC], [Col0, Col1, Col2]),
    sommeDiagonale([LigneA, LigneB, LigneC], [Diag0, Diag1]),
    tousIdentique([SA, SB, SC, Col0, Col1, Col2, Diag0, Diag1]).

contraintes(4, [A0,A1,A2,A3,B0,B1,B2,B3,C0,C1,C2,C3,D0,D1,D2,D3]) :-
    LigneA = [A0,A1,A2,A3],
    LigneB = [B0,B1,B2,B3],
    LigneC = [C0,C1,C2,C3],
    LigneD = [D0,D1,D2,D3],
    sommeListe(LigneA,SA),
    sommeListe(LigneB,SB),
    sommeListe(LigneC,SC),
    sommeListe(LigneD,SD),
    sommeColonne([LigneA, LigneB, LigneC, LigneD], [Col0, Col1, Col2, Col3]),
    sommeDiagonale([LigneA, LigneB, LigneC, LigneD], [Diag0, Diag1]),
    tousIdentique([SA, SB, SC, SD, Col0, Col1, Col2, Col3, Diag0, Diag1]).

/* ---- */

nombres(1,[1]):-!.
nombres(N,[N|R]):- M is N-1, nombres(M,R).

choix(X, [X|R], R).
choix(X, [Y|Xs], [Y|Ys]):- choix(X, Xs, Ys).

affectation([], _).
affectation([V|Vs], Dom):- choix(V, Dom, NewDom), affectation(Vs, NewDom).

carre(LV,N) :-
    /* on va chercher les variables et leur domaine */
    variables(N, LV),
    Taille is N*N,
    nombres(Taille,Domaine),
    /* on genere */
    affectation(LV, Domaine),
    /* on teste */
    tousDifferent(LV),
    contraintes(N, LV).



/* csp(S) :-
    variableCSP(Lv), domaineCSP(Ld), affectationCSP(Lv, Ld), contraintesCSP(Lv).
*/