problème de la traversée du prof layton

**GrosseBuse** · 10/06/2011, 15h47

J'ai fait un programme en swi prolog pour résoudre le problème de la traversée du professeur Layton mais ça ne marche pas (retourne false
pour le but ?- traverse(rive(3, 3), rive(0, 0), true, 12).

1. Pourquoi ?
2. Comment optimiser ou faire un programe plus concis ?

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
%------------------- ICI LE LISTING A COPIER COLLER
%problème de la traversée du professeur Layton et l'étrange village sur Nintendo DS
%le but du problème est d'amener 3 poussins et 3 loups d'une rive A à une rive B
%on ne peut déplacer que 2 animaux à la fois
%les loups ne doivent pas être supérieurs aux poussins en nombre sur aucune rive
%on ne peut déplacer la barque sans animaux dedans
%une solution existe en 11 coups
 
%ce programme en PROLOG a été écrit en SWI-PROLOG
 
%traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true, PMOV)
%=>rive(LOUPS1, POUSSINS1) : la rive A avec son nombre de poussins et son nombre de loups
%=>rive(LOUPS2, POUSSINS2) : la rive B avec son nombre de poussins et son nombre de loups
%=>true : on déplace les animaux de la rive A à la rive B, false pour l'inverse 
%=>PMOV : le nombre de coups restant, décrémenté jusqu'à 0
%ATTENTION si une solution est générée, elle se lit en commençant par la fin et en remontant 
%jusqu'au début
 
debug(_,_,_,_).
%debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, ACT) :-
%	write(PMOV), write(':'),write(ACT),write('#('), write(LOUPS1), write(','), write(POUSSINS1), write(')-('),
%	write(LOUPS2), write(','), write(POUSSINS2), writeln(')').
 
%les loups sur l'une des rive données peuvent ils prendrent des poussins ?
%=>oui si ils sont plus nombreux et qu'il y a au moins un poussin
prise(rive(LOUPS, POUSSINS)) :-
	POUSSINS > 0,
	LOUPS > POUSSINS.
 
%pour chaque clause traverse on test si aucune prise n'est possible et si on a pas atteint
%le nombre maximal de coups : ce prédicat est présent dans chaque clause du prédicat "traverse"
constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV) :-
	not(prise(rive(LOUPS1, POUSSINS1))),
	not(prise(rive(LOUPS2, POUSSINS2))),
	PMOV >= 0.
 
%clause de réussite : tous les animaux sont passés de la rive A à la rive B
traverse(rive(0, 0), rive(3, 3), _, _).
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	LOUPS1 >= 1, %traversée de 1 loup de rive A vers B
	ZLOUPS1 is LOUPS1 - 1, ZLOUPS2 is LOUPS2 + 1,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '1L->'),
	traverse(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), false, ZMOV),
	write(PMOV), writeln(':1L->').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	LOUPS1 >= 2, %traversée de 2 loups de rive A vers B
	ZLOUPS1 is LOUPS1 - 2, ZLOUPS2 is LOUPS2 + 2,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '2L->'),
	traverse(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), false, ZMOV),
	write(PMOV), writeln(':2L->').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	POUSSINS1 >= 1, %traversée de 1 poussin de rive A vers B
	ZPOUSSINS1 is POUSSINS1 - 1, ZPOUSSINS2 is POUSSINS2 + 1,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '1P->'),
	traverse(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), false, ZMOV),
	write(PMOV), writeln(':1P->').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	POUSSINS1 >= 2, %traversée de 2 poussins de rive A vers B
	ZPOUSSINS1 is POUSSINS1 - 2, ZPOUSSINS2 is POUSSINS2 + 2,
	ZMOV is PMOV - 1, 
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '2P->'),
	traverse(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), false, ZMOV),
	write(PMOV), writeln(':2P->').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	POUSSINS1 >= 1, %traversée de 1 poussin et 1 loup de rive A vers B
	LOUPS1 >= 1,
	ZPOUSSINS1 is POUSSINS1 - 1, ZPOUSSINS2 is POUSSINS2 + 1,
	ZLOUPS1 is LOUPS1 - 1, ZLOUPS2 is LOUPS2 + 1,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '1L1P->'),
	traverse(rive(ZLOUPS1, ZPOUSSINS1), rive(ZLOUPS2, ZPOUSSINS2), false, ZMOV),
	write(PMOV), writeln(':1L1P->').
 
%les clauses qui suivent sont pour la traversée de la rive B vers la rive A
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	LOUPS2 >= 1,
	ZLOUPS1 is LOUPS1 + 1, ZLOUPS2 is LOUPS2 - 1,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '<-1L'),
	traverse(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), true, ZMOV),
	write(PMOV), writeln(':<-1L').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	LOUPS2 >= 2,
	ZLOUPS1 is LOUPS1 + 2, ZLOUPS2 is LOUPS2 - 2,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '<-2L'),
	traverse(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), true, ZMOV),
	write(PMOV), writeln(':<-2L').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	POUSSINS2 >= 1,
	ZPOUSSINS1 is POUSSINS1 + 1, ZPOUSSINS2 is POUSSINS1 - 1,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '<-1P'),
	traverse(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), true, ZMOV),
	write(PMOV), writeln(':<-1P').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	POUSSINS2 >= 2,
	ZPOUSSINS1 is POUSSINS1 + 2, ZPOUSSINS2 is POUSSINS1 - 2,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '<-2P'),
	traverse(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), true, ZMOV),
	write(PMOV), writeln(':<-2P').
 
traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false, PMOV) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
	POUSSINS2 >= 1,
	LOUPS2 >= 1,
	ZLOUPS1 is LOUPS1 + 1, ZLOUPS2 is LOUPS2 - 1,
	ZPOUSSINS1 is POUSSINS1 + 1, ZPOUSSINS2 is POUSSINS1 - 1,
	ZMOV is PMOV - 1,
	debug(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, '<-1L1P'),
	traverse(rive(ZLOUPS1, ZPOUSSINS1), rive(ZLOUPS2, ZPOUSSINS2), true, ZMOV),
	write(PMOV), writeln(':<-1L1P').
 
%ici c'est le but en 12 coups max :
%?- traverse(rive(3, 3), rive(0, 0), true, 12).

**Trap D** · 11/06/2011, 11h42

Bonjour
J'avoue que je n'ai pas regardé ton programme en détail

Pour ce qui est de la méthode et de trouver le chemin le plus court, tu devrais utiliser la recherche en largeur qui t'assure de trouver le chemin le plus court mais pas forcément le plus rapidement !
Tu as deux squelettes de recherche sur ma page perso, (le probleme de partage, ou l'ane rouge).
Tu n'as qu'a écrire ce qui correspond exactement à ton problème !

**GrosseBuse** · 12/06/2011, 14h55

Finalement j'ai résolu le problème

merci de vous être tous précipités pour me sauver

listing :

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
113
114
115
116
117
118
119
120
121
122
 
%problème de la traversée du professeur Layton et l'étrange village sur Nintendo DS
%le but du problème est d'amener 3 poussins et 3 loups d'une rive A à une rive B
%on ne peut déplacer que 2 animaux à la fois
%les loups ne doivent pas être supérieurs aux poussins en nombre sur aucune rive
%on ne peut déplacer la barque sans animaux dedans
%une solution existe en 11 coups
 
%ce programme en PROLOG a été écrit en SWI-PROLOG
 
%traverse(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV)
%=>rive(LOUPS1, POUSSINS1) : la rive A avec son nombre de poussins et son nombre de loups
%=>rive(LOUPS2, POUSSINS2) : la rive B avec son nombre de poussins et son nombre de loups
%=>PMOV : le nombre de coups restant, décrémenté jusqu'à 0
 
%les loups sur l'une des rive données peuvent ils prendrent des poussins ?
%=> oui si ils sont plus nombreux et qu'il y a au moins un poussin
prise(rive(LOUPS, POUSSINS)) :-
    POUSSINS > 0,
    LOUPS > POUSSINS.
 
%pour chaque clause traverse on test si aucune prise n'est possible et si on a pas atteint
%le nombre maximal de coups : ce prédicat est présent dans chaque clause du prédicat "traverse"
constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV) :-
    not(prise(rive(LOUPS1, POUSSINS1))),
    not(prise(rive(LOUPS2, POUSSINS2))),
    PMOV >= 0.
 
%clause de réussite : tous les animaux sont passés de la rive A à la rive B
traverseBA(rive(0, 0), rive(3, 3), _, []) :- !.
 
traverseAB(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    LOUPS1 >= 1, %traversée de 1 loup de rive A vers B
    ZLOUPS1 is LOUPS1 - 1, ZLOUPS2 is LOUPS2 + 1,
    ZMOV is PMOV - 1,
    traverseBA(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), ZMOV, R2),
    R = ['1L->'|R2].
 
traverseAB(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    LOUPS1 >= 2, %traversée de 2 loups de rive A vers B
    ZLOUPS1 is LOUPS1 - 2, ZLOUPS2 is LOUPS2 + 2,
    ZMOV is PMOV - 1,
    traverseBA(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), ZMOV, R2),
    R = ['2L->'|R2].
 
traverseAB(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    POUSSINS1 >= 1, %traversée de 1 poussin de rive A vers B
    ZPOUSSINS1 is POUSSINS1 - 1, ZPOUSSINS2 is POUSSINS2 + 1,
    ZMOV is PMOV - 1,
    traverseBA(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), ZMOV, R2),
    R = ['1P->'|R2].
 
traverseAB(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    POUSSINS1 >= 2, %traversée de 2 poussins de rive A vers B
    ZPOUSSINS1 is POUSSINS1 - 2, ZPOUSSINS2 is POUSSINS2 + 2,
    ZMOV is PMOV - 1, 
    traverseBA(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), ZMOV, R2),
    R = ['2P->'|R2].
 
traverseAB(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    POUSSINS1 >= 1, %traversée de 1 poussin et 1 loup de rive A vers B
    LOUPS1 >= 1,
    ZPOUSSINS1 is POUSSINS1 - 1, ZPOUSSINS2 is POUSSINS2 + 1,
    ZLOUPS1 is LOUPS1 - 1, ZLOUPS2 is LOUPS2 + 1,
    ZMOV is PMOV - 1,
    traverseBA(rive(ZLOUPS1, ZPOUSSINS1), rive(ZLOUPS2, ZPOUSSINS2), ZMOV, R2),
    R = ['1L1P->'|R2].
 
%les clauses qui suivent sont pour la traversée de la rive B vers la rive A
traverseBA(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    LOUPS2 >= 1,
    ZLOUPS1 is LOUPS1 + 1, ZLOUPS2 is LOUPS2 - 1,
    ZMOV is PMOV - 1,
    traverseAB(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), ZMOV, R2),
    R = ['<-1L'|R2].
 
traverseBA(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    LOUPS2 >= 2,
    ZLOUPS1 is LOUPS1 + 2, ZLOUPS2 is LOUPS2 - 2,
    ZMOV is PMOV - 1,
    traverseAB(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), ZMOV, R2),
    R = ['<-2L'|R2].
 
traverseBA(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    POUSSINS2 >= 1,
    ZPOUSSINS1 is POUSSINS1 + 1, ZPOUSSINS2 is POUSSINS1 - 1,
    ZMOV is PMOV - 1,
    traverseAB(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), ZMOV, R2),
    R = ['<-1P'|R2].
 
traverseBA(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    POUSSINS2 >= 2,
    ZPOUSSINS1 is POUSSINS1 + 2, ZPOUSSINS2 is POUSSINS1 - 2,
    ZMOV is PMOV - 1,
    traverseAB(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), ZMOV, R2),
    R = ['<-2P'|R2].
 
traverseBA(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV, R) :- 
    constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), PMOV),
    POUSSINS2 >= 1,
    LOUPS2 >= 1,
    ZLOUPS1 is LOUPS1 + 1, ZLOUPS2 is LOUPS2 - 1,
    ZPOUSSINS1 is POUSSINS1 + 1, ZPOUSSINS2 is POUSSINS2 - 1,
    ZMOV is PMOV - 1,
    traverseAB(rive(ZLOUPS1, ZPOUSSINS1), rive(ZLOUPS2, ZPOUSSINS2), ZMOV, R2),
    R = ['<-1L1P'|R2].
 
solution :-
    traverseAB(rive(3, 3), rive(0, 0), 11, R),
    write(R).
 
%ici c'est le but en 11 coups max :
%?- solution.

**GrosseBuse** · 13/06/2011, 23h02

Merci Trap D,

Je voulais justement expérimenter le parcours d'arbre en l'argeur

Voici le listing :

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
%problème de la traversée du professeur Layton et l'étrange village sur Nintendo DS
%le but du problème est d'amener 3 poussins et 3 loups d'une rive A à une rive B
%on ne peut déplacer que 2 animaux à la fois
%les loups ne doivent pas être supérieurs aux poussins en nombre sur aucune rive
%on ne peut déplacer la barque sans animaux dedans
%une solution existe en 11 coups
 
%ce programme en PROLOG a été écrit en SWI-PROLOG
 
%RESOLUTION DU PROBLEME PAR PARCOURS DE l'ARBRE DES SOLUTIONS EN LARGEUR
 
%format d'une action = action(liste_noms_des_noeuds, etat(rive(loups1, poussins1), rive(loups2, poussins2), vers))
%liste_noms_des_noeuds est de la forme ['1P1L->', '<-1L', '1P->'] : pour afficher la solution
%vers : booleen = true <=> déplacement de la rive A vers la rive B
 
del_deja_vu([], []) :- !.
del_deja_vu([action(_, ETAT)|L_ACTIONS], RES) :-
	db_deja_vu(ETAT),!, %deja_vu est la database des noeuds déjà visités
	del_deja_vu(L_ACTIONS, RES).
del_deja_vu([action(P, ETAT)|L_ACTIONS], RES) :-
	assertz(db_deja_vu(ETAT)),
	del_deja_vu(L_ACTIONS, ZRES),
	RES = [action(P, ETAT)|ZRES].
 
get_succ(action(L_ACTIONS, ETAT), RES) :-
	((bagof(R, traverse(action(L_ACTIONS, ETAT), R), RES_INTER),!) ; RES_INTER = []), %findall...
	del_deja_vu(RES_INTER, RES).
 
get_all_succ([], []) :- !.
get_all_succ([X|L_ACTIONS], RES) :-
	get_succ(X, ZRES),
	get_all_succ(L_ACTIONS, RES_INTER),
	append(ZRES, RES_INTER, RES).
 
solution_trouvee([], _) :- !, fail.
solution_trouvee([action(RES, etat(rive(0,0), rive(_,_), _))|_], RES) :- !.
solution_trouvee([_|L], RES) :- solution_trouvee(L, RES).
 
% ici le but principal
solution :- 
	INIT = action([], etat(rive(3, 3), rive(0, 0), true)),
	assertz(db_level([INIT])), %la liste d'actions du niveau courrant
	assertz(db_deja_vu(INIT)),
	repeat, %on répete tant qu'aucune solution n'a été trouvée
	retract(db_level(LEVEL_NODES)),
	get_all_succ(LEVEL_NODES, NEXT_LEVEL),
	assertz(db_level(NEXT_LEVEL)),
	(NEXT_LEVEL = [] ; solution_trouvee(NEXT_LEVEL, RES)), %le ; pour ou logique
	write(RES).
 
%------------ ci-dessous, les règles du jeu :	
 
prise(rive(LOUPS, POUSSINS)) :-
	POUSSINS > 0,
	LOUPS > POUSSINS.
 
	%pour chaque clause traverse on test si aucune prise n'est possible
constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)) :-
	not(prise(rive(LOUPS1, POUSSINS1))),
	not(prise(rive(LOUPS2, POUSSINS2))).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	LOUPS1 >= 1, %traversée de 1 loup de rive A vers B
	ZLOUPS1 is LOUPS1 - 1, ZLOUPS2 is LOUPS2 + 1,
	RES = action(['1L->'|L_ACTIONS], etat(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), false)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	LOUPS1 >= 2, %traversée de 2 loups de rive A vers B
	ZLOUPS1 is LOUPS1 - 2, ZLOUPS2 is LOUPS2 + 2,
	RES = action(['2L->'|L_ACTIONS], etat(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), false)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	POUSSINS1 >= 1, %traversée de 1 poussin de rive A vers B
	ZPOUSSINS1 is POUSSINS1 - 1, ZPOUSSINS2 is POUSSINS2 + 1,
	RES = action(['1P->'|L_ACTIONS], etat(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), false)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	POUSSINS1 >= 2, %traversée de 2 poussins de rive A vers B
	ZPOUSSINS1 is POUSSINS1 - 2, ZPOUSSINS2 is POUSSINS2 + 2,
	RES = action(['2P->'|L_ACTIONS], etat(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), false)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), true)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	POUSSINS1 >= 1, %traversée de 1 poussin et 1 loup de rive A vers B
	LOUPS1 >= 1,
	ZPOUSSINS1 is POUSSINS1 - 1, ZPOUSSINS2 is POUSSINS2 + 1,
	ZLOUPS1 is LOUPS1 - 1, ZLOUPS2 is LOUPS2 + 1,
	RES = action(['1L1P->'|L_ACTIONS], etat(rive(ZLOUPS1, ZPOUSSINS1), rive(ZLOUPS2, ZPOUSSINS2), false)).
 
	%les clauses qui suivent sont pour la traversée de la rive B vers la rive A
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	LOUPS2 >= 1,
	ZLOUPS1 is LOUPS1 + 1, ZLOUPS2 is LOUPS2 - 1,
	RES = action(['<-1L'|L_ACTIONS], etat(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), true)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	LOUPS2 >= 2,
	ZLOUPS1 is LOUPS1 + 2, ZLOUPS2 is LOUPS2 - 2,
	RES = action(['<-2L'|L_ACTIONS], etat(rive(ZLOUPS1, POUSSINS1), rive(ZLOUPS2, POUSSINS2), true)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	POUSSINS2 >= 1,
	ZPOUSSINS1 is POUSSINS1 + 1, ZPOUSSINS2 is POUSSINS2 - 1,
	RES = action(['<-1P'|L_ACTIONS], etat(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), true)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	POUSSINS2 >= 2,
	ZPOUSSINS1 is POUSSINS1 + 2, ZPOUSSINS2 is POUSSINS2 - 2,
	RES = action(['<-2P'|L_ACTIONS], etat(rive(LOUPS1, ZPOUSSINS1), rive(LOUPS2, ZPOUSSINS2), true)).
 
traverse(action(L_ACTIONS, etat(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2), false)), RES) :- 
	constraint(rive(LOUPS1, POUSSINS1), rive(LOUPS2, POUSSINS2)),
	POUSSINS2 >= 1,
	LOUPS2 >= 1,
	ZLOUPS1 is LOUPS1 + 1, ZLOUPS2 is LOUPS2 - 1,
	ZPOUSSINS1 is POUSSINS1 + 1, ZPOUSSINS2 is POUSSINS2 - 1,
	RES = action(['<-1L1P'|L_ACTIONS], etat(rive(ZLOUPS1, ZPOUSSINS1), rive(ZLOUPS2, ZPOUSSINS2), true)).

**Trap D** · 14/06/2011, 10h39

Bonjour
Je pense que tu te compliques la vie avec tous tes prédicats traversées.
J'ai résolu ton problème avec mon squelette de recherche en largeur.
Pour simplifier, j'ai dit que le nombre d'animaux qui traversaient était N, que N etait positif et plus petit que 2, que ce nombre N d'animaux était la somme du nombre de poussins et de loups qui traversaient, ces nombres etant compris entre 0 et 2. voila ce que ça donne pour une traversée possible :
Un état est codé par une liste à 3 éléments, la position du bateau, le nombre d'animaux à gauche et le nombre d'animaux à droite.
un_etat_suivant correspond à ton prédicat traversée

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
un_etat_suivant([g, [LG1, PG1], [LD1, PD1]], [d, [LG2, PG2], [LD2, PD2]]) :-
	% DL est le nombre de loups changeant de cote
	member(DL, [0, 1, 2]),
	% DP est le nombre de poussins changeant de cote
	member(DP, [0, 1, 2]),
	% DA est le nombre d'animaux changeant de cote
	DA is DP+DL,
	% AU moins 1 animal change de coté
	% et au plus deux animaux changent de cote
	DA > 0, DA < 3,
	% on calcule le nouveau nombre d'animaux de chaque cote
	% les loups
	LG2 is LG1 - DL,
	LD2 is LD1 + DL,
	% les poussins
	PG2 is PG1 - DP,
	PD2 is PD1 + DP,
	% on s'assure que les loups ne peuvent pas manger les poussins
	% de chaque cote
	(   PG2 \= 0 -> LG2 =< PG2; true),
	(   PD2 \= 0 -> LD2 =< PD2; true).

J'ai pratiquement le même prédicat pour le bateau à droite et c'est tout.
Le backtrack de Prolog se charge de trouver les cas possibles.

**GrosseBuse** · 14/06/2011, 12h53

Très bien tu as raison, c'est beaucoup mieu effectivement. j'aurais du y penser

problème de la traversée du prof layton

Prolog

Discussions similaires

Partager

Partager