Discussion :

[Nicobras]

Bonjour !

Je suis en train d'essayer faire un programme permettant de résoudre des sudokus sans utiliser la méthode du "backtracking".
J'ai donc fait une procédure permettant de modifier un tableau (contenant un sudoku), mais le tableau n'est pas modifié au final !
Je ne comprends pas mon erreur, puisque le programme valide bien toutes les conditions imposées (il passe bien par tous les "if"), mais j'ai l'impression que seule la ligne spécifique ou j'assigne des valeurs dans les cases du tableau n'est pas prise en compte.
Lorsque j'affiche le tableau avant, puis après la procédure, il n'est pas modifié. Ai-je mal compris le fonctionnement des procédures ?
Je n'ai vraiment aucune idée d'où peu se trouver mon erreur.

[Prof]

Bonjour.

Citation :

Je n'ai vraiment aucune idée d'où peu se trouver mon erreur.

Nous non plus !

Pour t'aider, il nous faut un minimum de renseignements, en premier lieu le code qui pose problème.

Alors, fais un copié-collé de ton programme entre les balises [code] et [/code].
Et poste le tout ...

[droggo]

Bonjour,

Parions qu'il s'agit d'un passage par valeur plutôt que par adresse.

[Nicobras]

J'avais peur que ça soit un peu confus, je suis pas sûr d'être vraiment à cheval sur tout les conventions de présentation, etc...

Voilà la procédure qui pose problème :

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
 
Procedure ResSect (chi:integer);  
 
var It, Jt, S, I1, J1, I2, J2 : integer;     {il y a en plus Sud[I,J] qui est un tableau de 9*9 cases contenant un sudoku non complété, et des cases contenant 0}
 
Begin
For I1:=1 to 9 do
        Begin
        For J1:=1 to 9 do
                Begin
                If (((I1=2) or (I1=5) or (I1=8)) and ((J1=2) or (J1=5) or (J1=8))) Then   
                        Begin
                        It:=I1;
                        Jt:=J1;
                        S:=0;
                        For I2:=It-1 to It+1 do
                                Begin
                                For J2:=Jt-1 to Jt+1 do
                                        Begin
                                        If ((VerifLigne(chi)=1) and (VerifColonne(chi)=1) and (VerifSecteur(chi)=1)) Then    {ces fonctions vérifient si le chiffre correspond aux règles du jeu}
                                                Begin
                                                S:=S+1;
                                                I:=I2;
                                                J:=J2;
                                                End;
                                        End;
                                End;
                        If (S=1) Then
                                Begin
                                Sud[I,J]:=chi;          {Ici le tableau est sensé prendre de nouvelles valeurs, si on rajoute un Write('...'); le programme l'affiche}
                                End;
                        End;
                End;
        End;
 
End;

Pour utiliser cette procédure je l'ai simplement mise dans une boucle qui teste plusieurs fois pour chi allant de 1 à 9.
Voilà, j'espère que c'est un peu plus clair.

[Prof]

Effectivement, c'est un peu confus.
Mais rassure-toi, on a vu pire ...

Commençons par dissiper le brouillard en simplifiant cette procédure.
1) il faut indenter le code en plaçant un end sur la même colonne que le begin associé ;
cela facilite la lecture et donc la compréhension.
2) les mots clés begin et end servent à entourer un bloc d'instructions afin que ce bloc se comporte comme une seule instruction ;
il n'y a pas besoin de begin/end pour entourer une seule instruction.
3) les variables intermédiaires It et Jt ne sont pas indispensables.

Après simplifications, on obtient le code suivant :

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
Procedure ResSect (chi:integer);  
var S, I1, J1, I2, J2 : integer;
Begin
  For I1:=1 to 9 do
      For J1:=1 to 9 do
          If (((I1=2) or (I1=5) or (I1=8)) and ((J1=2) or (J1=5) or (J1=8))) Then   
             Begin
                 S:=0;
                 For I2:=I1-1 to I1+1 do
                     For J2:=J1-1 to J1+1 do
                         If ((VerifLigne(chi)=1) and (VerifColonne(chi)=1) and (VerifSecteur(chi)=1)) Then
                             Begin
                                  S:=S+1;
                                  I:=I2;
                                  J:=J2;
                             End;
                 If (S=1) Then Sud[I,J]:=chi;
             End;
End;

Il apparait ainsi que le tableau est étudié bloc par bloc ( on utilise le mot "bloc" plutôt que le mot "secteur", dans les sudokus ).
Il apparait aussi que I et J sont deux variables globales et qu'elles indiquent quelle case du tableau va être modifiée.

Je présume que les fonctions VerifLigne/VerifColonne/VerifSecteur retournent 1 si le chiffre chi peut être placé dans la ligne/la colonne/le bloc.
( une remarque au passage : ce serait mieux si elles retournaient True ou False plutôt que 1 ou 0, le test serait plus simple à écrire )
La variable S compte le nombre de possibilités d'écriture du chiffre chi dans le bloc.
S'il n'y en a qu'une, la place du chiffre chi est imposée et donc on peut l'écrire dans la ligne I et la colonne J.

La méthode suivie est correcte dans l'absolu.
Mais son implémentation est ici fausse.

Je ne connais pas le code des 3 fonctions VerifLigne/VerifColonne/VerifSecteur.
Mais, sans les voir, je peux affirmer qu'elles sont mal codées !
Elles n'ont qu'un seul paramètre, chi, et donc elles utilisent aussi des variables globales pour savoir de quelle ligne/colonne/bloc il est question.
C'est une erreur : il faut passer aussi la ligne/la colonne/le bloc en paramètre de VerifLigne/VerifColonne/VerifSecteur.
En effet, je présume que VerifLigne utilise la variable globale I et vérifie si on peut écrire chi dans la ligne I.
Mais, dans le code de la procédure ci-dessus, on voit que I est modifié après le test et non avant ...
Forcément, la valeur retournée par VerifLigne n'est pas la bonne.
Et idem pour les deux autres fonctions ...

Il faut donc revoir ces trois fonctions.
Le test se fera avec VerifLigne(I2,chi), VerifColonne(J2,chi) et VerifSecteur(I1,J1,chi).
( dans la dernière fonction, il faudra calculer le numéro du bloc correspondant à I1 et J1 )
Une autre remarque au passage : la vérification du bloc doit se faire tout de suite car il est inutile d'examiner les 9 cases du bloc si chi figure déja dans le bloc.

Il y aurait d'autres remarques à faire, mais cela peut attendre.

[Nicobras]

Merci beaucoup pour ton aide.
J'ai essayé de modifier mes procédures et fonctions comme tu l'as conseillé, mais le problème persiste...
C'est probablement ma méthode pour vérifier les lignes/colonnes/blocs qui ne doit pas être bonne. J'avais essayé de la reprendre depuis un autre programme vu sur le net, en C, mais j'ai du mal comprendre du début.

Bon du coup je vais poster mon programme en entier (après modification) avec toutes les fonctions/procédure, j'espère que je suis pas trop demandant...

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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
 
program ResSecteur;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
var    Sud : array[1..9,1..9] of integer;
        I, J, chi, SI, SJ, VC, C : integer;
 
Procedure VComplet;
 
var I, J : integer;
 
Begin
VC:=1;
For I:=1 to 9 do
        For J:=1 to 9 do
                If(Sud[I,J]=0) Then VC:=0;
End;
 
Procedure CentreS(I:integer; J:integer);
 
Begin
 
If ((I=1) or (I=2) or (I=3)) Then SI:=2;
 
If ((I=4) or (I=5) or (I=6)) Then SI:=5;
 
If ((I=7) or (I=8) or (I=9)) Then SI:=8;
 
If ((J=1) or (J=2) or (J=3)) Then SJ:=2;
 
If ((J=4) or (J=5) or (J=6)) Then SJ:=5;
 
If ((J=7) or (J=8) or (J=9)) Then SJ:=8;
 
End;
 
 
Function VerifLigne (I2,chi:integer) : integer;
var J2 : integer;
Begin
For J2:=1 to 9 do
        Begin
        If (chi=Sud[I2,J2]) Then VerifLigne:=0
                                  Else VerifLigne:=1;
        End;
End;
 
Function VerifColonne (J2,chi:integer) : integer;
var  I2 : integer;
Begin
For I2:=1 to 9 do
        Begin
        If (chi=Sud[I2,J2]) Then VerifColonne:=0
                                  Else VerifColonne:=1;
        End;
End;
 
Function VerifSecteur (I1,J1,chi:integer) : integer;
 
Begin
CentreS(I1,J1);
For I1:=SI-1 to SI+1 do
        For J1:=SI-1 to SI+1 do
                If (chi=Sud[I1,J1]) Then VerifSecteur:=0
                                          Else VerifSecteur:=1;
 
 
End;
 
Procedure ResSect (chi:integer);  
var S, I1, J1, I2, J2 : integer;
Begin
  For I1:=1 to 9 do
      For J1:=1 to 9 do
          If (((I1=2) or (I1=5) or (I1=8)) and ((J1=2) or (J1=5) or (J1=8))) Then
             Begin
                 S:=0;
                 For I2:=I1-1 to I1+1 do
                     For J2:=J1-1 to J1+1 do
                         If ((VerifLigne(J2,chi)=1) and (VerifColonne(I2,chi)=1) and (VerifSecteur(I1,J1,chi)=1)) Then
                             Begin
                                  S:=S+1;
                                  I:=I2;
                                  J:=J2;
                             End;
                 If (S=1) Then Sud[I,J]:=chi;
             End;
End;
 
 
 
begin
 
Sud[1,1]:=0;
Sud[1,2]:=1;
Sud[1,3]:=8;
Sud[1,4]:=0;
Sud[1,5]:=3;
Sud[1,6]:=2;
Sud[1,7]:=6;
Sud[1,8]:=5;
Sud[1,9]:=0;
Sud[2,1]:=5;
Sud[2,2]:=9;
Sud[2,3]:=7;
Sud[2,4]:=4;
Sud[2,5]:=8;
Sud[2,6]:=6;
Sud[2,7]:=1;
Sud[2,8]:=2;
Sud[2,9]:=3;
Sud[3,1]:=2;
Sud[3,2]:=3;
Sud[3,3]:=6;
Sud[3,4]:=7;
Sud[3,5]:=1;
Sud[3,6]:=5;
Sud[3,7]:=9;
Sud[3,8]:=4;
Sud[3,9]:=8;
Sud[4,1]:=9;
Sud[4,2]:=2;
Sud[4,3]:=3;
Sud[4,4]:=5;
Sud[4,5]:=7;
Sud[4,6]:=4;
Sud[4,7]:=8;
Sud[4,8]:=1;
Sud[4,9]:=0;
Sud[5,1]:=7;
Sud[5,2]:=8;
Sud[5,3]:=5;
Sud[5,4]:=1;
Sud[5,5]:=6;
Sud[5,6]:=3;
Sud[5,7]:=4;
Sud[5,8]:=9;
Sud[5,9]:=0;
Sud[6,1]:=1;
Sud[6,2]:=6;
Sud[6,3]:=4;
Sud[6,4]:=2;
Sud[6,5]:=9;
Sud[6,6]:=8;
Sud[6,7]:=3;
Sud[6,8]:=7;
Sud[6,9]:=5;
Sud[7,1]:=3;
Sud[7,2]:=4;
Sud[7,3]:=9;
Sud[7,4]:=8;
Sud[7,5]:=2;
Sud[7,6]:=7;
Sud[7,7]:=5;
Sud[7,8]:=0;
Sud[7,9]:=1;
Sud[8,1]:=6;
Sud[8,2]:=7;
Sud[8,3]:=1;
Sud[8,4]:=3;
Sud[8,5]:=5;
Sud[8,6]:=9;
Sud[8,7]:=2;
Sud[8,8]:=0;
Sud[8,9]:=4;
Sud[9,1]:=8;
Sud[9,2]:=5;
Sud[9,3]:=2;
Sud[9,4]:=6;
Sud[9,5]:=4;
Sud[9,6]:=1;
Sud[9,7]:=7;
Sud[9,8]:=3;
Sud[9,9]:=9;
 
For I:=1 to 9 do
        Begin
        For J:=1 to 9 do
                Begin
                Write(Sud[I,J],' ');
                End;
        Writeln;
        End;
 
Writeln;
Writeln;
Writeln;
 
VComplet;
C:=0;
While ((VC=0) and (C<3000)) do
        Begin
        C:=C+1;
        For chi:=1 to 9 do
                Begin
                ResSect(chi);
                End;
        VComplet;
        End;
 
 
For I:=1 to 9 do
        Begin
        For J:=1 to 9 do
                Begin
                Write(Sud[I,J],' ');
                End;
        Writeln;
        End;
Readln;
end.

J'ai essayé de présenter un peu mieux le tout.
La procédure VComplet permet de savoir s'il reste des 0 dans le tableau, la procédure CentreS permet de trouver le centre du bloc pour les indices en entrées.
La variable C est un compteur pour que le programme ne tourne pas en boucle s'il ne peut pas remplir les cases.
Du coup le problème vient de la vérification, mais même après avoir essayé plusieurs indices différent absolument rien ne change. C'est encore un problème au niveau des variables globales/locales ?

[Prof]

Bonjour.

J'ai corrigé les erreurs qui figuraient dans ton programme.

En particulier, la fonction VerifLigne était fausse car elle retournait le résultat calculé avec le dernier indice de la boucle ;
elle ne tenait pas compte des tests effectués sur les indices précédents.
La solution consiste à initialiser le résultat de la fonction à 0 avant de parcourir la boucle.
Si, dans la boucle, on trouve que le chiffre figure déjà dans la ligne, on sort aussitôt de la fonction.
Cela se fait avec le mot clé Exit qui permet de quitter une fonction à n'importe quel endroit.
( il faut évidemment que le résultat de la fonction ait été initialisé avant )
Si on exécute la boucle en entier, sans être sorti de la fonction, c'est qu'on n'a pas trouvé le chiffre dans la ligne.
On peut alors mettre le résultat à 1 et sortir.

La même erreur figurait dans VerifColonne et VerifSecteur.

Puis j'ai modifié les fonctions afin qu'elles retournent un booléen.
C'est très pratique, un booléen ; il ne faut pas hésiter à s'en servir ...

J'ai ensuite apporté plusieurs simplifications :
j'ai simplifié la fonction CentreS et l'ai incorporée à VerifSecteur puisque c'est le seul endroit où elle sert ;
j'ai simplifié le test des numéros de ligne ou de colonne dans ResSect en utilisant des ensembles ;
on pourrait encore simplifier les deux boucles de ResSect, mais on risquerait d'y perdre en lisibilité.

J'ai enfin supprimé les variables globales qui n'étaient pas nécessaires : I, J, SI, SJ, VC, C.

A la place de la variable C, j'ai introduit la variable booléenne modif.
Elle permet de signaler une modification du tableau Sud dans la procédure ResSect.
La boucle " Repeat ... until not(modif); " est ainsi répétée jusqu'à ce qu'il n'y ait plus de modification.
C'est la bonne façon d'arrêter l'examen de la grille.

J'ai également renommé quelques variables locales.

A ce stade le programme fonctionnait, mais en partie seulement : 5 cases qui étaient vides au départ étaient remplies, mais 2 cases restaient vides.

Il m'a fallu un certain temps pour localiser l'erreur.
Elle se trouvait dans le calcul de la variable S : pour qu'on puisse écrire le chiffre dans la case, encore faut-il que la case soit libre !
Le test " la case est-elle libre ? " n'étant pas fait, S pouvait prendre des valeurs supérieures à 1, bien qu'il n'y ait plus qu'une seule case libre dans le bloc.
J'ai donc corrigé l'erreur en ajoutant une condition dans le calcul de S.

Maintenant, le programme tourne correctement.
Voici son 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
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
Program ResSecteur;
 
{$APPTYPE CONSOLE}
 
uses SysUtils;
 
var  Sud : array[1..9,1..9] of integer;
     chiffre : integer;
     modif : boolean;
 
Function VComplet : boolean;
  var I, J : integer;
  Begin
    VComplet := False;
    For I:=1 to 9 do
        For J:=1 to 9 do
            If(Sud[I,J]=0) Then Exit;
    VComplet := True;
  End;
 
Function VerifLigne(I,chi:integer) : boolean;
  var J : integer;
  Begin
    VerifLigne := False;
    For J:=1 to 9 do
        If (chi=Sud[I,J]) Then Exit;
    VerifLigne := True;
  End;
 
Function VerifColonne(J,chi:integer) : boolean;
  var I : integer;
  Begin
    VerifColonne := False;
    For I:=1 to 9 do
        If (chi=Sud[I,J]) Then Exit;
    VerifColonne := True;
  End;
 
Function VerifSecteur(I,J,chi:integer) : boolean;
  var II, JJ, SI, SJ : integer;
  Begin
    SI:=((I-1) div 3)*3 +2;
    SJ:=((J-1) div 3)*3 +2;
    VerifSecteur := False;
    For II:=SI-1 to SI+1 do
        For JJ:=SJ-1 to SJ+1 do
            If (chi=Sud[II,JJ]) Then Exit;
    VerifSecteur := True;
  End;
 
Procedure ResSect(chi:integer);  
  var I1, J1, I2, J2, I3, J3, S : integer;
  Begin
    For I1:=1 to 9 do
        For J1:=1 to 9 do
            If ((I1 in [2,5,8]) and (J1 in [2,5,8]) and VerifSecteur(I1,J1,chi)) Then
               Begin
                 S:=0;
                 For I2:=I1-1 to I1+1 do
                     For J2:=J1-1 to J1+1 do
                         If ((Sud[I2,J2]=0) and VerifLigne(I2,chi) and VerifColonne(J2,chi)) Then
                            Begin
                              S:=S+1;
                              I3:=I2;
                              J3:=J2;
                            End;
                 If (S=1) Then
                    Begin
                      Sud[I3,J3]:=chi;
                      Modif:=True;
                    End;
               End;
  End;
 
Procedure Affiche_grille;
  var I, J : integer;
  Begin
    For I:=1 to 9 do
        Begin
          For J:=1 to 9 do Write(Sud[I,J],' ');
          Writeln;
        End;
    Writeln;
  End;
 
 
begin  { corps du programme }
 
  Sud[1,1]:=0; Sud[1,2]:=1; Sud[1,3]:=8; Sud[1,4]:=0; Sud[1,5]:=3; Sud[1,6]:=2; Sud[1,7]:=6; Sud[1,8]:=5; Sud[1,9]:=0;
  Sud[2,1]:=5; Sud[2,2]:=9; Sud[2,3]:=7; Sud[2,4]:=4; Sud[2,5]:=8; Sud[2,6]:=6; Sud[2,7]:=1; Sud[2,8]:=2; Sud[2,9]:=3;
  Sud[3,1]:=2; Sud[3,2]:=3; Sud[3,3]:=6; Sud[3,4]:=7; Sud[3,5]:=1; Sud[3,6]:=5; Sud[3,7]:=9; Sud[3,8]:=4; Sud[3,9]:=8;
  Sud[4,1]:=9; Sud[4,2]:=2; Sud[4,3]:=3; Sud[4,4]:=5; Sud[4,5]:=7; Sud[4,6]:=4; Sud[4,7]:=8; Sud[4,8]:=1; Sud[4,9]:=0;
  Sud[5,1]:=7; Sud[5,2]:=8; Sud[5,3]:=5; Sud[5,4]:=1; Sud[5,5]:=6; Sud[5,6]:=3; Sud[5,7]:=4; Sud[5,8]:=9; Sud[5,9]:=0;
  Sud[6,1]:=1; Sud[6,2]:=6; Sud[6,3]:=4; Sud[6,4]:=2; Sud[6,5]:=9; Sud[6,6]:=8; Sud[6,7]:=3; Sud[6,8]:=7; Sud[6,9]:=5;
  Sud[7,1]:=3; Sud[7,2]:=4; Sud[7,3]:=9; Sud[7,4]:=8; Sud[7,5]:=2; Sud[7,6]:=7; Sud[7,7]:=5; Sud[7,8]:=0; Sud[7,9]:=1;
  Sud[8,1]:=6; Sud[8,2]:=7; Sud[8,3]:=1; Sud[8,4]:=3; Sud[8,5]:=5; Sud[8,6]:=9; Sud[8,7]:=2; Sud[8,8]:=0; Sud[8,9]:=4;
  Sud[9,1]:=8; Sud[9,2]:=5; Sud[9,3]:=2; Sud[9,4]:=6; Sud[9,5]:=4; Sud[9,6]:=1; Sud[9,7]:=7; Sud[9,8]:=3; Sud[9,9]:=9;
 
  Affiche_grille;
 
  Repeat
    modif:=False;
    For chiffre:=1 to 9 do ResSect(chiffre);
  Until not(modif);
 
  Affiche_grille;
  If VComplet Then writeln('La grille est remplie.')
              Else writeln('La grille n''est pas remplie.');
  Readln;
 
end.

Remarque : le programme remplit la grille car il y avait peu de cases vides au départ.
Si la grille est clairsemée, le programme ne pourra pas la remplir en entier en se contentant d'étudier les blocs.
Il y a d'autres examens à faire.
En fait, ce programme n'est que la première étape d'un programme résolvant les grilles de Sudoku ...

[Nicobras]

Merci beaucoup de ton aide, je comprends mieux mes erreurs maintenant.

J'ai réalisé ce programme pour un projet universitaire (déjà rendu), et le but n'était pas d'avoir un programme qui fonctionnait parfaitement, mais d'en faire le maximum.
C'est juste que ça m'irritait de ne pas voir mon erreur. Pour toutes les lacunes un peu bizarres (ne pas utiliser de booléens, etc...), elles s'expliquent par le fait que j'ai essayé de suivre le cours de mon prof au maximum, et nous n'avons jamais abordé ce type de variable (je suis en première année, et mon cursus n'est pas majoritairement informatique).
Pour les procédure/fonctions j'ai vu ça sur internet et j'ai trouvé ça très pratique, mais j'aurais du me pencher un peu plus sur la théorie avant de l'utiliser j'imagine...

Pour la suite, je vais probablement continuer le programme tout seul en essayant de tenir compte de vos conseils, je suis au courant que la résolution par bloc ne permet pas un remplissage complet d'une vraie grille.

Encore merci pour l'aide, bonne journée.

[Prof]

Et bien, pour un débutant, c'était plutôt pas mal ...

( même s'il y avait des erreurs : mais nous faisons tous des erreurs, y compris les anciens comme moi ;
les erreurs permettent de progresser ; elles sont donc indispensables)

Bonne continuation dans tes études.