#include <stdio.h>
#include <stdlib.h>

#define SIZE 9

typedef int Grid[SIZE][SIZE];

/* verifie si la valeur est valide */
int check_case(Grid grid, int row, int col, int n)
{
  int i,j;
  int mini_row = row - row % 3;
  int mini_col = col - col % 3;
  if(grid[row][col] == n)
    return 1;
  if(grid[row][col] != 0)
    return 0;
  for(i = 0; i < SIZE; i++)
    if(grid[row][i] == n || grid[i][col] == n)
      return 0;
  for(i = mini_row; i < mini_row + 3; i++)
    for(j = mini_col; j < mini_col + 3; j++)
      if(grid[i][j] == n)
        return 0;
  return 1;
}

void grid_cpy(Grid dest, Grid src)
{
  int i,j;
  for(i = 0; i < SIZE; i++)
    for(j = 0; j < SIZE; j++)
      dest[i][j] = src[i][j];
}

/* resolution par backtracking */
void solve(Grid grid, int row, int col, Grid sol)
{
  if(row < SIZE)
  {
    int i;
    for(i = 1; i <= SIZE; i++)
    {
      if(check_case(grid, row, col, i))
      {
        int tmp = grid[row][col];
        grid[row][col] = i;

        if(col != SIZE - 1)
          solve(grid, row, col + 1, sol);
        else
          solve(grid, row + 1, 0, sol);
        
        grid[row][col] = tmp; /* on remet l'ancienne valeur */
      }
    }
  }
  else
    grid_cpy(sol, grid); /* on copie la solution (quand trouvée) avant
                            que l'ancienne valeur ne soit rétablie */
}

void get_grid(Grid grid)
{
  int i, j;
  for(i = 0; i < SIZE; i++, getchar())
    for(j = 0; j < SIZE; j++)
    {
      int tmp = getchar();
      grid[i][j] = tmp == ' ' ? 0 : tmp - '0';
    }
}

void print_grid(Grid grid)
{
  int i, j;
  for(i = 0; i < SIZE; i++, printf("\n"))
    for(j = 0; j < SIZE; j++)
      printf("%d", grid[i][j]);
  printf("\n");
}

int main(void)
{
  Grid grid, sol;

  get_grid(grid);
  print_grid(grid);
  solve(grid, 0, 0, sol);
  print_grid(sol);

  return EXIT_SUCCESS;  
}

~/Dropbox/Programming/C/sudoku$ ./a.out < grille1.txt 
900007100
000802070
570163000
005400936
001000200
326009800
000916083
060305000
003200001

932547168
614892375
578163429
785421936
491638257
326759814
247916583
169385742
853274691

#include <stdlib.h>
#include <stdio.h>

enum {
  M = 3,
  N = M * M,
  NxN = N * N
};

void printGrid(int * grid) {
  int i;
  
  for (i = 0; i < NxN; i++) {
    if (i != 0) {
      if (i % N == 0)
        putchar('\n');
      else if (i % M == 0)
        putchar(' ');
      if (i % (N * M) == 0)
        putchar('\n');
    }
    
    printf("%d ", grid[i]);
  }
  puts("");
  puts("-----------");
}

int isValid(int * grid, int n, int pos) {
  int i, j;
  int col, lin;
  
  col = pos % N;
  lin = pos / N;
  
  /* Line, column */
  for (i = 0; i < N; i++) {
    if (grid[lin * N + i] == n ||
        grid[i * N + col] == n)
      return 0;
  }
  
  /* case */
  col = (col / M) * M;
  lin = (lin / M) * M;
  
  for (i = 0; i < M; i++) {
    for (j = 0; j < M; j++) {
      if (grid[(lin + i) * N + (col + j)] == n)
        return 0;
    }
  }
  
  return 1;
}

int resolve(int * grid, int pos) {
  int i, tmp;
  
  if (pos >= NxN)
    return 1;
  if (grid[pos] != 0)
    return resolve(grid, pos + 1);
  
  for (i = 1; i <= N; i++) {
    if (isValid(grid, i, pos)) {
      grid[pos] = i;
      
      tmp = resolve(grid, pos + 1);
      if (tmp != 0)
        return tmp;
      
      grid[pos] = 0;
    }
  }
  
  return 0;
}

int main (void) {
  int grid[NxN] = { 0 };
  
  printGrid(grid);
  resolve(grid, 0);
  printGrid(grid);
  
  return EXIT_SUCCESS;
}