bonjour tout le monde,
est ce que quelquun pourai maider pour le calul de complexite d'un programme qui resout les sudoku ?
En fait je voudrais trouver un resultat generique( pour une grille n*n ).
merci bcp.
void vp(unsigned int lig, unsigned int col, unsigned int grille [9][9], bool t[9])
{
for(unsigned int i=0;i<9;i++)
{
if(grille [lig][i]!=0) t[grille[lig][i]-1]=false;
if(grille [i][col]!=0) t[grille[i][col]-1]=false;
}
unsigned int lg=0,cl=0;
if(lig<3) lg=0;
else if (lig<6) lg=3;
else lg=6;
if(col<3) cl=0;
else if (col<6) cl=3;
else cl=6;
for(unsigned int i=lg;i<lg+3;i++)
for(unsigned int j=cl;j<cl+3;j++)
if (grille [i][j]!=0) t[grille[i][j]-1]=false;
}
void resoudre(unsigned int grille[9][9])
{
bool ok=false;
unsigned int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
if(grille[i][j]==0) {ok=true;break;}
if(ok) break;
}
if(!ok) afficher(grille);
else
{
bool t[9];
for(unsigned int a=0;a<9;a++) t[a]=true;
vp(i,j,grille,t);
for(unsigned int k=0;k<9;k++)
{
if(t[k])
{
unsigned int grille2[9][9];
for(unsigned int ii=0;ii<9;ii++)
for(unsigned int jj=0;jj<9;jj++)
grille2[ii][jj]=grille[ii][jj];
grille2[i][j]=k+1;
resoudre(grille2);
}
}//fin parcours tableau valeurs
}// fin else
}
void afficher(unsigned int grille[9][9])
{
cout<<endl<<endl;
unsigned int a=0;
for(unsigned int i=0;i<9;i++)
{
for(unsigned int j=0;j<9;j++)
{
if (j==3 || j==6) cout<<" ";
if (i==a) {cout<<endl;a+=3;}
cout<<grille[i][j]<<" ";
}
cout<<endl;
}
}