/* 1ère modelisation */

reines4_v1(Vars) :-
/* on déclare les variables */
Vars = [C1,C2,C3,C4,L1,L2,L3,L4],
/* le domaine de chaque variable est {1,2,3,4} */
member(C1, [1,2,3,4]),
member(C2, [1,2,3,4]),
member(C3, [1,2,3,4]),
member(C4, [1,2,3,4]),
member(L1, [1,2,3,4]),
member(L2, [1,2,3,4]),
member(L3, [1,2,3,4]),
member(L4, [1,2,3,4]),
/* Les reines doivent être sur des lignes différentes */
L1 =\= L2,
L1 =\= L3,
L1 =\= L4,
L2 =\= L3,
L2 =\= L4,
L3 =\= L4,
/* Les reines doivent être sur des colonnes différentes */
C1 =\= C2,
C1 =\= C3,
C1 =\= C4,
C2 =\= C3,
C2 =\= C4,
C3 =\= C4,
/* Les reines doivent être sur des diagonales montantes différentes */
C1+L1 =\= C2+L2, C1+L1 =\= C3+L3, C1+L1 =\= C4+L4,
C2+L2 =\= C3+L3, C2+L2 =\= C4+L4, C3+L3 =\= C4+L4,
/* Les reines doivent être sur des diagonales descendantes différentes */
C1-L1 =\= C2-L2, C1-L1 =\= C3-L3, C1-L1 =\= C4-L4,
C2-L2 =\= C3-L3, C2-L2 =\= C4-L4, C3-L3 =\= C4-L4.

/* 2eme modelisation */

reines4_v2(Vars) :-
/* on déclare les variables */
Vars = [L1,L2,L3,L4],
/* le domaine de chaque variable est {1,2,3,4} */
member(L1, [1,2,3,4]), member(L2, [1,2,3,4]),
member(L3, [1,2,3,4]), member(L4, [1,2,3,4]),
/* Les reines doivent être sur des lignes différentes */
L1 =\= L2, L1 =\= L3, L1 =\= L4, L2 =\= L3, L2 =\= L4, L3 =\= L4,
/* Les reines doivent être sur des diagonales montantes différentes */
L1+1 =\= L2+2, L1+1 =\= L3+3, L1+1 =\= L4+4,
L2+2 =\= L3+3, L2+2 =\= L4+4, L3+3 =\= L4+4,
/* Les reines doivent être sur des diagonales descendantes différentes */
L1-1 =\= L2-2, L1-1 =\= L3-3, L1-1 =\= L4-4,
L2-2 =\= L3-3, L2-2 =\= L4-4, L3-3 =\= L4-4.


/* Probleme des N reines */

/* solution_valable(Lc,N,Lr,S) Lc liste d'entiers donnée, N entier donné, Lr liste de reines donnée,
S liste de reines résultat */
solution_valable([],_,_,[]).
solution_valable(ColonnesPossibles,N,LreinesDejaAffectees,[reine(N,Colonne)|S]) :-
member(Colonne,ColonnesPossibles),
non_prise(reine(N,Colonne), LreinesDejaAffectees),
enleve(Colonne,ColonnesPossibles,ColonnesPossiblesRestantes),
M is N+1,
solution_valable(ColonnesPossiblesRestantes,M,[reine(N,Colonne)|LreinesDejaAffectees],S).

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

/* predicats donnes */
/* solution(N,S) N entier positif donné, S liste de reines résultat */
solution(N,Lreines) :- nombres(N,L), solution_valable(L,1,[],Lreines).

nombres(1,[1]):-!.
nombres(N,[N|R]):- M is N-1, nombres(M,R).
/* ou version avec arg supp pour les avoir dans l'ordre croissant */


non_diag(reine(X1,Y1), reine(X2,Y2)) :- abs(X1-X2) =\= abs(Y1-Y2).

non_prise(_,[]).
non_prise(Reine, [X|Reste]) :- non_diag(Reine,X), non_prise(Reine,Reste).