génération d'une grille de sudoku

Version imprimable

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:

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

22/09/2008, 10h38
ToTo13

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 ;).
22/09/2008, 13h00
gnouz

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;
22/09/2008, 16h32
ToTo13

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.
22/09/2008, 17h41
gnouz

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?
22/09/2008, 19h49
méphistopheles

3 pièce(s) jointe(s)

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

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 :aie::
http://www.developpez.net/forums/att...1&d=1222105564 /\ http://www.developpez.net/forums/att...1&d=1222105551 /\ http://www.developpez.net/forums/att...1&d=1222105543

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

bonne chance;)
23/09/2008, 02h02
gnouz

Alors les deux premières grilles sont résolues parfaitement mais pas la derniere =/

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

Donc mon solveur marche pas bien? A quel niveau, car je ne vois pas vraiment..

merci
23/09/2008, 15h27
ToTo13

Bonjour,

le assert fonctionne comme un if en C. Donc => assert(mon test) ;
Par exemple : assert (tab != null) ;
C'est une fonction indispensable lorsque l'on fait des allocations dynamiques.
L'avantage est de ne pas avoir d'affichage monstrueux lors de l'exécution et ça stoppe le programme.
23/09/2008, 19h52
PhDt76

Bonjour à tous,

J'ai aussi réalisé un solveur de Sudoku, et en essayant le test ultime proposé par Méphistopheles, mon algo me signale plus de retour arrière possible après avoir essayé les possibilités de 1 à 9 sur la case (0, 0)

La grille ne serait elle pas tout simplement impossible ou bien est ce mon algo qui est faut . . .

Oui, je fais du backtrack pour l'instant, je cherche une méthode plus "intelligente" mais les trois techniques que j'ai mises au point ne me suffisent pas pour résoudre toutes les grilles.
23/09/2008, 20h04
méphistopheles

effectivement :D c'est une grille impossible et si ton algo ne plante pas, c'est qu'il est bien fait :p

en effet, il n'est possible de se rendre compte que cette grille est imposible.... qu'après plusieurs dizaines de millier d'itération :aie: (j'ai eu du mal à la fabriquer)

cette grille est totalement inaccessible à un humain bien sûr :p

toutefois, ce test permet de voir que ton algo de base a un gros bug...

je veut bien le regarder en details, mais pourrais-tu le découper en fonctions (postées entre des balises code différentes) et avec des commentaires externes ?

merci ;)

Edit: pour une resolution logique, ce site est de loin le meilleur. pour ma part, mon solveur n'utilise que les methodes de résolutions A,B et C (en même temps, ce site n'existait pas à l'époque) + un backtrack (bien sûr).

Plus votre résolution est logique, plus elle est perfomante !

Très bien, alors :

Ma structure case_sudoku qui définit comme son nom l'indique une case d'une grille de sudoku, le tableau temp est le tableau des possibilités de la case on utilise que les cases de 1 à 10, lorsque l'on aura testé la valeur 1 d'une case x, on mets 1 à la case 1, si on teste la valeur 4, on mettra 1 à la valeur 4 etc..

valeur_case est la valeur que contiendra la case

base, est un booleen qui indique si la case est une case "base", c'est à dire si c'est un élement inmodifiable de la grille.

Code:

1
2
3
4
5
6
7
8
 
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;

Ma fonction de backtracking qui prend en paramètre un tableau à deux dimensions de type case_sudoku, le numéro de ligne, de colonne, et un pointeur nb_solutions vers un int, (on incrementera *nb_solutions à chaque fois que l'on passera par la case [8][8] (la derniere case du sudoku)

On traite toutes les cases de la grille case par case et ligne par ligne.
Si la case à traiter n'est pas une case "base", donc une case modifiable, on va tester toutes les valeurs possibles sur cette case, on vérifie à chaque fois grâçe à la fonction conflit si la valeur est possible.
Si elle l'est, on passe à la case suivante, sinon on recule jusqu'à la derniere case "non base".

Code:

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
 
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);
    }
}

Cette fonction sert à indiquer sur une valeur d'une case de la grille est possible ou non, en verifiant si la valeur est présente sur la ligne, colonne, région.

Si elle l'est, alors on renvoie 1, sinon on renvoie 0.

Code:

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
 
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;
}

Merci d'avance.

p.s : toto13> je suis en train de lire une documentation sur la fonction assert, je ne connaissais pas du tout, si ça peut m'aider à debugguer plus facilement mes programmes c'est interessant.
D'habitude je debuggue tout depuis le main, mais là c'est une fonction par backtracking donc il peut y avoir des milliers de retour en arriere, c'est très long.

ouille, tres bizarre ton code... déjà, je trouve curieux que tu n'utilise pas le plus avantageux principe de la récursion dans ton code: une fonction ne s'arrête pas lorsqu'elle s'appelle elle même (enfin elle continue lorsque son propre appel s'est terminé).
Ce qui veut dire que plutot que d'appeller des backtrack à la ligne d'en dessous (ce qui est catastrophique d'un point de vue de performances et douteux au niveau de la sûreté), tu peut ne faire des appel que dans un sens !

D'ailleurs, j'ai du mal à comprendre comment ton backtrack fonctionne:
supposons le parcourt suivant : je fait un appel sur la case 1,1 de backtrack, la grille est vide !
Code:

1 2 3 4 5 6 7 8 9 10 11 12 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 */ { [...] }
bon ici, on ne rentre pas dans les détails, c'est le premier appel, on a toutes les valeurs possibles.
Continuons:
Code:

1 2 3 4 5 6 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;
Jusque-là, ça va, pas de problèmes
Code:

1 2 3 4 5 if(conflit(tab,ligne,col,k)) /* S'il y a un conflit, on relance la boucle */ { [...] }
on n'a pas encore de conflicts, là, la grille est vide
Code:

1 2 3 4 else /* S'il n'y a pas de conflit on sort de la boucle et on passe à la case suivante */ { continuer=0;
BON, là tu arrete la boucle avec ça et c'est justement le problème car:
Code:

1 2 3 4 5 6 if(col==8 && ligne==8) { (*nb_solutions)++; return 1; }
Cette instruction n'est éviddement pas executée, on est dans la case 1,1
Code:

1 2 3 4 5 6 if(col==8) backtrack(tab,ligne+1,0,nb_solutions); else backtrack(tab,ligne,col+1,nb_solutions); }
Bon, Tres bien tu réappell tes fonctions mais... il se passe quoi lorsque celles-ci ont fait leurs returns (lorsqu'elles se sont arrétées) ?
Code:

1 2 3 4 5 6 } else if(tab[ligne][col].temp[k]!=0) /* Si on n'en a pas trouvé */ { [...] }
ON sort du "If"
Code:

1 2 }
On sort de la boucle
Code:

1 2 3 4 5 6 } else /* C'est une case base */ { [...] }
On sort du dernier if
Code:

1 2 }
et on arrive à la fin de la fonction sans avoir fait un seul return .... normalement, tu devrais avoir un gros bug...

Et je n'ai regardé que la partie la plus simple du code: tu manque vraiment d'une conception de ton code et d'une clarté de ton algorithme .... essaye de diviser tout ça en plusieurs fonction, ce sera déjà mieux...

D'autre part, même si cela marchait, ton code pourrait passer des années à résoudre des problèmes simple: la puissance de ton PC est limitée, économise là, d'autant plus que la génération de sudockus est bien plus gourmande en ressources que leur résolution. D'ailleurs, si tu regarde le site que j'ai mis en lien dans mon précédent post, leur programme tourne à une vitesse ahurissante et en Javascript sur compilateur car ils utilisent principalement des méthodes logiques et le backtrack en dernier ressort.

Je veut bien continuer, mais essaye de rendre ton code plus corrigible, par-ce que comme ça, nous mettrons des millions d'années à le corriger...

bonne chance néamoins (tu en aura besoin):aie:

24/09/2008, 12h47
gnouz

j'avoue avoir un peu de mal à comprendre comment procéder autrement (sans les rappels à la fonction backtrack), et pas trop compris non plus où etait l'erreur, car dans tous les cas on a soit un return si on est à la derniere case et qu'on s'apprêtait à avancer, ou un à la première case et qu'on s'apprêtait à reculer.
Le reste des cas est un appel à backtrack pour avancer/reculer dans la matrice.

Je crois que pour vraiment comprendre d'où vient mon erreur je vais charger la grille impossible que tu as posté avant, et debugguer le programme ligne par ligne (ça risque d'être très long mais bon), j"espere que ça m'aidera à comprendre mon erreur.

J'ai appliqué l'idée de l'algorithme classique : parcourir toutes les cases, si la case actuelle est une base, appeler backtrack avec la case suivante, si ce n'en est pas une, tester les valeurs une par une, si l'une d'entre elle marche, appeler backtrack avec la case suivante, sinon appeler backtrack avec la premiere case non base d'avant.

Soit 3 appels différents à la fonction backtrack mais *2 car il faut gerer les cas où la case actuelle est au bout de la ligne, donc appeler backtrack avec la ligne suivante et la colonne à 0.
Donc au total 6 appels à backtrack.

Mais j'ai appliqué l'algorithme du backtracking tel quelle, je sais qu'il y a des methodes pour résoudre une grille qui sont beaucoup plus performante au niveau du temps de calcul en appliquant des principes plus "naturelles" tels que les paires nues, les triplets etc, mais là j'ai voulu appliquer cette méthode pour bien la comprendre, puis plus tard utiliser cette méthode plus naturelle.

Donc je ne vois pas trop comment diminuer les appels à la fonction backtrack tout en respectant l'algorithme du backtracking.
Si vous pourriez m'éclairer ça serait sympa.

Merci d'avance, c'est vrai que je débute mais je suis très motivé pour apprendre et progresser.

Désolé pour les eventuelles fautes d'ortographe, un peu fatigué en ce moment...
24/09/2008, 13h30
pseudocode

Citation:

Envoyé par gnouz

Donc je ne vois pas trop comment diminuer les appels à la fonction backtrack tout en respectant l'algorithme du backtracking.

Il faut faire alterner backtracking et élagage des possibilités restantes. En fait, c'est un problème de couverture exacte dans une matrice 729×324. A chaque choix d'une ligne de la matrice, on supprime entre 0 et 24 autres lignes.

http://en.wikipedia.org/wiki/Exact_cover#Sudoku

Citation:

Envoyé par gnouz

[...] pas trop compris non plus où etait l'erreur, car dans tous les cas on a soit un return si on est à la derniere case et qu'on s'apprêtait à avancer, ou un à la première case et qu'on s'apprêtait à reculer.[...]

Le problème est justement que tu n'a pas compris le problème de la récursion : lorsqu'une fonction s'apelle elle même, elle n'est pas arrétée : c'est comme si tu appelait une autre fonction qui fait exactement la même chose.

ça reviiendrait un peu à faire:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 fonction1(paramètres){ fonction1(paramètres){ fonction1(paramètres){ fonction1(paramètres){ ... return resulatat } return resulatat } return resulatat } return resulatat }
En effet, on ne sort normalement du'une fonction à parmètres que sur un return... et dans ton cas, il arrive souvent que tu sorte sans...ce qui peut provoquer pas mal d'erreur.

D'autre part, l'interet des fonctions récursive est principalement de recevoir le résultat d'un certains nombre d'oppération inconnu.
alors que la menière dont tu utilise la fonction pourrais revenire à boucler sur chacune des cases ...:?

Bref, COnceptualise avant d'écrire... et demande toi comment obtenir le plus de preformances avec le moins de code possible à écrire

Bonne chance;)

Si ca peut aider, j'ai remis au propre mon implémentation Java avec backtracking en itératif.

Code:

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
 
/**
 * Sudoku solver (exploration + backtracking)
 * 
 * @author Xavier PHILIPPEAU
 */
public class SudokuSolver {
 
	// Sudoku size K=square size, N=grid size (N=K*K)
	private final int K, N;
 
	// the grid to solve 
	private int[][] solution;
 
	// marker for the initial (fixed) values
	private boolean[][] fixed;
 
	// locks on the rows, columns and squares
	private boolean[][] lockrow, lockcol, locksqr;
 
	// constructor
	public SudokuSolver(int K) {
		this.K        = K;
		this.N        = K*K;
	}
 
	// initialize/reset structures
	private void initialize() {
		this.solution = new int[N][N];
		this.fixed    = new boolean[N][N];
		this.lockrow  = new boolean[N][N];
		this.lockcol  = new boolean[N][N];
		this.locksqr  = new boolean[N][N];
	}
 
	// load initial grid
	private void load(String grid) {
		for(int i=0;i<grid.length();i++) {
			char c = grid.charAt(i);
			int row = i/N, col = i%N, val = c-'0';
			if (c=='.') continue;
			solution[row][col]=val;
			fixed[row][col]=true;
			setlock(row,col,val, true);
		}	
	}
 
	// set/unset locks for the tuple (row,col,value)
	private void setlock(int row, int col, int val, boolean state) {
		int sqr=(col/this.K)+this.K*(row/this.K);
		this.lockrow[row][val-1]=state;
		this.lockcol[col][val-1]=state;
		this.locksqr[sqr][val-1]=state;	
	}
 
	// check if a tuple (row,col,value) is locked
	private boolean islocked(int row, int col, int val) {
		if (this.lockrow[row][val-1]) return true;
		if (this.lockcol[col][val-1]) return true;
		int sqr=(col/this.K)+this.K*(row/this.K);
		if (this.locksqr[sqr][val-1]) return true;
		return false;
	}
 
	// print grid
	private void print() {
		StringBuffer sb = new StringBuffer();
		for(int r=0;r<N;r++) {
			for(int c=0;c<N;c++)
				sb.append( (solution[r][c]==0)?".":solution[r][c] ).append(" ");
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
 
	// solver
	public void solve(String grid) {
		// init structures
		initialize();
 
		// load and print initial grid
		load(grid);
		print();
 
		boolean backtrack=false;
		int position=0;
 
		// complete tree exploration with backtracking
		while(position>=0 && position<N*N) {
			int row = position/N;
			int col = position%N;
 
			// fixed cell : skip  and continue
			if (fixed[row][col]) {
				if (backtrack) position--; else position++;
				continue;
			}
 
			// remove the previous lock (if any)
			if (solution[row][col]>0) setlock(row,col,solution[row][col], false);
 
			// lookup for a possible value
			int val = solution[row][col]+1;
			while(val<=N && islocked(row,col,val)) val++;
 
			if (val<=N) {
				// value found: add to current solution
				solution[row][col]=val;
				// set the lock
				setlock(row,col,val, true); 
				// go next
				backtrack=false;
				position++;
			} else {
				// no value found: backtrack
				solution[row][col]=0;
				// go previous
				backtrack=true;
				position--;
			}
 
			// end loop
		}
 
		// exited the loop while backtracking => no solution.
		if (position<0) {
			System.out.println("no solution");
			return;
		}
 
		// else it'ok => print solution.
		print();
	}
 
}

Un petit exemple d'utilisation:

Code:

1
2
3
4
5
6
7
8
9
10
 
public static void main(String[] args) {
	long t0=System.currentTimeMillis();
 
	String grid = "1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1";
	new SudokuSolver(3).solve(grid);
 
	long t1=System.currentTimeMillis();
	System.out.println("duration: "+(t1-t0)+"ms");
}

Ce qui nous donne:

Citation:

1 . . . . . . . 2
. 9 . 4 . . . 5 .
. . 6 . . . 7 . .
. 5 . 9 . 3 . . .
. . . . 7 . . . .
. . . 8 5 . . 4 .
7 . . . . . 6 . .
. 3 . . . 9 . 8 .
. . 2 . . . . . 1

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

duration: 140ms

je suis en train de m'orienter finalement vers une solution itérative vu que je ne suis pas encore très à l'aise avec le recursif.

Code:

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
 
/* 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;
 
  while(ligne<8)
    {
      ligne++;
      col=0;
      while(col<9)
	{
	  k=1;
	  continuer=1;
	  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=0;
		      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--;
			    }
			  ligne--;  /* reculer avec la derniere case non base */
			}
		      else
			{
			  col--;
			  while(tab[ligne][col].base==1)
			    {
			      if(col==0 && ligne==0)
				return 0;
			      if(col==0) 
				{
				  ligne--;
				  col=9;
				}
			      col--;
			    }
			}
		    } // fin du if(k<9)
 
		  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;
			  col++;
			}
		    }
		  else if(tab[ligne][col].temp[k]!=0) /* Si on n'en a pas trouvé */
		    {
		      k++;
		      continuer=1;
		    }
		} // fin du while(continuer)
	    } // fin du si ce n'est pas une base
	  else /* C'est une case base */
	    {
	      col++;
	    }
	} // fin du while(col<9)
    } // fin du while(ligne<9)
  (*nb_solutions)++;
  return 1;
}

Maintenant tout fonctionne parfaitement (:

Bon j'aimerais maintenant améliorer la performance de mon algo de résolution et j'ai entendu dire que la méthode des "dancing links" est la plus efficace.

C'est vrai?