I: Generate and Test
-------------------------------
On genere chaque combinaison possible, puis on verifie
pour chaque combinaison si les dames ne se menacent pas
respectivement.
Pour chaque ligne i, Xi represente la colonne ou placer la dame.
Ou, dit autrement, chaque dame est placee aux coordonnees (i,Xi).
Pour generer les permutations:
Pour verifier que les dames ne se menacent pas:
Les dames ne se menacent pas, si elles sont sur des colonnes
differentes (elles sont avec la representation d'une liste [X1,...,X8]
forcement sur des lignes differentes), et si elles ne sont pas sur
des diagonales:
On peut aussi utiliser une strategie de backtracking classique au lieu de
Generate and Test:
(La suite plus bas)
-------------------------------
On genere chaque combinaison possible, puis on verifie
pour chaque combinaison si les dames ne se menacent pas
respectivement.
Pour chaque ligne i, Xi represente la colonne ou placer la dame.
Ou, dit autrement, chaque dame est placee aux coordonnees (i,Xi).
Code:
eight_queens([X1,X2,X3,X4,X5,X6,X7,X8]) :-
permutation([X1,X2,X3,X4,X5,X6,X7,X8], [1,2,3,4,5,6,7,8]),
safe([X1,X2,X3,X4,X5,X6,X7,X8]).Pour generer les permutations:
Code:
permutation([],[]).
permutation([X|Xs], Ls) :-
delete(X,Ls,Rs),
permutation(Xs,Rs).
delete(X,[X|Xs],Xs).
delete(X,[Y|Ys],[Y|Rs]) :-
delete(X,Ys,Rs).Pour verifier que les dames ne se menacent pas:
Code:
safe([]).
safe([X|Xs]) :-
noattack(X,Xs),
safe(Xs).Les dames ne se menacent pas, si elles sont sur des colonnes
differentes (elles sont avec la representation d'une liste [X1,...,X8]
forcement sur des lignes differentes), et si elles ne sont pas sur
des diagonales:
Code:
noattack(X,Xs) :-
noattack(X,Xs,1).
noattack(X,[],Nb).
noattack(X,[Y|Ys],Nb) :-
X =\= Y - Nb,
X =\= Y + Nb,
Nb1 is Nb + 1,
noattack(X,Ys,Nb1).On peut aussi utiliser une strategie de backtracking classique au lieu de
Generate and Test:
Code:
eight_queens(X) :-
queens(X,[],[1,2,3,4,5,6,7,8]).
queens([],Placed,[]).
queens([X|Xs],Placed,Values) :-
delete(X,Values,New_values),
noattack(X,Placed),
queens(Xs,[X|Placed],New_values).(La suite plus bas)
