Discussion :

[pcaboche]

Très bien !

Cependant, en testant, je me suis aperçu que j'avais oublié une condition très importante: on ne propage que si le domaine a changé (sinon, ça fait une boucle infinie !)

Le prédicat devient donc:

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
%%
% variablesToPropagate
%
% Arguments:
%   +Ind           : l'indice de la variable
%   +OldDom        : l'ancien domaine de la variable
%   +Dom           : le domaine de la variable
%   +VarsToProp    : liste des variables à propager
%   -NewVarsToProp : la nouvelle liste des variables à propager
%
% Comportement:
%   Domaine limité à une valeur       => ajouté aux variables à propager si domaine a changé
%   Domaine vide                      => échec
%   Plus d'une valeur dans le domaine => pas de propagation
%
 
variablesToPropagate(Ind, OldDom, [Val], Vars, [(Ind,Val) | Vars]) :- 
  OldDom \= [Val],
  !.
 
 
variablesToPropagate(_, _, [], _, _) :-
  !, fail.
 
variablesToPropagate(_, _, _, Vars, Vars) :- !.

Mais j'en suis encore au truc d'avant moi

Quel truc? La saisie de la grille?


Il faudrait aborder la question de la saisie des valeurs et de la propagation des variables. J'ai implémenté ce prédicat (et le reste):

Code :

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

1
2
3
4
5
6
7
8
%%
% setValue(+N, +Ind, +Val, +Grid, -NewGrid)
%
%   Affecte la valeur +Val à la case d'indice +Ind et propage les contraintes
%
 
setValue(N, Ind, Val, Grid, NewGrid) :-
  propagateConstraints(N, [(Ind,Val)], Grid, NewGrid).

Tu penses réussir à tout implémenter ou t'as besoin d'aide? T'as encore beaucoup d'autres projets, exams, etc?

[temar]

Tu penses réussir à tout implémenter ou t'as besoin d'aide? T'as encore beaucoup d'autres projets, exams, etc?

J'ai plutôt l'air de bien galérer... Avec le temps je devrais réussir (enfin, j'espère lol). Sauf que le temps...
Exam la semaine du 20 juin, et projet a rendre pour la semaine juste avant les exams, autrement dit bientôt.
Autre projet : je m'y suis pris le plus tôt possible, mais 2 autres ne sont pas encore finis, et aucun rapport n'est fait (yen a 4)

Sinon oui le truc d'avant que j'ai pas fini, c'est bien la saisie de la grille

[pcaboche]

Sinon oui le truc d'avant que j'ai pas fini, c'est bien la saisie de la grille

Pour la saisie de la grille, tu pars d'une grille vierge (où tous les domaines sont [1,2,3,4,5,6,7,8,9]) et tu rajoutes les contraintes les unes après les autres avec le prédicat setValue/5 cité précédemment.

Tu veux que je te file ce que j'ai fait pour la propagation de contraintes ou ça va aller?

[temar]

Je vais essayer de me débrouiller, et si a un moment, je sens que mon seul recours est de sauter par la fenêtre, je te redemanderais de l'aide.

Merci, tu m'as déjà beaucoup aidé

Juste pour etre sur, je repars donc de GenerateGrid, et a partir du résultat, je propage les contraintes ?

Donc je parcours la grille de données, et pour chaque valeur je regarde si c'est un 0 ou pas.
En fonction, je dois réduire les domaines avec setValue. Il faut donc que j'écrive le prédicat qui est utilisé dans setValue.

En fait, j'ai passé l'après midi a essayé d'écrire un truc pour rien ?

[pcaboche]

Je vais essayer de me débrouiller, et si a un moment, je sens que mon seul recours est de sauter par la fenêtre, je te redemanderais de l'aide.

Pourquoi la fenètre? Pourquoi pas une balle à la place? Ben oui, une balle et: pan temar!

Juste pour etre sur, je repars donc de GenerateGrid, et a partir du résultat, je propage les contraintes ?

Oui !

En fait, j'ai passé l'après midi a essayé d'écrire un truc pour rien ?

Comment ça l'après-midi? Normalement tu boucles ça en 2 minutes (le temps de tapper, quoi...). Ah la la, l'UTBM c'est plus ce que c'était !

Moi, en une après-midi, je t'ai fait la propagation des contraintes. Visiblement, ça a l'air de marcher (mais on n'est jamais à l'abris d'un bug). C'est justement en faisant cela que je me suis rendu compte que tu ne pouvais pas écrire ta grille directement (enfin si, mais tu ne réduis pas tes domaines, donc ça met plus de temps pour trouver la solution...)

[temar]

oui enfin, le prolog et moi

Enfin, tant qu'au final ça marche

[pcaboche]

oui enfin, le prolog et moi

Quand tu sais faire du Prolog, tu sais tout faire ! (à un moment, c'était ma signature. )

Enfin, tant qu'au final ça marche

Knuth a dit un jour:

1. Il faut que ça marche
2. Il faut que ça marche bien
3. Il faut que ça marche vite

[temar]

Quand tu sais faire du Prolog, tu sais tout faire ! (à un moment, c'était ma signature. )

oui oui, je l'avais vu
Mais moi je sais pas encore en faire
Mais je désespère pas

Knuth a dit un jour:

1. Il faut que ça marche
2. Il faut que ça marche bien
3. Il faut que ça marche vite

Facile a dire quand on sait le faire

[pcaboche]

Avant que temar ne se défenestre et que cela traumatise tous les gamins du quartier, voici un bout de code pour la propagation des contraintes.

J'ai juste laissé un tout petit prédicat (quelques lignes seulement) à implémenter:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
%%
% setValue(+N, +Ind, +Val, +Grid, -NewGrid)
%
%   Affecte la valeur +Val à la case d'indice +Ind et propage les contraintes
%
 
setValue(N, Ind, Val, Grid, NewGrid) :-
  propagateConstraints(N, [(Ind,Val)], Grid, NewGrid).
 
 
%%
% propagateConstraints(+N, +VarsToProp, +Grid, -NewGrid).
%
%

Prédicat propagateConstraints à implémenter

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
%%
% setConstraint(+N, +Ind, +Val, +Grid, +CurInd, +VarsToProp, -NewGrid, -NewVarsToProp)
%
%
 
setConstraint(N, Ind, Val, [Dom|Grid], CurInd, VarsToProp, [[Val]|NewGrid], NewVarsToProp) :-
  % Meme case  
 
  Ind == CurInd,
  !,
 
  % si la valeur n'est pas dans le domaine => échec
  member(Val, Dom),       
 
  NextInd is CurInd + 1,
  setConstraint(N, Ind, Val, Grid, NextInd, VarsToProp, NewGrid, NewVarsToProp).
 
 
 
 
setConstraint(N, Ind, Val, [Dom|Grid], CurInd, VarsToProp, [NewDom|NewGrid], NewVarsToProp) :-
  % Meme ligne, colonne ou carre
 
  ligneColonneCarre(Ind, N, LiInd, ColInd, CarInd),
  ligneColonneCarre(CurInd, N, LiCur, ColCur, CarCur),
  ( LiInd==LiCur ; ColInd==ColCur ; CarInd==CarCur ),
 
  !,
 
  removeFromSortedList(Dom, Val, NewDom),
  variablesToPropagate(CurInd, Dom, NewDom, VarsToProp, TempVarsToProp),
 
  NextInd is CurInd + 1,
  setConstraint(N, Ind, Val, Grid, NextInd, TempVarsToProp, NewGrid, NewVarsToProp).
 
 
 
 
setConstraint(N, Ind, Val, [Dom|Grid], CurInd, VarsToProp, [Dom|NewGrid], NewVarsToProp) :-
  % Variable non affectée par le changement
 
  NextInd is CurInd + 1,
  setConstraint(N, Ind, Val, Grid, NextInd, VarsToProp, NewGrid, NewVarsToProp).
 
 
setConstraint(_, _, _, [], _, VarsToProp, [], VarsToProp).
  % Plus de variable => on s'arrête

Note: le prédicat member/2 est défini de base dans swi-prolog mais doit être implémenté pour d'autres interprèteurs.

[pcaboche]

A l'intention des étudiants de l'UTBM ayant le même sujet que temar:

Merci de ne plus m'importuner par mail ou par message privé sur votre problème de sudoku en Prolog. J'ai franchement autre chose à faire ce week-end que de faire vos devoirs (ce n'est d'ailleurs pas la vocation de ce forum).

Votre soutenance est Jeudi, si vous attendez la dernière minute pour essayer de bricoler un programme, c'est votre problème, pas le mien (et ne me dites pas que vous avez d'autres projets, parce que vos collègues ont autant de projets que vous et s'en sortent quand même en s'y prennant suffisamment à l'avance).

Cordialement.