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