tout le monde,j'ai essayé de mettre en oeuvre le solveur de SuDoKu basé sur le principe du BackTracking,mais j'ai decouvert que pour certaines combinaisons provoquent une boucle infinie. J'ai essayé de comprendre qu'est ce qui ne va pas dans mon algorithme mais sans resultat.
Voici une partie du 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
112
 
 
typedef struct
                  {
	         int lg; // La ligne vide
	         int cl; // Colonne vide
	      }Case;
 
Case Tabr[81]; // Contiendra les emplacements vides de la matrice
 
int remp_matr_zero(int Mat[][9])
{
   int i,j;
 
   for(i=0;i<9;i++)
       for(j=0;j<9;j++)
          Mat[i][j]=0; /* Remplissage de la matrice par des 0 */
 
  return 0;
}
 
int Position_Case_Vide(int Mat[][9],Case Tabv[])
{
  int i,j,n=0;
 
   for(i=0;i<9;i++)
	for(j=0;j<9;j++)
	  if(!Mat[i][j])
	    {
		Tabv[n].lg=i;    /* Enregistre la ligne de la case vide */
		Tabv[n++].cl=j;/* Enregistre la colonne de la case vide*/
	    }
   return n;   /* Retourne le nombre de cases vides */
}
 
int Verification(int Mat[][9],int i,int j,int x,int y,int element)
{
 
  int k,a,b,existe=0;
 
 
  for(k=0;k<9&&!existe;k++)                       // teste sur la ligne
          if( element==Mat[i][k] &&j!=k )
	    existe=1;
 
  for(k=0;k<9&&!existe;k++)                     //  teste sur la colonne
          if( element==Mat[k][j] &&i!=k )
	    exist=1;
 
   for(a=x;a<x+3&&!existe;a++)                   //  teste sur la region
	for(b=y;b<y+3&&!existe;b++)
	    if( element==Mat[a][b] && (a!=i||b!=j) )
	       existe=1;
 
 return existe; /* Retourne 1 si l'element existe , Sinon 0*/
}
 
int Possibilite(int Mat[][9],int i,int j,int T[]) /* Stocke toutes les possiblites
                                                              dans le tableau T[] */ 
{
   int k,x,y,n=0;
 
	x=i/3*3;
	y=j/3*3;
 
	for(k=1;k<10;k++)
	 if( !Verification(Mat,i,j,x,y,k) )
	   T[n++]=k;
 
	return n; /* Retourne le nombre de possbilités */
}
 
 
 
int Solution(int Mat[][9],Case Tab[],int N,int i) /* Fonction de Backtracking */
{
  int T[9],j,n;
 
	 if(i<N)
	 {
 
	   n=Possibilite(Mat,Tab[i].lg,Tab[i].cl,T); /* n contient le nombre 
                                                                        de possibilités */
 
	   j=0;
	   while(j<n)
	   {
		  Mat[Tab[i].lg][Tab[i].cl]=T[j++]; /* On stocke une 
                                                                          possbilité dans la 
                                                                          matrice 
                                                                         */
 
		  if( Solution(Mat,Tab,N,i+1) )       /* Appel recurrsif de la 
                                                                             fct solution pour i+1
                                                                        */ 
		   return 1;
 
	   }
	   Mat[Tab[i].lg][Tab[i].cl]=0;
	   return 0;
 
	 }
	 else
	 {
	   trouve=1; /* On a trouvé une solution , trouve est utile pour 
                                 afficher plusieurs solutions */
 
		 Affichage_martice(Mat); /* Fct d'afficage de la matrice */
	   return 0;
 
	 }
}
Le probleme est pour une combinaison comme celle-ci :

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


Cela donne une boucle infinie .

Je me suis dit ke je dois mettre un compteur pour les appels de la fct Solution() afin de stopper l'execution s'il depasse un nombre MAX d'appels,par exemple MAX=1000 ,mais cela ne me parrait pas logique...


Merci de m'aider,vos suggestions sont la bienvenue.

Bonne chance ^^ .