RÉSOLUTION SUDOKU (9X9) PAR BACKTRACKING RÉCURSIF INTELLIGENT

/*
** solve_grid.c for  in /home/guicqu_g/projets/c/sudoki-bi
** 
** Made by gallien guicquero
** Login   <guicqu_g@epitech.net>
** 
** Started on  Fri Apr 23 20:17:34 2010 gallien guicquero
** Last update Sat May 14 20:36:01 2011 gallien guicquero
*/

int     solve_grid(char grid[9][9], int row, int col);

/*
**      Check si la grille est complete
*/

int     end_grid(char grid[9][9])
{
  int   row;
  int   col;

  row = 9;
  while (--row >= 0)
    {
      col = 9;
      while (--col >= 0)
        {
          if (!grid[row][col])
            return (0);
        }
    }
  return (1);
}

/*
**      Elimine les chiffres deja present sur la ligne, la colonne puis le carre
*/

void    solve_grid_find(char grid[9][9], char vacant[9], int row, int col)
{
  int   i;
  int   j;

  i = -1;
  while (++i < 9)
    {
      if (grid[row][i])
        vacant[(int)(grid[row][i]) - 1] = 0;
      if (grid[i][col])
        vacant[(int)(grid[i][col]) - 1] = 0;
    }
  row -= row % 3;
  col -= col % 3;
  i = row - 1;
  while (++i < row + 3)
    {
      j = col - 1;
      while (++j < col + 3)
        if (grid[i][j])
          vacant[(int)(grid[i][j]) - 1] = 0;
    }
}

/*
**      Essaye de completer la grille
*/

int     solve_grid_fill(char grid[9][9], int row, int col)
{
  char  vacant[9];
  int   test;
  int   save;

  test = -1;
  while (++test < 9)
    vacant[test] = test + 1;
  solve_grid_find(grid, vacant, row, col);
  test = -1;
  while (++test < 9)
    {
      if (vacant[test])
        {
          save = grid[row][col];
          grid[row][col] = vacant[test];
          solve_grid(grid, row, col + 1);
          if (end_grid(grid))
            return (0);
          grid[row][col] = save;
        }
    }
  return (0);
}

/*
**      Parcours la grille a la recherche d'une case a completer
*/

int     solve_grid(char grid[9][9], int row, int col)
{
  while (row < 9)
    {
      while (col < 9)
        {
          if (!grid[row][col])
            return (solve_grid_fill(grid, row, col));
          ++col;
        }
      col = 0;
      ++row;
    }
  return (0);
}