algorithmique de fonction rec

Question

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

yann_lo_san · Answer

Juste une petite remarque, si tu avais plus de 2 boucles imbriquées, le if(ok) break; serait une redondance extrème.

bool ok=false;
for(i=0; i<9 && !ok; i++)
{
     for(j=0; j<9; j++)
          if(grille[i][j]==0) {ok=true; break;}
     // if(ok) break;
}

Algorithmique de fonction rec

1 réponse

Votre réponse

Discussions similaires