Un solveur de logigram en Prolog

**Samildanach** · 22/10/2007, 17h11

bonjour à tous, alors mon projet est décrit dans le titre. Bon c'est très interessant et ça commence même à marcher mais j'ai un petit problème : en fait pour l'instant je travail sur un logigram facile avec comme conditions
Fernand est plus âgé que Luc.
Celui qui joue au jeu C a juste 7 ans.
Paul qui n'est pas le plus jeune joue au jeu A.

simple 3 personnes, 3 jeux et 3 âges.
mon problème vient de la première condition que je n'arrive pas à représenter, du coup prolog me renvoit 2 solutions alors qu'il n'y en a qu'une ...

voilà mon code :

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
app(X, [X | _]).
app(X, [_ | L]) :- app(X, L).
 
ret(X, [X|L], L).
ret(X, [Y|L], [Y| R]) :- ret(X, L, R).
 
assoc(U, V, U, V). % en fait la seconde clause est inutile
assoc(X, Y, U, V) :- X \== U, Y \== V.
 
sup(X, Y) :- X > Y.
 
superieur(X,Y,[ass(I, A, J) | LR]) :- X == fernand, I == luc, Y > A.
superieur(X,Y,[ass(I, A, J) | LR]) :- X == luc, I == fernand, Y < A.
superieur(X,Y,[ass(I, A, J) | LR]) :- superieur(X,Y,LR).
 
imp(U, V, U, V) :- !, fail.
imp(_, _, _, _).
%Autre solution assoc(X, Y, A, B) :- (X == A, Y == B); (X \== A, Y \== B).
%imp(X, Y, A, B) :- X \== A ; Y \== B.
 
 
donnees([ass(luc, _, _),ass(paul, _, jeuA),  ass(fernand, _, _)]).
jeu(D) :- donnees(D), assigner(D, [5, 7, 9], [jeuA, jeuB, jeuC]).
assigner([], _, _).
assigner([ass(I, A, J) | LR], LA, LJ) :- app(A, LA), 
                                                   app(J, LJ),
                                                   assoc(J, A, jeuC, 7),	
                                                   imp(I, A, paul, 5),
                                                   imp(I, A, luc, 9),
                                                   ret(A, LA, LAR),
                                                   ret(J, LJ, LJR), 
                                                   assigner(LR, LAR, LJR).

j'ai crée le prédicat supérieur mais il ne marche pas

Merki d'avance pour toute aide

**Trap D** · 22/10/2007, 23h17

Salut

Inspire-toi de ce post http://www.developpez.net/forums/showthread.php?t=25494

**Samildanach** · 23/10/2007, 14h30

Oui j'avais déjà vu, mais en fait ce que je remarque c'est qu'il est difficile de créer un algo générique, mon problème vient juste de la notion d'ordre, je ne vois pas le moyen de représenter le fait que fernand est plus age que luc, dans la page que tu m'a envoye on a une notion de voisinage facilement traduite, mais c'est peut etre la facon dont j'ai represente mes donnees qui n'est pas bonne, je vais continuer à reflechir en esperant que quelqu'un ait une bonne idee

**Trap D** · 23/10/2007, 17h55

Tu as tout à fait raison, c'est une question de formalisation :
J'ai formalisé en définissant une base de données pour les ages

Code :

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

1
2
3
age(5).
age(7).
age(9).

Je définis une triplé personne(Nom, Age, Jeu) et j'ai comme obligation lorsque j'utilise le triplé personne d'avoir age(Age).
Par exemple lorsque tu dis que "Fernand est plus âgé que Luc." tu peux traduire celà par

Code :

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

1
2
3
4
5
6
7
8
9
% j'utilise le triplé fernand (on n'a pas besoin de la variable JeuF
personne(fernand, AgeF, _JeuF),
% idem pour le triplé luc
personne(luc, AgeL, _JeuL),
% les ages sont des éléments de la base de données "age"
age(AgeF),
age(AgeL),
% L'age de luc est inférieur à l'âge de fernand
AgeL < AgeF.

**Samildanach** · 23/10/2007, 18h00

Ben merki de ton aide je vais essayer cela et je te dis si ca marche

**Trap D** · 23/10/2007, 18h27

Ça doit marcher puisque j'ai réussi à résoudre ton problème comme ça

**Samildanach** · 23/10/2007, 18h29

t'as reussi a resoudre tout le problème ???
Parce qu'en fait après je voudrais que cet algo soit assez générique pour pouvoir l'appliquer à différents logigrams héhé

Fais voir un peu ton code, j'essaye de modifier le mien mais il me fait un peu de la *****

en fait j'arrive pas trop a voir comment gerer le truc avec une base d'age et une base de jeu et de personne

**Trap D** · 23/10/2007, 18h57

Je te renvoie à mon premier post. Cherche un peu d'abord.
Tu as tous les éléments pour le faire.

**Samildanach** · 23/10/2007, 19h47

Bon j'ai tenté avec la structure de ton code, ce qui me donne

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
age(5).
age(7).
age(9).
 
jeu(jeuA).
jeu(jeuB).
jeu(jeuC).
 
personne(paul,AgeP, _JeuP).
personne(luc,AgeL, _JeuL).
personne(fernand, AgeF, _JeuF).
 
donnee(personne, H, [H, A, J]).
donnee(age, A, [H, A, J]).
donnee(jeu, J, [H, A, J]).
 
element_de(X, L) :- member(X, L).
 
probleme(L) :-	
	age(AgeL),
	age(AgeF),
	age(AgeP),
	AgeP > 5,
	AgeL < 9,
	AgeL < AgeF,
	element_de(E1, L),
		donnee(age, 7, E1),
		donnee(jeu, jeuC, E1),
 
	element_de(E2, L),
		donnee(personne, paul, E2),
		donnee(jeu, jeuA, E2),
 
	element_de(E3,L),
		donnee(personne,luc,E3),
 
	element_de(E4,L),
		donnee(personne, fernand,E4),
 
	element_de(E5,L),
		donnee(jeu, jeuB,E5),
 
	element_de(E6,L),
		donnee(age, 5, E6),
 
	element_de(E7,L),
		donnee(age, 9, E7)
 
	.

Et prolog me renvoie une solution
H1 = luc,
A1 = 7,
J1 = jeuC,
H2 = paul,
A2 = 5,
J2 = jeuA,
H3 = fernand,
A3 = 9,
J3 = jeuB

mais celle ci n'est pas bonne, et ca vient bien des ages, le test n'a pas l'air d'etre pris en compte, je m'y replonge mais j'ai un peu de al a voir comment marche ton code en fait

**Samildanach** · 23/10/2007, 20h45

non je vois vraiment pas la, je comprend pas la logique de ton programme tant pis pour moi

**Samildanach** · 24/10/2007, 13h44

Tu veux vraiment pas m'expliquer

**Trap D** · 24/10/2007, 18h39

C'est mon jour de bonté

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
% la base de données
% l'accesseur pour le nom
nom(personne(Nom, _Age, _Jeu), Nom).
 
% les jeux
jeu(jeuA).
jeu(jeuB).
jeu(jeuC).
jeu(personne(_Nom, _Age, Jeu), Jeu).
 
% les ages
age(5).
age(7).
age(9).
age(personne(_Nom, Age, _Jeu), Age).
 
% la base de règles
% 
% règle 1
% "fernand est plus agé que luc"
regle1(X, Y) :-
	nom(X, fernand),
	age(X, AgeF),
	age(AgeF),
	% Y = personne(luc, AgeL, _),
	nom(Y, luc),
	age(Y, AgeL),
	age(AgeL),
	AgeF > AgeL.
 
% règle 2
% "Celui qui joue au jeu C à juste 7 ans
regle2(X) :-
	age(X, 7),
	jeu(X, jeuC).
 
% règle 3
% Paul joue au jeu A
regle3(X) :-
	nom(X,paul),
	jeu(X, jeuA).
 
% règle 4
% Paul n'est pas le plus jeune
regle4(X, Y, Z) :-
	nom(X, paul),
	age(X,AgeP),
	nom(Y, luc),
	age(Y, AgeL),
	nom(Z, fernand),
	age(Z, AgeF),
	age(AgeF), age(AgeL), age(AgeP),	
	(   AgeL < AgeP; AgeF < AgeP).
 
% regle 5 (implicite)
% Les enfants ont des jeux différents
regle5(X, Y, Z) :-
	nom(X ,paul),
	jeu(X, JeuP),
	nom(Y, luc),
	jeu(Y, JeuL),
	nom(Z, fernand),
	jeu(Z, JeuF),
	jeu(JeuP), jeu(JeuL), jeu(JeuF),
	JeuP \= JeuL,
	jeuL \= JeuF,
	JeuF \= JeuP.
 
%regle 6 (implicite)
% les enfants ont des âges différents
regle6(X, Y, Z) :-
	nom(X ,paul),
	age(X, AgeP),
	nom(Y, luc),
	age(Y, AgeL),
	nom(Z, fernand),
	age(Z, AgeF),
	age(AgeP), age(AgeL), age(AgeF),
	AgeP \= AgeL,
	AgeL \= AgeF,
	AgeF \= AgeP.
 
element_de(E, L) :-
	member(E, L).
 
go :-
	L = [X, Y, Z],
	element_de(E1, L),
	element_de(E2, L),
	regle1(E1, E2),
 
	element_de(E3, L),
	regle2(E3),
 
	element_de(E4, L),
	regle3(E4),
 
	element_de(E5, L),
	element_de(E6, L),
	element_de(E7, L),
	regle4(E5, E6, E7),
 
	element_de(E8, L),
	element_de(E9, L),
	element_de(E10, L),
	regle5(E8, E9, E10),
 
	regle6(E8, E9, E10),
 
	writeln(X),
	writeln(Y),
	writeln(Z).

Pose des questions si tu ne comprends pas.

**Samildanach** · 24/10/2007, 20h23

Oki merki t'es un chef, je regarde ca de plus près, et t'inquiete pas si j'ai des questions je les poserai

merki encore

**Samildanach** · 24/10/2007, 21h54

Ben c'est cool ca marche très bien, à part qu'il arrive à trouver plusieurs solutions malgré les contraintes ce qui est bizarre. Ce que je ne comprend pas en fait dans l'algo c'est pourquoi tu fais element_de et après tu mets les règles, même en traçant je ne comprend pas trop le raisonnement

encore merki

**Trap D** · 25/10/2007, 08h25

Il ne trouve qu'une seule solutio, c'est toujours la même qui ressort, celà est du au backtrack.

**Samildanach** · 27/10/2007, 14h43

Ben je te remercie de ton aide, j'ai reussi a adapter l'algo a differents logigrams donc c'est cool

Merki encore de m'avoir aider

**vicnet** · 29/07/2010, 13h48

Envoyé par Trap D

Code :

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

1
2
3
4
5
% les ages
age(5).
age(7).
age(9).
age(personne(_Nom, Age, _Jeu), Age).

Pose des questions si tu ne comprends pas.

Pourquoi ne pas avoir mis une regle sur le dernier prédicat pour forcer le fait que Age doit être un age, du style

Code :

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

age(personne(_Nom, Age, _Jeu), Age) :- age(Age).

?
Est-ce que cela ne simplifierait pas l'écriture des regles en évitant de vérifier que l'Age récupéré sur X est bien un age.

a+
Vicnet

**vicnet** · 29/07/2010, 14h53

Ah aussi, dans la regle 5, il est écrit:

Code :

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

jeuL \= JeuF,

alors qu'il faudrait:

JeuL \= JeuF,

avec une majuscule à jeuL

Sinon il trouve plusieurs solution avec le même jeux partagé par plusieurs !

De toutes façons, swi-prolog trouve bizarement plusieurs solutions identiques !
Surement une histoire de backtrack qui fait qu'il arrive au même endroit par différents chemins ?

Un cut après la dernière regle du go résoud évidement le pb...

a+
Vicnet

**laurentcp** · 01/12/2021, 18h00

Envoyé par Samildanach

bonjour à tous, alors mon projet est décrit dans le titre. Bon c'est très interessant et ça commence même à marcher mais j'ai un petit problème : en fait pour l'instant je travail sur un logigram facile avec comme conditions
Fernand est plus âgé que Luc.
Celui qui joue au jeu C a juste 7 ans.
Paul qui n'est pas le plus jeune joue au jeu A.

simple 3 personnes, 3 jeux et 3 âges.

Voici une solution, qui me semble plus claire et plus simple.
J'ai souhaité la réaliser sans utiliser de listes, ni de prédicats Prolog prédéfinis.
Ce ne fut pas si simple à coder, la règle Celui qui joue au jeu C a juste 7 ans m'a posé quelques problèmes et j'ai dû revoir la règle resoudre/3 et ajouter le prédicat joue/3.

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
 
%! Domaine des âges
age(5).
age(7).
age(9).
 
%! Domaine des jeux
jeu(jeuA).
jeu(jeuB).
jeu(jeuC).
 
% Celui qui joue au jeu C a juste 7 ans.
joue((jeuC, 7), _, _).
joue(_, (jeuC, 7), _).
joue(_, _, (jeuC, 7)).
 
% le prédicat different est vrai seulement si ses 3 paramètres sont différents :
different(X,Y,Z) :- X \== Y, X \== Z, Y \== Z.
 
resoudre((fernand, AF, JF), (luc, AL, JL), (paul, AP, JP)) :-
  age(AF), age(AL), age(AP),
  %! Paul qui n'est pas le plus jeune joue au jeu A.
  AP > 5, jeuA = JP,
  %! Fernand est plus âgé que Luc
  AF > AL,
  %! Tous les âges sont différents
  different(AF, AL, AP),
  jeu(JF), jeu(JL),
  %! Tous les jeux sont différents
  different(JF, JL, JP),
  %! L'une des paires (jeu, âge) est (jeuC, 7).
  joue((JF,AF), (JL,AL), (JP,AP)).
 
%! Et la recherche de solutions
?- resoudre(A,B,C).
A =  (fernand, 7, jeuC),
B =  (luc, 5, jeuB),
C =  (paul, 9, jeuA) ;
false.
 
%! La solution est unique.

**Trap D** · 01/12/2021, 18h08

Le P.O. attendait ta solution avec impatience !

Un solveur de logigram en Prolog

Prolog

Discussions similaires

Partager

Partager