Discussion :

[temar]

Salut tout le monde !

Voila, comme beaucoup de monde, je suis entrain de coder un solveur de sudoku. Sauf que je débute sous prolog, donc c'est pas évident.

J'ai bien réussi a définir les contraintes :

- tous les termes d'une ligne sont différents
- tous les termes d'une colonne sont différents
- tous les termes d'un carré sont différents

Maintenant, je veux définir la contrainte sur le fait que les termes sont compris entre 1 et 9.

J'ai donc définit les prédicats :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
%toutes les valeurs du sudoku sont entre 1 et 9
tous_entre_un_et_neuf([]).
tous_entre_un_et_neuf([T|R]) :-
  entre_un_et_neuf(T),
  tous_entre_un_et_neuf(R).
 
%imposer qu'une variable soit comprise entre 1 et 9
entre_un_et_neuf(X) :-
  le(1,X),
  le(X,9),
  intsplit([X]).

Si je teste sur un sudoku résolu, il me renvoit bien true, donc a priori, il arrive bien a tester si des valeurs sont comprises entre 1 et 9.
Cependant, lorsque je passe ma grille de variables, il part en boucle infinie, en m'affichant :

true;
true;
true;
true;
etc...

Mon appel se fait comme suit :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
GRILLE = 
 [ 
    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
  ],
  tous_entre_un_et_neuf(GRILLE).

Pour info, c'est un projet scolaire, donc il y a des contraintes de travail : prolog IV et pas de module externe. On code tout nous-mêmes...

Voila, je vois pas trop où est mon erreur. Si vous pouviez m'éclairer, ça serait sympa

D'avance merci

[pcaboche]

Pour bien situer par rapport au contexte, il s'agit de résoudre un sudoku sans avoir recours à la PLC (mon article sur la PLC n'est donc d'aucune aide ici).

Pour que tout le monde soit sur le même pied dégalité, je vais poster ce que je t'ai dit par mp:

Au niveau de la représentation des données, je procéderais ainsi:

• on représente chaque case sous la forme d'une liste des valeurs qu'elle peu prendre (au départ: [1,2,3,4,5,6,7,8,9])
• on représente la grille comme une liste de ces cases. (Je n'aime pas la représentation sous la forme d'une liste de listes, beaucoup trop problématique à gérer).
• on aura des prédicats qui, en fonction de l'index dans la liste, nous donneront le numéro de la ligne et de la colonne dans le sudoku. Grâce à ces prédicats on écrira d'autres prédicats qui nous diront si 2 cases sont situées sur la même ligne, colonne ou carre

Pour la résolution du problème, tu as 2 étapes importantes:

• la réduction des domaines
• la recherche des solutions

Réduction des domaines:
A chaque fois que tu fixes la valeur d'une case, tu dois propager cette contrainte à toutes les variables affectées par le changement (ex: si on fixe la valeur d'une case à 3, on doit retirer la valeur 3 des domaines de toutes les variables correspondant aux cases situées sur la même ligne, la même colonne ou dans le même carré).

Durant cette phase, il faut vérifier les choses suivantes:

• si le domaine d'une variable devient vide, il n'y a pas de solution. Pas besoin d'aller plus loin, on fait échouer le prédicat ("!, fail.")
• si le domaine d'une variable est réduit à une seule valeur, alors il faut également propager cette contrainte (appel récursif au prédicat de réduction de domaines)

Recherche des solutions
Une fois que tu auras complètement réduit la grille (donc après avoir fixé toutes les valeurs connues), tu te retrouveras normalement avec certaines cases pouvant avoir plusieurs valeurs possibles (sinon, c'est que le sudoku est entièrement résolu).

Si une case a plusieurs valeurs possibles, tu fixes arbitrairement sa valeur à la première et tu propages les contraintes avec le prédicat de réduction des domaines. Soit cela t'amène vers une solution (auquel cas tu la retournes), soit cela échoue et dans ce cas, tu essayes avec les autres valeurs possibles.

L'idée importante est que la recherche de solution utilise le prédicat de réduction de domaines, ce qui facilite son implémentation (puisqu'une partie du boulot est déjà faite!). Cependant, il est très important d'avoir un prédicat de réduction de domaines qui marche extrêmement bien. Il faudra donc bien le tester.


En théorie, l'ordre dans lequel tu instancies tes variables à une incidence sur le temps d'exécution et il vaut mieux commencer par instancier les variables ayant le plus petit domaine. Pour ce problème, la recherche des variables ayant le plus petit domaine risque de faire perdre plus de temps qu'il ne permettrait d'en gagner.

[temar]

Oublier, ça je sais faire

En gros, je recommence a zéro

Première étape, j'essaye de générer des listes N*N, contenant des listes de 1 à N... J'essaye

[pcaboche]

Première étape, j'essaye de générer des listes N*N, contenant des listes de 1 à N... J'essaye

En fait, une liste de taille N^4 contenant les élément de 1 à N^2 conviendrait mieux (pour des sudoku de taille N*N*N*N). C'est mieux niveau interface.

Voici ce que ça donne (avec N=3, on aura 81 éléments de valeurs entre 1 et 9) :

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
generateGrid(N, Grid) :-
  N_2 is N*N,
  N_4 is N_2*N_2,
  generateInterval(1, N_2, Element),
  generateList(N_4, Element, Grid).
 
 
generateInterval(I, I, [I]) :- !.
generateInterval(I, N, [I|L]) :-
  NewI is I+1,
  generateInterval(NewI, N, L).
 
 
generateList(0, _, []) :- !.
generateList(I, Elem, [Elem|L]) :-
  NewI is I-1,
  generateList(NewI, Elem, L).

[temar]

Cela fonctionne nickel et je te remercie (encore) pour l'aide que tu m'apportes.

Il faut juste remettre le i de [i] (deuxième prédicat) en majuscule

Pour pouvoir accéder à chacun des membres, il faut donc que je passe par son index dans la liste ? Et pour trouver l'index, je fais un simple comptage ?

Avec ça, ça irait ?

Code :

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

1
2
3
4
5
6
7
8
9
10
 
trouve_index(1,T,[T|_]).
trouve_index(N,X,[T|R]) :-
  dif(X,T),
  trouve_index(N-1,X,R).
 
 
>> trouve_index(N,3,[1,2,3,4,5,6]).
 
N = 3.

J'ai le pressentiment que ça suffira pas ?

[pcaboche]

Il faut juste remettre le i de [i] (deuxième prédicat) en majuscule

Je ne sais pas comment cette faute de frappe est apparue, mais elle y était. C'est corrigé.

Pour pouvoir accéder à chacun des membres, il faut donc que je passe par son index dans la liste ?

Non.

Et pour trouver l'index, je fais un simple comptage ?

Oui.

Les indices nous permettrons de savoir, en fonction de N, si 2 cases se trouvent à la même ligne, à la même colonne, ou dans le même carré. Par contre, on effectuera un parcours de liste tout ce qu'il y a de plus banal en Prolog (patience, tu verras...).

Je pense qu'il est préférable de dire que l'indice du premier élément de la grille est 0. Cela évitera de soustraire 1 à chaque fois.

Maintenant, il nous faut écrire des prédicats qui, en fonction de N, nous retourneront les numéros de ligne, de colonne, de carré d'une case d'indice Ind (en vue d'effectuer des comparaisons).

Il nous faudra aussi un prédicat removeFromSortedList(+List, +Element, -NewList) qui supprime Element de la liste triée List et unifie le résultat dans NewList.

Je te laisse réfléchir là-dessus.

J'ai le pressentiment que ça suffira pas ?

En fait, ton prédicat trouve_index/3 ne nous servira pas à grand chose (on n'a pas besoin de faire de recherche dans une liste).

[temar]

Maintenant, il nous faut écrire des prédicats qui, en fonction de N, nous retourneront les numéros de ligne, de colonne, de carré d'une case d'indice Ind (en vue d'effectuer des comparaisons).

Je vois ça des demain, la fatigue n'aidant pas à réfléchir...

[pcaboche]

Je vois ça des demain, la fatigue n'aidant pas à réfléchir...

Bouarf, c'est même pas drôle: 0h15 et dèjà fatigué... C'est plus ce que c'était les étudiants de l'UTBM !

Dis plutôt que c'est samedi soir et que t'as envie de faire la fête, ce sera plus plausible...

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
ligneColonneCarre(Ind, N, Li, Col, Car) :-
  N_2 is N*N,
  Li  is Ind //  N_2,
  Col is Ind mod N_2,
  Car is (Li//N)*N + Col//N.
 
 
 
removeFromSortedList([T|Q], Elem, [T|R]) :-
  T < Elem,
  !,
  removeFromSortedList(Q, Elem, R).
 
removeFromSortedList([T|Q], Elem, Q) :-
  T == Elem,
  !.
 
removeFromSortedList(L, _, L).

[temar]

Arf, nan nan, j'étais vraiment fatigué
Mais la veille j'avais fait la fête, donc ceci explique cela

Bon, ben je vois que tu as rajouté du code, je vais regarder ça

[pcaboche]

Mais la veille j'avais fait la fête, donc ceci explique cela

Tous les mêmes ces UT-Bohémiens !

[temar]

Tu supportais pas de faire la chouille, c'est pour ça que t'es parti ?

Bon, trêve de plaisanterie, je regarde le prédicat pour calculer le numéro d'une ligne, colonne et carré, mais ça me chiffonne.

Genre, pour le calcul de la ligne

Code :

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

Li  is Ind //  N_2

donc si je veux le numéro de la case 21, ça fait 21/9, ce qui donne 2,333333 et prolog me rend 2. Or la case 21 est sur la ligne 3.
J'ai pensé a ajouter 1 au résultat, mais pour les case 9, 18, 27, etc, ça va pas, vu que par exemple, 18/9 = 2, +1 ça fait 3, et la case 18 et sur la ligne 2...

Sinon, pour les colonnes, le modulo ne fonctionne pas
J'ai regardé dans la doc, il y a bien un prédicat mod/3 qui existe, mais lorsque je teste :

Relation not yet implemented: mod
false.

Je précise, que dans la doc, ya un gros point noir a côté de ce prédicat, mais je sais pas où il renvoie. Donc apparemment, il est pas encore implémenté

[temar]

Bon, pour le modulo, c'est réglé.

Code :

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

1
2
3
4
5
6
7
8
9
10
eucl(0,A,A,B) :- lt(A,B).
eucl(Q+1,R,A,B) :-
  ge(A,B),
  eucl(Q,R,A-B,B).
 
 
>> eucl(Q,R,21,9).
 
R = 3,
Q = 2.

Donc, je pense que ça fonctionne comme suit :

- Si l'indice de la case < N_2 et que le Reste de la division euclidienne est différent de 0, on a
ligne = 1
colonne = Reste

- Si l'indice de la case > N_2 et que le reste de la division euclidienne est différent de 0, on a
ligne = Quotient + 1
colonne = R

- Si le reste de la division euclidienne = 0, on a
ligne = Quotient
colonne = N_2

Je vais modifier le prédicat LigneColonneCarre, et voir ce que ça donne.

[pcaboche]

Tu supportais pas de faire la chouille, c'est pour ça que t'es parti ?

Non, c'est surtout parce que j'étais trop limite niveau maths. Et aussi parce que j'aimais pas cette école (au point que j'ai même pas re-postulé à la sortie de l'IUT et je crois que j'ai eu raison). Sinon, je ne suis pas un gros fêtard non plus...

Concernant les modulos, je tiens à préciser que tous les indices de lignes, colonnes et carré commencent en fait à 0. On a donc une ligne 0, une colonne 0 et un carré 0 (et le premier indice de la grille est aussi 0). Le but est d'avoir un moyen d'identifier chaque ligne, colonne et carré de manière unique, peu imoporte la méthode utilisée (que les indices commencent à 0 ou 1, on s'en fout...). J'ai vérifié (en parcourant tous les éléments de la grille et en regardant la valeur de leur ligne, colonne, carré et ça a l'air de marcher.

Exemple de test (sous swi-prolog) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
test :-
  generateInterval(0,80,Inter),
 
  forall(
     member(Ind,Inter)
  ,
     (
       ligneColonneCarre(Ind, 3, _, _, Car),
       write(Car), write(' ')
     )
  ).

Ca renvoie bien :

Code :

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

0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 3 3 3 4 4 4 5 5 5 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 6 6 6 7 7 7 8 8 8 6 6 6 7 7 7 8 8 8

[temar]

Ok ok, commençons à zéro alors.
Mais j'utilise quand meme mon prédicat de division euclidienne pour avoir le modulo

[pcaboche]

Mais j'utilise quand meme mon prédicat de division euclidienne pour avoir le modulo

De toute façon t'as pas le choix: l'opérateur mod n'est aps implémenté sous ton interprèteur Prolog (je trouve ça un peu ridicule, mais c'est pas grave... ).


Maintenant, il nous faut un prédicat pour pouvoir entrer notre grille. Ce prédicat prendra en entrée une liste (liste d'entier entre 0 et N) et nous sortira une liste de listes (notre grille de sudoku, avec les domaines de chaque variables sous forme d'une liste):
- 0 => [1,2,3,...,N]
- X appartient à 1..N => [X]
C'est pas trop difficile...

Ce prédicat rendra obsolète le prédicat generateGrid, mais ce n'est pas grave c'est une question de performance.

Après on en viendra à la réduction de domaine proprement dite, ce qui sera vraiment le gros morceau...

[temar]

ok , je me m'y met, mais il ne faut pas aussi des prédicats qui utilise ligneColonneCarre, pour savoir si 2 cases sont sur la meme ligne, la meme colonne ou dans le meme carré ?

[pcaboche]

ok , je me m'y met, mais il ne faut pas aussi des prédicats qui utilise ligneColonneCarre, pour savoir si 2 cases sont sur la meme ligne, la meme colonne ou dans le meme carré ?

Pas forcément (si on ne le fait qu'à un seul endroit du programme, on ne va pas déclarer un prédicat exprès pour ça). On verra ça un peu plus loin (des fois, quand on essaye de trop anticiper, on finit par écrire des choses qui ne servent à rien).

[pcaboche]

Ce prédicat rendra obsolète le prédicat generateGrid...

Rectification: on en a quand même besoin. C'est à partir d'une grille "vierge" qu'il faut ajouter des contraintes.

Je regarde la propagation des contraintes en ce moment même.


Jete déjà un oeil à ce prédicat (plus facile à écrire qu'à expliquer) et dis-moi si tu comprends:

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
%%
% variablesToPropagate
%
% Arguments:
%   +Ind           : l'indice 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
%   Plus d'une valeur dans le domaine => pas de propagation
%   Domaine vide                      => échec
%
 
variablesToPropagate(Ind, [Val], Vars, [(Ind,Val) | Vars]) :- !.
 
variablesToPropagate(_, [_|_], Vars, Vars) :- !.
 
variablesToPropagate(_, [], _, _) :-
  !, fail.

[temar]

Pas patrique de savoir si ce que j'écris est presque bon ou pas. Le truc me répond que L est de la forme tree...

[temar]

et dis-moi si tu comprends:

Oui, je vois ce que ça fait. Ca va créer une liste des variables à propager.

Si un domaine ne contient qu'une valeur, c'est que c'est la valeur de la case, donc il faut propager la contrainte pour dire que sur la meme ligne, la meme colonne et dans le meme carré, on ne peut pas avoir cette valeur.

Si un domaine contient plusieurs valeurs, ya rien a faire.

Si un domaine est vide, le sudoku est faux...

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