Discussion :

[jason69]

Salut à tous!

Voila, je suis étudiant et je dois réaliser un projet au choix en prolog.
Je me suis donc dit pourquoi pas un sudoku! C'est à la mode et je pourrai trouver de l'aide probablement sur Internet!

J'ai bien trouver le tuto de pccaboche sur la résolution (que j'ai trouvé très bien fait au passage!)mais ceci n'est pas ce qui m'est demandé (je dois tout coder moi même).

Alors voila, j'ai mis en place mes contraintes comme ceci 'je ne mets pas tous les prédicats) :

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
% Grille est une grille de sudoku contenant dont certaines
% cases contiennent deja des valeurs,
% les autres cases étant initialisés à 0.
solution(Grille,Sol):-Sol= [A1,A2,A3,A4,A5,A6,A7,A8,A9,
B1,B2,B3,B4,B5,B6,B7,B8,B9,
C1,C2,C3,C4,C5,C6,C7,C8,C9,
D1,D2,D3,D4,D5,D6,D7,D8,D9,
E1,E2,E3,E4,E5,E6,E7,E8,E9,
F1,F2,F3,F4,F5,F6,F7,F8,F9,
G1,G2,G3,G4,G5,G6,G7,G8,G9,
H1,H2,H3,H4,H5,H6,H7,H8,H9,
I1,I2,I3,I4,I5,I6,I7,I8,I9],
 
% vérifie que tous les éléments de Sol sont 
% compris entre 1 et 9
dansDomaine(Sol), 
 
% Prédicat tousDifferent vérifie que tous 
% les éléments d'une liste sont différents
tousDifferent([A1,A2,A3,A4,A5,A6,A7,A8,A9]),
tousDifferent([B1,B2,B3,B4,B5,B6,B7,B8,B9]),
tousDifferent([C1,C2,C3,C4,C5,C6,C7,C8,C9]),
tousDifferent([D1,D2,D3,D4,D5,D6,D7,D8,D9]),
tousDifferent([E1,E2,E3,E4,E5,E6,E7,E8,E9]),
tousDifferent([F1,F2,F3,F4,F5,F6,F7,F8,F9]),
tousDifferent([G1,G2,G3,G4,G5,G6,G7,G8,G9]),
tousDifferent([H1,H2,H3,H4,H5,H6,H7,H8,H9]),
tousDifferent([I1,I2,I3,I4,I5,I6,I7,I8,I9]),
 
tousDifferent([A1,B1,C1,D1,E1,F1,G1,H1,I1]),
tousDifferent([A2,B2,C2,D2,E2,F2,G2,H2,I2]),
tousDifferent([A3,B3,C3,D3,E3,F3,G3,H3,I3]),
tousDifferent([A4,B4,C4,D4,E4,F4,G4,H4,I4]),
tousDifferent([A5,B5,C5,D5,E5,F5,G5,H5,I5]),
tousDifferent([A6,B6,C6,D6,E6,F6,G6,H6,I6]),
tousDifferent([A7,B7,C7,D7,E7,F7,G7,H7,I7]),
tousDifferent([A8,B8,C8,D8,E8,F8,G8,H8,I8]),
tousDifferent([A9,B9,C9,D9,E9,F9,G9,H9,I9]),
 
tousDifferent([A1,A2,A3,B1,B2,B3,C1,C2,C3]),
tousDifferent([A4,A5,A6,B4,B5,B6,B4,B5,B6]),
tousDifferent([A7,A8,A9,B7,B8,B9,C7,C8,C9]),
tousDifferent([D1,D2,D3,E1,E2,E3,F1,F2,F3]),
tousDifferent([D4,D5,D6,E4,E5,E6,F4,F5,F6]),
tousDifferent([D7,D8,D9,E7,E8,E9,F7,F8,F9]),
tousDifferent([G1,G2,G3,H1,H2,H3,I1,I2,I3]),
tousDifferent([G4,G5,G6,H4,H5,H6,I4,I5,I6]),
tousDifferent([G7,G8,G9,H7,H8,H9,I7,I8,I9]).
 
dansDomaine([]).
dansDomaine([A|L]):-A>=1,A=<9,dansDomaine(L).
 
% member (Elem, Liste) : permet de dire si Elem appartient
% à Liste
membre(Elem,[Elem|_]).
membre(Elem,[_|Suivants]):-membre(Elem,Suivants).
 
tousDifferent([]).
tousDifferent([A|L]):-not(membre(A,L)),tousDifferent(L).

Mais maintenant, je n'ai pas du tout compris comment je pouvais lancer une résolution en donnant une valeur possible à une case inconnue, propager par les contraintes (les cases devant être différentes ne peuvent plus prendre cette valeur) et voir si je peux trouver une solution (revenir si impossible).

Voila, pour le moment je dois dire que je suis assez perdu, j'ai vu quelques explications que je comprends très bien (en théorie) mais je ne vois pas du tout comment mettre en place tout ça sous prolog...

Je précise que je débute sous prolog (j'ai pas vraiment eu de "vrai" cours).

Je précise aussi que des solutions toutes faites présentes sur Internet ne m'intéressent pas trop, je préfère comprendre le truc

Merci d'avance!

[pcaboche]

J'ai bien trouver le tuto de pccaboche sur la résolution (que j'ai trouvé très bien fait au passage!

Concernant la résolution de sudoku, si tu dois tout coder toi-même, tu risqueras de tomber assez rapidement sur la problématique:

• soit décider de réduire les domaines de tes variables par propagation de contraintes, mais avec le risque de dépassement de la capacité de la pile d'appels de prédicats (= stack overflow) dans le cas de grand sudokus
• soit faire une implémentation n'utilisant que très peu de mémoire, mais beaucoup trop lente pour être exploitable
• soit, pour économiser de la mémoire, tu fais des trucs assez marrants avec des prédicats dynamiques et une base de connaissance que tu modifies au fur et à mesure (par contre, pour les retours sur trace, c'est assez galère...)

Le plus dur, c'est de trouver le juste milieu entre ces extrêmes (ou réussir à optimiser un maximum de choses). La problématique est intéressante, mais ce n'est pas ce qu'il y a de mieux pour commencer avec Prolog (à moins bien sûr que tu n'aies envie d'être rapidement dégouté par le langage).


Autre chose: les sudoku, c'est assez "bateau" comme sujet. Tellement bateau que tu risques d'être mal noté (parun prof qui te dira que le sujet a été traité en long en large et en travers sur internet). A mon avis, pour avoir un sujet original, il faut qu'il soit assez spécifique et réponde à un besoin particulier (et si possible réel). Je suis sûr que tu peux trouver plein d'exemples autour de toi (et si l'exemple est intéressant, ça peut même faire une contrib pour DVP).

[jason69]

Je pourrais en effet faire un autre projet mais comme j'ai déjà commencé celui là, maintenant je vais le terminer (et tant pis pour la note, le principal c'est que j'ai appris quelque chose non?).

Bref, j'ai donc tourné mon problème autrement : Pour chaque case vide de ma grille, je mets une valeur entre 1 et dedans et je vérifies si dans la ligne, colonne, et bloc de cette case, la valeur que j'y mets n'a pas déjà utilisé. Si cette valeur est dispo, je la mets dans ma case et je passe à la case suivante. Si elle n'est pas dispo, j'en mets une autre et je re-vérifie (mon prof m'a conseillé cette démarche en me disant que ca permettait de gagner du temps).

Je ne sais pas si c'est la meilleure méthode car manifestement ca prend beaucoup trop de temps à l'exécution....

Peut-être que j'ai fait une erreur dans mon code, le voici (j'appelle mon resolveur par grilleMini(G),resolveSudoku(G). :

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
% Valeurs possibles :
nombre(1).
nombre(2).
nombre(3).
nombre(4).
nombre(5).
nombre(6).
nombre(7).
nombre(8).
nombre(9).
 
creeGrille(G,Sol):-
% Représentation de la grille Solution
% Lignes représentées par des lettres et colonnes par des chiffres.
Sol=
[A1,A2,A3,A4,A5,A6,A7,A8,A9,
B1,B2,B3,B4,B5,B6,B7,B8,B9,
C1,C2,C3,C4,C5,C6,C7,C8,C9,
D1,D2,D3,D4,D5,D6,D7,D8,D9,
E1,E2,E3,E4,E5,E6,E7,E8,E9,
F1,F2,F3,F4,F5,F6,F7,F8,F9,
G1,G2,G3,G4,G5,G6,G7,G8,G9,
H1,H2,H3,H4,H5,H6,H7,H8,H9,
I1,I2,I3,I4,I5,I6,I7,I8,I9
],
 
creeListe(G,Sol),
 
ligne(A1,A2,A3,A4,A5,A6,A7,A8,A9,1,Sol),
ligne(B1,B2,B3,B4,B5,B6,B7,B8,B9,2,Sol),
ligne(C1,C2,C3,C4,C5,C6,C7,C8,C9,3,Sol),
ligne(D1,D2,D3,D4,D5,D6,D7,D8,D9,4,Sol),
ligne(E1,E2,E3,E4,E5,E6,E7,E8,E9,5,Sol),
ligne(F1,F2,F3,F4,F5,F6,F7,F8,F9,6,Sol),
ligne(G1,G2,G3,G4,G5,G6,G7,G8,G9,7,Sol),
ligne(H1,H2,H3,H4,H5,H6,H7,H8,H9,8,Sol),
ligne(I1,I2,I3,I4,I5,I6,I7,I8,I9,9,Sol).
 
% On remplit cette ligne avec les valeurs 1 à 9 en vérifiant
% à chaque fois si la valeur qu'on met est dispo :
ligne(A1,A2,A3,A4,A5,A6,A7,A8,A9,NumLigne,Sol):-
L=[1,2,3,4,5,6,7,8,9],
select(A1,L,L1),verif(A1,NumLigne,Sol,1),
select(A2,L1,L2),verif(A2,NumLigne,Sol,2),
select(A3,L2,L3),verif(A3,NumLigne,Sol,3),
select(A4,L3,L4),verif(A4,NumLigne,Sol,4),
select(A5,L4,L5),verif(A5,NumLigne,Sol,5),
select(A6,L5,L6),verif(A6,NumLigne,Sol,6),
select(A7,L6,L7),verif(A7,NumLigne,Sol,7),
select(A8,L7,L8),verif(A8,NumLigne,Sol,8),
select(A9,L8,_),verif(A9,NumLigne,Sol,9).
 
% Permet de vérifier que la variable X n'a pas déjà été affecté
% dans la ligne, colonne et dans le bloc ou elle se trouve
 
%Pour le bloc -> pas encore implémenté
 
verif(X,NumLigne,Sol,NumColonne):-verifLigne(X,NumLigne,NumColonne,1,Sol),verifColonne(X,NumColonne,NumLigne,1,Sol).
%,calcNumBloc(NumLigne,NumColonne,Bloc),different(X,Bloc).
 
verifLigne(_,_,_,NumColCourante,_):-NumColCourante>9.
 
verifLigne(X,Num,NumColonne,NumColCourante,Sol):-
NumColCourante=<9,
NumColonne==NumColCourante,
NCol is NumColCourante+1,
Nb is Num+1,
verifLigne(X,Nb,NumColonne,NCol,Sol).
 
verifLigne(X,Num,NumColonne,NumColCourante,Sol):-
NumColCourante=<9,
NumColonne\=NumColCourante,
NCol is NumColCourante+1,
element(Num,X1,Sol),
!,
(X\=X1;var(X1)),
Nb is Num+1,
verifLigne(X,Nb,NumColonne,NCol,Sol).
 
% Permet de vérifier que la variable X n'a pas déjà été affecté
% dans la colonne ou elle se trouve :
verifColonne(_,_,_,NumLigneCourante,_):-NumLigneCourante>9.
 
verifColonne(X,Num,NumLigne,NumLigneCourante,Sol):-
NumLigneCourante=<9,
NumLigne==NumLigneCourante,
NLigne is NumLigneCourante+1,
Nb is Num+9,
verifColonne(X,Nb,NumLigne,NLigne,Sol).
 
verifColonne(X,Num,NumLigne,NumLigneCourante,Sol):-
NumLigneCourante=<9,
NumLigne\=NumLigneCourante,
NLigne is NumLigneCourante+1,
element(Num,X1,Sol),
!,
Nb is Num+9,
(X\=X1;var(X1)),
verifColonne(X,Nb,NumLigne,NLigne,Sol).
 
% X sera la variable en position I dans la liste
element(1,X,[X|_]).
element(I,X,[_|L1]):-nonvar(I),J is I-1,element(J,X,L1).
element(I,X,[_|L1]):-var(I),element(J,X,L1),I is J+1.
 
% member (Elem, Liste) : permet de dire si Elem appartient
% à Liste
membre(Elem,[Elem|_]).
membre(Elem,[_|Suivants]):-membre(Elem,Suivants).
 
tousDifferent([]).
tousDifferent([A|L]):-not(membre(A,L)),tousDifferent(L).
 
creeListe([],[]).
creeListe([N|L1],[N|L2]):-creeListe(L1,L2).
creeListe([_|L1],[_|L2]):-creeListe(L1,L2).
 
% Predicat permettant de résoudre la grille de sudoku
solution(G,Sol):-creeGrille(G,Sol).%,contraintes(Sol).
affiche(G):-afficheLigne,afficheGrille(G,0,0),afficheLigne.
 
afficheLigne:-write('============='),nl.
 
afficheGrille([],_,_).
 
afficheGrille([A|L],NumVar,NumLigne):-
(NumVar==0;NumVar==3;NumVar==6),
write('|'),
write(A),
NewVar is NumVar+1,
afficheGrille(L,NewVar,NumLigne).
 
afficheGrille([A|L],NumVar,NumLigne):-
NumVar==8,
NewLigne is NumLigne+1,
(NewLigne==3;NewLigne==6),
write(A),
write('|'),
nl,
afficheLigne,
afficheGrille(L,0,NewLigne).
 
afficheGrille([A|L],NumVar,NumLigne):-
NumVar==8,
NewLigne is NumLigne+1,
write(A),
write('|'),
nl,
afficheGrille(L,0,NewLigne).
 
afficheGrille([A|L],NumVar,NumLigne):-
write(A),
NewVar is NumVar+1,
afficheGrille(L,NewVar,NumLigne).
 
% Predicat permettant de résoudre une grille de sudoku
% puis d'afficher la solution.
resolveSudoku(G):-solution(G,Sol),affiche(Sol).
 
grilleMini([
_,1,_,_,_,_,_,_,9,
_,_,_,3,_,_,8,_,_,
_,_,_,_,_,_,6,_,_,
_,_,_,_,1,2,4,_,_,
7,_,3,_,_,_,_,_,_,
5,_,_,_,_,_,_,_,_,
8,_,_,6,_,_,_,_,_,
_,_,_,_,4,_,_,2,_,
_,_,_,7,_,_,_,_,_
]).

Peut-être est-ce ma démarche qui n'est pas bonne? Ou alors j'ai peut-etre fait une erreur dans mon code?

Quand j'exécute tout ca, j'ai jamais pu voir ce que ca donnait puisque l'exécution était tellement longue que j'arrêtais avant

J'ai donc grand besoin d'aide

Merci d'avance aux âme charitables qui voudront bien me filer un coup de main!

[pcaboche]

(et tant pis pour la note, le principal c'est que j'ai appris quelque chose non?).

Tu peux aussi apprendre plein d'autres choses avec d'autres projets...

(mon prof m'a conseillé cette démarche en me disant que ca permettait de gagner du temps).

Faux !

Cela permet de gagner en mémoire (pas de risque de dépassement de la pile) mais cela prend un temps considérable (vu qu'on n'élimine pas d'office certaines valeurs absurdes).

Je ne sais pas si c'est la meilleure méthode car manifestement ca prend beaucoup trop de temps à l'exécution....

C'est exactement ce que je viens de te dire: ce n'est pas la meilleure méthode vu que cela prend beaucoup trop de temps.

Une autre méthode consiste à spécifier un domaine pour chaque variable (de 1 à 9) et ensuite de répercuter chaque changement de domaine d'une variable aux variables voisines (même ligne/colonne/carré). C'est la propagation de contraintes et ça va beaucoup plus vite. Le problème, c'est que ça fait pas mal d'appels récursifs et tu peux te retrouver avec un dépassement de capacité de la pile (à moins de bien tout optimiser).

Comme je le disais, concernant la résolution de sudoku, ce n'est pas évident de tout implémenter "from scratch".

[jason69]

Ca yest j'ai réussi à faire mon solveur de sudoku!

Pour la méthode c'est à peu près celle que j'ai expliqué et qui marche assez bien :

- Je parcours mes lignes une par une.
- Pour chaque élément de ma ligne, je mets une valeur (valeur distincte des autres déjà présente sur la ligne) puis je teste si cette valeur n'a pas été utilisée dans la colonne et le bloc associé. Si non, on passe à l'élement suivant de la ligne, sinon on met une autre valeur.

Par contre il est vrai que pour les sudoku les plus difficiles, je n'ai pas vérifié si ça allait assez vite.... Il y a peut-être meilleure solution!

Voila, je pourrais mettre mon code si ça intéresse quelqu'un...

Merci au forum!

[gedili]

Salut,

je m'attaque a prolog, donc je connait pas encore le langage, ceux que je maitrise sont le c, c++, et scheme.

Donc au niveau du code je me suis pas vraiment penché dessus, en revanche ta methode de résoltion me parait pas concluante en dehors des cas simples.

Si tu te contente de :

- Je parcours mes lignes une par une.
- Pour chaque élément de ma ligne, je mets une valeur (valeur distincte des autres déjà présente sur la ligne) puis je teste si cette valeur n'a pas été utilisée dans la colonne et le bloc associé. Si non, on passe à l'élement suivant de la ligne, sinon on met une autre valeur.

tu vas forcement avoir un probleme si tu ne fais pas de retour arriere.
Pour le premier element tu vas par exemple pouvoir mettre x parce qu'il n'est ni dans colonne, ni ligne ni bloc, ceci dit il est fort possible que ce x ne soit pas la bonne solution, et que donc apres avoir traité ensuite plusieurs autres elements tu te retrouve dans une situation sans solution.

Il faudra donc remonter jusqu'a ce x, et essayer une autre possibilité, mais cela reviendra a explorer toutes les combianaisons jusqu'a que tu en trouve une valide ce qui est tres lourd.

je m'y connait pas en prolog j'ai fait quelque fois des sudoku, et donc evidement pour optimiser traite d'abord les cases ayant le moins de possibilites. Et comme autre amelioration essaye d'implementer,cette propriete qui m'a debloqué pas mal de situations, donc dans ton cas bcp de parcours sans solution:

dans une ligne/bloc ou colonne si deux cases n'ont que 2 valeurs possibles qui sont les memes pour l'une et l'autre, alors tu peux les enlever des valeurs possibles des autres cases de la ligne/bloc ou colonne. Generalisation possibles (3 cases ayant les meme 3 valeurs possibles ...) mais situations peu frequentes .

dans une colonne par exemple tu a 3 case libres, valeur possibles de la premiere 2,6,8, deuxieme 6,2 et troisieme 2,6. tu peux directement en deduire que la premiere est 2.