Hi,
Here is the code to solve su-do-kus. These things are popping up in almost every newspaper here. This program is not at all perfect. If you find any bug or any improvement please leave a comment. It is divided into two part. One that solves it deterministically and other non-deterministically.

I know that deterministic part is not complete. You can still fill some slots deterministically. But current code is adequate to solve all the puzzles only thing is it will inspect more states than necessary.

Worst thing about this program is that you have to hard-code the input and that takes a lot of time. I am planning to create a Qt or GTK frontend for it just to get acquainted with these frontends.

Here is the code:

void print_state(char state[9][9])
{
 int x, y;
 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   printf("%d ", state[x][y]); 
  }
  printf("\n");
 }
 printf("\n");
}
int check_possibilities(char state[9][9], char possibilities[9], int x, int y)
{
 int ret = 0;
 int i, j, sq_x, sq_y;
 int temp_poss[9] = {1, 1, 1, 1, 1, 1, 1, 1, 1};
 if(state[x][y] || x>8 || y>8)
  return  -1;

 sq_x = (x/3) * 3; 
 sq_y = (y/3) * 3;

 for(i = sq_x; i < sq_x + 3; i++)
  for(j = sq_y; j < sq_y + 3; j++)
   temp_poss[state[i][j]-1] = 0;

 for(i = 0; i < 9; i++){
  temp_poss[state[i][y]-1] = 0;
  temp_poss[state[x][i]-1] = 0;
 }

 for(i = 0; i < 9; i++){
  if(temp_poss[i]){
   possibilities[ret] = i+1;
   ret++;
  }
 }
 return ret;
}

/* Returns 1 if found atleast one correct slot. (solve deterministically again)
   Returns 0 if no correct spot is found. (solve non-deterministically)
   Returns -1 if there is an error, i.e. found a spot with no 
    possibilities. (backtrack) */
int solve_deterministic(char state[9][9])
{
 char poss[9];
 int x, y;
 int num_pos;
 int ret = 0;
 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   num_pos = check_possibilities(state, poss, x, y);
   if(num_pos == 1){
    state[x][y] = poss[0];
    ret = 1;
   }
   if(!num_pos)
    return -1;
  }
 }
 return ret;
}

int solved(char state[9][9]){

 int x, y;
 int done = 1;
 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   if(!state[x][y]){
    done = 0;
    break;
   }
  }
  if(!done) break;
 }
 
 if(done)
  return 1;
 
 return 0;
}

int solve(char state[9][9])
{
 int det_sol = 0;
 int x, y, i;
 char poss[9];
 int num_pos;
 int done = 1;
 char new_state[9][9];
 

 while(det_sol = solve_deterministic(state)){
  if(det_sol == -1)
   return 0;
 }
 if(solved(state)){
  print_state(state);
  return 1;
 }

 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   memcpy(new_state, state, sizeof(new_state));
   num_pos = check_possibilities(state, poss, x, y);
   
   for(i = 0; i < num_pos; i++){
    new_state[x][y] = poss[i];
    if(solve(new_state) == 1){
     return 1;
    }
    new_state[x][y] = 0; 
   }  
  }
 }

 return 0; 
}
int main()
{
 char init_state[9][9] = {0, 0, 6,  0, 5, 0,  0, 8, 0,
     5, 7, 0,  3, 0, 2,  0, 6, 0, 
     0, 0, 2,  4, 0, 0,  3, 0, 9, 

     0, 9, 0,  5, 0, 4,  1, 3, 0,
     7, 0, 0,  0, 0, 0,  0, 0, 4,
     0, 4, 1,  7, 0, 8,  0, 2, 0,

     9, 0, 3,  0, 0, 5,  2, 0, 0, 
     0, 1, 0,  2, 0, 9,  0, 4, 5, 
     0, 5, 0,  0, 6, 0,  9, 0, 0};

 print_state(init_state);
 if(solve(init_state)){
  printf("solved\n");
  return 0;
 } else {
  printf("cannot solve\n");
  return 1;
 }
}

-------------------------------------------------------------------
Yours Sincerely,

void print_state(char state[9][9])
{
 int x, y;
 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   printf("%d ", state[x][y]); 
  }
  printf("\n");
 }
 printf("\n");
}
int check_possibilities(char state[9][9], char possibilities[9], int x, int y)
{
 int ret = 0;
 int i, j, sq_x, sq_y;
 int temp_poss[9] = {1, 1, 1, 1, 1, 1, 1, 1, 1};
 if(state[x][y] || x>8 || y>8)
  return  -1;

 sq_x = (x/3) * 3; 
 sq_y = (y/3) * 3;

 for(i = sq_x; i < sq_x + 3; i++)
  for(j = sq_y; j < sq_y + 3; j++)
   temp_poss[state[i][j]-1] = 0;

 for(i = 0; i < 9; i++){
  temp_poss[state[i][y]-1] = 0;
  temp_poss[state[x][i]-1] = 0;
 }

 for(i = 0; i < 9; i++){
  if(temp_poss[i]){
   possibilities[ret] = i+1;
   ret++;
  }
 }
 return ret;
}

/* Returns 1 if found atleast one correct slot. (solve deterministically again)
   Returns 0 if no correct spot is found. (solve non-deterministically)
   Returns -1 if there is an error, i.e. found a spot with no 
    possibilities. (backtrack) */
int solve_deterministic(char state[9][9])
{
 char poss[9];
 int x, y;
 int num_pos;
 int ret = 0;
 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   num_pos = check_possibilities(state, poss, x, y);
   if(num_pos == 1){
    state[x][y] = poss[0];
    ret = 1;
   }
   if(!num_pos)
    return -1;
  }
 }
 return ret;
}

int solved(char state[9][9]){

 int x, y;
 int done = 1;
 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   if(!state[x][y]){
    done = 0;
    break;
   }
  }
  if(!done) break;
 }
 
 if(done)
  return 1;
 
 return 0;
}

int solve(char state[9][9])
{
 int det_sol = 0;
 int x, y, i;
 char poss[9];
 int num_pos;
 int done = 1;
 char new_state[9][9];
 

 while(det_sol = solve_deterministic(state)){
  if(det_sol == -1)
   return 0;
 }
 if(solved(state)){
  print_state(state);
  return 1;
 }

 for(x = 0; x < 9; x++){
  for(y = 0; y < 9; y++){
   memcpy(new_state, state, sizeof(new_state));
   num_pos = check_possibilities(state, poss, x, y);
   
   for(i = 0; i < num_pos; i++){
    new_state[x][y] = poss[i];
    if(solve(new_state) == 1){
     return 1;
    }
    new_state[x][y] = 0; 
   }  
  }
 }

 return 0; 
}
int main()
{
 char init_state[9][9] = {0, 0, 6,  0, 5, 0,  0, 8, 0,
     5, 7, 0,  3, 0, 2,  0, 6, 0, 
     0, 0, 2,  4, 0, 0,  3, 0, 9, 

     0, 9, 0,  5, 0, 4,  1, 3, 0,
     7, 0, 0,  0, 0, 0,  0, 0, 4,
     0, 4, 1,  7, 0, 8,  0, 2, 0,

     9, 0, 3,  0, 0, 5,  2, 0, 0, 
     0, 1, 0,  2, 0, 9,  0, 4, 5, 
     0, 5, 0,  0, 6, 0,  9, 0, 0};

 print_state(init_state);
 if(solve(init_state)){
  printf("solved\n");
  return 0;
 } else {
  printf("cannot solve\n");
  return 1;
 }
}