Discussion :

[bazoga]

Bonjour,

j'ai realisé un programme en prolog qui permer de placer N reines sur un echiquier de N*N sans qu'elles soient en prise les unes avec les autres, je veux etendre le programme pour placer N pieces qui ont le pouvoir de la reine et du cavalier, j'ai résolu ce probleme en utilisant purement prolog mais j'ai du mal à le resoudre en utilisant la programmation par contraintes (clpfd)
merci de m'aider :

voici le programme qui permet de placer N reines en utilisant les librairies clpfd

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
:-use_module(library(clpfd)).
 
reine_clp(N,Sol):-
       length(Sol,N),
       domain(Sol,1,N),
       clp_contraintes(1,Sol),
       labeling([],Sol).
 
 
/************** test de contraintes*********************/
 
clp_contraintes(_,[]).
clp_contraintes(I,[Xi|L]):-	
	Iplus1 is I+1,
	clp_contraintesXi(Xi,I,Iplus1,L),
	lp_contraintes(Iplus1,L).
 
clp_contraintesXi(_,_,_,[]).
 
clp_contraintesXi(Xi,I,J,[Xj|L]):- 
	Xi #\= Xj,
       	Xi+I #\= Xj+J,
	I-Xi  #\= J-Xj,
	Js is J+1,
	clp_contraintesXi(Xi,I,Js,L).
 
/***********************************************/

j'ai essayé d'ajouter le predicat ci dessous dans clp_contrainesXi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
test_prise_cavalier1(Xi,I,J,Xj):-
	(abs(Xi-Xj) #\= 1 ; abs(I-J)#\= 2),
	(abs(Xi-Xj) #\= 2 ; abs(I-J)#\= 1).

qui assure que les deux cases [I,Xi] et [J,Xj] ne sont pas en prise.

le programme entre dans une boucle infini

merci de m'aider svp

cordialement

[Trap D]

Une amélioration intéressante de conception est de séparer la phase de création des contraintes de la phase de labelling :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
reine_clp(N,Sol):-
       length(Sol,N),
       Sol ins 1..N,
       clp_contraintes(1,Sol).
 
 
reine(N, Sol) :-
	reine_clp(N,Sol),
	labeling([],Sol).

Ainsi tu peux voir si lorsque tu décris tes contraintes tu obtiens un problème "bien posé", c'est à dire qu'il ne donnes pas lieu à une multiplicité de solutions.
C'est très net en ce qui te concerne :
Sans ton ajout de test_prise_cavalier1(Xi,I,J,Xj):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
6 ?- reine_clp(4,Sol).
Sol = [_G9055, _G9058, _G9061, _G9064],
_G9055 in 1..4,
_G9064#\=_G9055+3,
_G9055#\=_G9064+3,
_G9055#\=_G9064,
_G9061#\=_G9055+2,
_G9055#\=_G9061+2,
_G9055#\=_G9061,
_G9058#\=_G9055+1,
_G9055#\=_G9058+1,
_G9055#\=_G9058,
_G9058 in 1..4,
_G9064#\=_G9058+2,
_G9058#\=_G9064+2,
_G9058#\=_G9064,
_G9061#\=_G9058+1,
_G9058#\=_G9061+1,
_G9058#\=_G9061,
_G9061 in 1..4,
_G9064#\=_G9061+1,
_G9061#\=_G9064+1,
_G9061#\=_G9064,
_G9064 in 1..4 ;
false.
 
7 ?-

Avec l'ajout de test_prise_cavalier1(Xi,I,J,Xj):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
7 ?- reine_clp(4,Sol).
Sol = [_G10279, _G10282, _G10285, _G10288],
_G10279 in 1..4,
abs(_G10279-_G10288)#\=2,
abs(_G10279-_G10288)#\=1,
_G10288#\=_G10279+3,
_G10279#\=_G10288+3,
_G10279#\=_G10288,
abs(_G10279-_G10285)#\=2,
abs(_G10279-_G10285)#\=1,
_G10285#\=_G10279+2,
_G10279#\=_G10285+2,
_G10279#\=_G10285,
abs(_G10279-_G10282)#\=2,
abs(_G10279-_G10282)#\=1,
_G10282#\=_G10279+1,
_G10279#\=_G10282+1,
_G10279#\=_G10282,
_G10282 in 1..4,
abs(_G10282-_G10288)#\=2,
abs(_G10282-_G10288)#\=1,
_G10288#\=_G10282+2,
_G10282#\=_G10288+2,
_G10282#\=_G10288,
abs(_G10282-_G10285)#\=2,
abs(_G10282-_G10285)#\=1,
_G10285#\=_G10282+1,
_G10282#\=_G10285+1,
_G10282#\=_G10285,
_G10285 in 1..4,
abs(_G10285-_G10288)#\=2,
abs(_G10285-_G10288)#\=1,
_G10288#\=_G10285+1,
_G10285#\=_G10288+1,
_G10285#\=_G10288,
_G10288 in 1..4 ;
Sol = [_G10451, _G10454, _G10457, _G10460],
_G10451 in 1..4,
abs(_G10451-_G10460)#\=2,
abs(_G10451-_G10460)#\=1,
_G10460#\=_G10451+3,
_G10451#\=_G10460+3,
_G10451#\=_G10460,
abs(_G10451-_G10457)#\=2,
abs(_G10451-_G10457)#\=1,
_G10457#\=_G10451+2,
_G10451#\=_G10457+2,
_G10451#\=_G10457,
abs(_G10451-_G10454)#\=2,
abs(_G10451-_G10454)#\=1,
_G10454#\=_G10451+1,
_G10451#\=_G10454+1,
_G10451#\=_G10454,

Et il y en a des pages et des pages comme ça !
Il faut réfléchir à comment améliorer ton test.

PS : c'est juste, un conseil, pour le moment je ne vois pas comment faire

[bazoga]

Merci TrapD pour le conseil

j'ai pensé à passer par la negation pour eviter le ou, le resultat n'est pas une boucle infinie mais malheureusement no

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
en_prise_caval([I,Xi],[J,Xj]):-
  abs(Xi-Xj) #= 1,
  abs(I-J) #= 2.
 
en_prise_caval([I,Xi],[J,Xj]):-
  abs(Xi-Xj) #= 2,
  abs(I-J) #= 1.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
constraintXi(_,[]):- !.
constraintXi([I,Xi],[[J,Xj]|L]):-
    I #\= J,
    Xi #\= Xj,
    I-J #\= Xi-Xj,
    I-J #\= Xj-Xi,
\+ en_prise_caval([I,Xi],[J,Xj]),
    constraintXi([I,Xi],L).

j'ai pas compris pourquoi j'ai un tel resultat

merci de m'aider à resoudre ce probleme

[Trap D]

Ton problème a des solutions à partir de quelle dimension d'échiquier ?
Je viens de trouver qu'il avait des solutions à partir de 10

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
9 ?- reine(10, S).
S = [3, 6, 9, 1, 4, 7, 10, 2, 5, 8] ;
S = [4, 8, 1, 5, 9, 2, 6, 10, 3, 7] ;
S = [7, 3, 10, 6, 2, 9, 5, 1, 8, 4] ;
S = [8, 5, 2, 10, 7, 4, 1, 9, 6, 3] ;

Il faut que tu sépares les contraintes sur le mouvement ses cavaliers des contraintes sur le mouvement des reines.

[bazoga]

Merci pour votre aide, votre remarque est precieuse, en fait j'ai séparé les contraintes et j'ai amelioré le test sur le cavalier comme suit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
constraint_one_c(_,[]):- !.
constraint_one_c([I,Xi],[[J,Xj]|L]):- 
            			(abs(I-J) #>2 ; abs(Xi-Xj) #>2),!,
			 constraint_one_c([I,Xi],L).
 
constraint_one_c([I,Xi],[[J,Xj]|L]):-
			test_prise_caval1([I,Xi],[J,Xj]),				             test_prise_caval2([I,Xi],[J,Xj]),					constraint_one_c([I,Xi],L).
 
la solution est à partir d'un echiquier de 10*10

un grand merci pour vous.