/*-------------------------------------*/
	           /*   LE PROBLEME DES HUIT REINES       */
                   /*-------------------------------------*/



reines(L):-
	placer(L,1,[],[1,2,3,4,5,6,7,8]).

/*----------------------------------------------------------------------*/
/* placer(Resultat,Ligne,Deja_placees, A_placer) signifie  que la liste */
/* Resultat est la liste des colonnes deja placees jusqu'a la ligne     */
/* Ligne, Deja_placees est la liste des diagonales correspondantes      */
/* aux couples(ligne,colonne) deja choisis ([] a l'appel), A_placer est */
/* la liste des colonnes encore a placer ([1,2,3,4,5,6,7,8] a l'appel). */
/*----------------------------------------------------------------------*/
/* regle d'arret (quand on est a la neuvieme ligne) */
placer([],9,_,[]).
placer([Colonne|Reste],Ligne,Deja_placees,A_placer):-
    retirer(Colonne,A_placer,Encore_a_mettre),
    Diag1 is Ligne + Colonne,
    Diag2 is Ligne - Colonne,
    verifier(Diag1,Diag2,Deja_placees),
    Nouvelle_ligne is Ligne + 1,
    placer(Reste,Nouvelle_ligne,[[Diag1,Diag2]|Deja_placees],Encore_a_mettre).


retirer(J,[J|L],L).
retirer(J,[K|L],[K|M]):- retirer(J,L,M).

verifier(_,_,[]).
verifier(D1,D2,[[X,Y]|Autre]):- D1 \== X,
                                D2 \== Y,
				verifier(D1,D2,Autre).
				



/* exemple |?- reines(L)            */
/*          L=[1,5,8,6,3,7,2,4] */