génération d'une grille de sudoku

**gnouz** · 21/09/2008, 20h49

Bonsoir, j'ai réalisé un solveur / générateur de sudoku.

Le problème est que le solveur résout bien toutes les grilles, mais lorsque je génère une grille, parfois j'ai un segmentation fault et je crois que ça vient du solveur, car quand je trace avec gdb, l'erreur est sur ma fonction backtrack.

Pourtant je pense avoir pensé à tous les cas possibles où ma fonction backtrack doit retourner 0 (= qu'il n'y a pas de solutions).

Si quelqu'un pouvait m'aider, ça serait sympa

Merci d'avance

Code C :

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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
 
/* Structure d'une case de sudoku */
 
struct case_sudoku{
  int temp[10];   // tableau des possibilités de la case
  int valeur_case; // valeur de la case , 0 si aucune valeur
  int base;        // 1 si valeur_case est une base
};
 
typedef struct case_sudoku case_sudoku;
 
/* Genere une grille de sudoku */
 
void generer_grille(case_sudoku **tab,int *nb_solutions) {
 
  case_sudoku **temp=NULL;  
  int ligne,col,valeur,i,j,k=0;
  *nb_solutions=0;
 
 
  init_grille(tab);
  temp=allouer_tab(9,9);
  init_grille(temp);
 
  while(k<10) // laisser à 26 
    {
      do 
	{                       // Tant qu'il n'est pas possible de placer cette valeur refaire le random
	  ligne=nbreaupif(0,8);
	  col=nbreaupif(0,8);
	  valeur=nbreaupif(1,9);
	}
      while(conflit(temp,ligne,col,valeur));
 
      if(temp[ligne][col].valeur_case==0)
	{
	  temp[ligne][col].valeur_case=valeur;  // On place la valeur
	  temp[ligne][col].base=1;
	  k++;
	}
    }
 
 
      for(i=0;i<9;i++)
	{
	  for(j=0;j<9;j++)
	    {
	      tab[i][j].valeur_case=temp[i][j].valeur_case;
	      tab[i][j].base=temp[i][j].base;
	    }
	}
 
      backtrack(temp,0,0,nb_solutions);
      if(grille_resolu(temp) && *nb_solutions==1)
	return;
      else
	generer_grille(tab,nb_solutions);
 
}
 
/* Fonction qui choisit un nombre aléatoire entre i et j */
 
int nbreaupif(i,j) {
 
  return (rand() % (j-i+1)) + i;
 
}
 
/* Fonction qui resoud une grille de sudoku par backtracking */
 
char backtrack(case_sudoku **tab,int ligne,int col,int *nb_solutions) {
 
  int k=1,continuer=1,l;
 
  if(tab[ligne][col].base==0) // Si ce n'est pas une base
    {
      while(continuer)  // on avance dans le tableau temp pour trouver la premiere valeur candidate
	{
	  if(k>9) // Si aucune valeur n'est possible
	    {
	      tab[ligne][col].valeur_case=-1;
	      for(l=0;l<10;l++)
		tab[ligne][col].temp[l]=0;
	      continuer=0;
	      if(col==0 && ligne==0)
		return 0;
	      if(col==0) 
		{
		  col=8;
		  while(tab[ligne-1][col].base==1)
		    {
		      col--;
		    }
		  backtrack(tab,ligne-1,col,nb_solutions);  // reculer avec la derniere case non base
		}
	      else
		{
		  col=col-1;
		  while(tab[ligne][col].base==1)
		    {
		      if(col==0 && ligne==0)
			return 0;
		      if(col==0) 
			{
			  ligne-=1;
			  col=9;
			}
		      col--;
		    }
 
		  backtrack(tab,ligne,col,nb_solutions); // reculer avec la derniere case non base
		}
	    }
 
	  else if(tab[ligne][col].temp[k]==0) // Si on a trouvé une valeur candidate
	    {
	      tab[ligne][col].valeur_case=k; // On l'assigne
 
	      tab[ligne][col].temp[k]=1;
	      if(conflit(tab,ligne,col,k))  // S'il y a un conflit, on relance la boucle
		{
		  k++;
		  continuer=1;
		}
	      else  // S'il n'y a pas de conflit on sort de la boucle et on passe à la case suivante
		{
		  continuer=0;
		  if(col==8 && ligne==8)
		    {
		      (*nb_solutions)++;
		      return 1;
		    }
		  if(col==8)
		    backtrack(tab,ligne+1,0,nb_solutions);
		  else
		    backtrack(tab,ligne,col+1,nb_solutions);
		}
	    }
	  else if(tab[ligne][col].temp[k]!=0) // Si on n'en a pas trouvé
	    {
	      k++;
	      continuer=1;
	    }
	}
    }
  else // C'est une case base
    {
      if(col==8 && ligne==8)
	{                      // Si on est à la derniere case
	  (*nb_solutions)++;
	  return 1;
	}
 
 
      if(col<8)
	backtrack(tab,ligne,col+1,nb_solutions);
      else if(col==8)
	backtrack(tab,ligne+1,0,nb_solutions);
    }
}
 
 
 
/* Fonction qui verifie si (tab[ligne][col].valeur_case==valeur) est une valeur possible ou si elle est deja présente sur la ligne, colonne ou région */		      
 
char conflit(case_sudoku **tab,int ligne,int col,int valeur) {
 
  int i,x,y;
 
  // On vérifie d'abord pour la ligne
  for(i=0;i<9;i++) 
    {
      if(tab[ligne][i].valeur_case!=0) 
	{
	  if(i!=col)
	    {
	      if(tab[ligne][i].valeur_case==valeur)
		return 1;
	    }
	}
    }
 
  // On verifie maintenant pour la colonne
 
  for(i=0;i<9;i++) 
    {
      if(tab[i][col].valeur_case!=0)
	{
	  if(i!=ligne)
	    {
	      if(tab[i][col].valeur_case==valeur)
		return 1;
	    }
	}
    }
 
  // On verifie maintenant la région
 
  x=(ligne/3)*3;
  y=(col/3)*3;
 
  for(i=y;i<y+3;i++)  
    {
      if(tab[x][i].valeur_case!=0)
	{
	  if(i!=col || x!=ligne)
	    {
	      if(tab[x][i].valeur_case==valeur)
		return 1;
	    }
	}
    }
 
  for(i=y;i<y+3;i++)
    {
      if(tab[x+1][i].valeur_case!=0)
	{
	  if(i!=col || x+1!=ligne)
	    {
	      if(tab[x+1][i].valeur_case==valeur)
		return 1;
	    }
	}
    }
 
  for(i=y;i<y+3;i++)
    {
      if(tab[x+2][i].valeur_case!=0)
	{
	  if(i!=col || x+2!=ligne)
	    {
	      if(tab[x+2][i].valeur_case==valeur)
		return 1;
	    }
	} 
    }
 
  return 0;
}
 
/* Fonction booleenne qui verifie si une grille de sudoku est fini ou non :
   0 : fini
   1 : pas fini */    
 
char grille_resolu(case_sudoku **tab) {
 
    int i,j;
 
    for(i=0;i<9;i++)
      {
	for(j=0;j<9;j++)
	  if(tab[i][j].valeur_case==0) 
	    {
	      return 0;
	    }
      }
    return 1;
}

Une partie de mon code.

Ce que j'apelle "base" est une valeur de la grille qu'on ne peut pas modifier

**ToTo13** · 22/09/2008, 10h38

Bonjour,

c'est très d'avoir utilisé un débuggeur pour localiser l'erreur. Maintenant, si on pouvait connaître la ligne exacte ce serait mieux

.
Ensuite, met donc des petit printf ou assert afin de vérifier les différentes valeurs lors de l'exécution

.

**gnouz** · 22/09/2008, 13h00

En gros, je lance gdb avec ma souce compilé, et je fais un run, et je génère la grille jusqu'à que le programme plante avec un segmentation fault.

Il s'arrête à 4 lignes différentes, et j'ai déjà essayé de voir en mettant des printf mais j'avoue que même comme ça je ne vois pas du tout où est le probleme =/

Soit il s'arrête à :

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xb7d498c0 (LWP 11901)]
0x08049bc0 in backtrack (tab=0x8088b10, ligne=3, col=5,
nb_solutions=0xbf8e7768) at marche.c:481
481 if(conflit(tab,ligne,col,k)) // S'il y a un conflit, on relance la boucle

ou à :

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xb7d858c0 (LWP 11904)]
backtrack (tab=0x821a130, ligne=4, col=8, nb_solutions=0xbfbbca38)
at marche.c:434
434 int k=1,continuer=1,l;

ou :

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xb7ce08c0 (LWP 11907)]
conflit (tab=0x81175d0, ligne=4, col=5, valeur=1) at marche.c:532
532 for(i=0;i<9;i++)

ou enfin :

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xb7d458c0 (LWP 11911)]
0x08049de9 in conflit (tab=0x809f5a8, ligne=3, col=7, valeur=9) at marche.c:560
560 x=(ligne/3)*3;

**ToTo13** · 22/09/2008, 16h32

Bonjour,

un petit assert pour chacune des variables qui sont dans ces quelques lignes serait bien... Il y en a bien une qui générera une assertion.

**gnouz** · 22/09/2008, 17h41

Bonjour je n'utilise jamais la fonction assert, j'aimerais savoir l'avantage de assert par rapport aux printf?

Sinon pour l'utiliser, par exemple pour la première je tapes :

assert(ligne);
assert(col);
assert(*nb_solutions);

juste avant la ligne 481, c'est bien ça?

**méphistopheles** · 22/09/2008, 19h49

C'est tres C pour une conversation algorithmie tout ça

plus serieusement, tu devrais "découper" tes fonctions , certaines sont assez grosse et surtout les découper au niveau de la présentation, j'ai moi même eu la flemme de tout lire.

Sinon, ayant moi même programmé un générateur (et tout le shmilblick qui va avec) je te propose quelques grilles pour vérifier si ton solveur marche : la première est une grille soluble par la logique,la seconde est une grille type "diabolique" (on doit supposer des nombres pour la résoudre), Quand à la dernière, c'est le test ultime

:

/\

sinon, je regarderais bien ton code, mais là, j'ai la flemme

bonne chance

génération d'une grille de sudoku

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager