Probléme des N-reines.

Version imprimable

26/12/2012, 23h05
Masshat

Probléme des N-reines.

bonjour a vous, je debute sous prolog et j'ai un projet a réaliser sur le prb des N-reines.
j'ai lu kk tutoriel et je suis entrain de suivre la même methode que pour le sodoku, la Programmation Logique avec Contraintes (PLC).
j'ai déclare mes variables entre autre mon échiquier de la forme suivante:
echequier:[A1,A2,A3,A4,A5,A6,A7,A8,
B1,B2,B3,B4,B5,B6,B7,B8,
C1,C2,C3,C4,C5,C6,C7,C8,
D1,D2,D3,D4,D5,D6,D7,D8,
E1,E2,E3,E4,E5,E6,E7,E8,
F1,F2,F3,F4,F5,F6,F7,F8,
G1,G2,G3,G4,G5,G6,G7,G8,
H1,H2,H3,H4,H5,H6,H7,H8]
les lignes: (A-H) et les colonnes: (1-8),
pour la Définition des domaine je bloque je n'arrive pas a trouver kk chose, merci de votre attention.
27/12/2012, 09h37
Trap D

Pour ce type de problème, il y a beaucoup dee méthodes possibles, on peut en trouver beaucoup sur Internet.
Tel que vous êtes partis, vous pouvez définir 8 lignes de longueur 8, dire que les valeurs de chaque lignes sont prises dnas 0..1 et que la somme des lignes est 1.
On transpose les la matrice des lignes on obtient ainsi la matrice des colonnes, la somme des colonnes est 1.
"Il ne reste plus" qu'à écrire les contraintes sur les diagonales.
C'est une méthode possible.

bonjour,

Voici une proposition de solution adaptée de l'ouvrage : Prolog Programming for Artificial Intelligence que je suis en train de lire.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
solution([]).
solution([reine(X,Y)|Rs]):-
	solution(Rs),
	element(Y,[1,2,3,4,5,6,7,8]),
	nonattaque(reine(X,Y),Rs).
 
nonattaque(Reine,[]).
nonattaque(Reine,[R|Rs]):-
	nondiagouligne(Reine,R),
	nonattaque(Reine, Rs).
 
nondiagouligne(reine(I,J),reine(I1,J1)):-
	J \= J1,
	N1 is I+J1, N2 is I1+J,  N1 \= N2,
	N3 is I+J,  N4 is I1+J1, N3 \= N4.
 
element(X,[X|L]).
element(X,[Y|L]):-
	element(X,L).
 
soluce([reine(1,_),reine(2,_),reine(3,_),reine(4,_),reine(5,_),reine(6,_),reine(7,_),reine(8,_)]).
 
trouver(X) :-
	soluce(X),solution(X).
 
// dans l'interpreteur saisir : trouver(X).

Bon courage

04/02/2013, 21h09
CetTer

Une solution ("laborieuse mais qui marche") par clpfd est de définir un domaine entre 1 et 64 et faire correspondre chaque indice à une position X et Y via un prédicat qui ramène la position (1=(1 2), 9=(2 1), 64=(8 8) etc...).
Les contraintes (pas la même ligne, pas la même colonne, pas la diagonales) sont posées sur les positions retournées par ces prédicats.