/*Rempli directement la grille donnée en argument*/
int resolve(int grille[RG][RG])
{
  int grille_init[RG][RG];
  int i = 0;
  int j = 0;
  int first_i;
  int first_j;
   
  copier_tableau(grille,RG,grille_init);
  /*on cherche la première case vide*/
  while (grille_init[i][j] != 0)
    {
      if (j == 8) /*si on arrive à la dernière colonne....*/
        {
          j = 0;
          i++; /*...on passe à la ligne suivante*/
        }
      else
        j++;
    }
  first_i=i;
  first_j=j;

  /*on ne s'arrete pas tant que toutes les cases ne sont pas remplies*/
  while (i < RG)
    {
      while ( test(grille,i,j)==0)/*on incrémente la valeur de la case tant qu'une valeur ne vérifie pas le test*/
        grille[i][j]++;
              
      grille[i][j]++;/*on incrémente la valeur car dans le test, on teste pour la valeur au dessus*/
            
      /*CAS OU LA GRILLE EST IRRESOLVABLE*/
      if(i == first_i && j == first_j && grille[i][j]==10) /*si on est à la première case vide et qu'aucunes valeurs ne convient*/
        {                                                  /*alors la grille est irrésolvable*/
          return 1;
        }

   
      if (grille[i][j] == 10)/*cas où aucune valeur n'est possible*/
        {
          grille[i][j] = 0;/*on remet à 0 la case qui a atteint le max = 10*/
          if (j == 0)/*on revient à la case précedente*/
            {
              j = 8;
              i--;
            }
          else
            j--;
          
          while (grille_init[i][j] != 0)/*on recule tant que l'on tombe sur une case contenant un chiffre fixe*/
            {
              if (j == 0)
                {
                  j = 8;
                  i--;
                }
              else
                j--;
            }
          
        }
      else if (j == 8)/*si la valeur est < 10, on continue en passant à la case suivante*/
        {
          j = 0;
          i++;
        }
      else
        j++;
     
      while (grille_init[i][j] != 0) /*on cherche la prochaine case vide */
        {
          if (j == 8)
            {
              j = 0;
              i++;
            }
          else
            j++;
        }
    }
   return 0;
}

/*Teste si la valeur de la case est valable */
int test(int grille_test[RG][RG], int a, int b)
{
  int result = 1;/*1 => valable, 0 => impossible */
  int valeur = grille_test[a][b]+1;
  int k;
  int l;
  int m;

  /*coordonnées des carrés de coté 3 */
  int carre_x = a/3;
  int carre_y = b/3;

  for (k = 0; k < 9; k++)
    if(grille_test[a][k] == valeur || grille_test[k][b] == valeur)
      result=0;/*alors la valeur testee est deja sur la ligne ou la colonne*/
   
  if(result == 1)/*evite de faire le test ci dessous si on a deja prouver que la valeur n'était pas possible a placer*/
    {
      for (l = 0; l < 3; l++)
        for (m = 0; m < 3; m++)
          if(grille_test[carre_x * 3 + l][carre_y * 3 + m] == valeur)
            result = 0;/*alors la valeur testee est deja dans la region*/
    }
  return result;
}

void copier_tableau(int original[RG][RG], int rang,int copie[RG][RG])/*fait une copie du tableau passé en argument*/
{
  int c;
  int d;

  for (c = 0; c < rang; c++)
    for (d = 0; d < rang; d++)
      copie[c][d] = original[c][d];
}