Sudoku

/* Su-Doku solver */

#include <stdio.h>
#include <string.h>
#include <time.h>

#define MAX 9

struct _nextS
{
   int res ;
   int r ;
   int c ;
} nextS[MAX][MAX] ;

int s[MAX][MAX], o[MAX][MAX] ;
int n=3, N=9, nosolution,
   first_r, first_c ; /*first non-zero (row,col) with the least number of possible candidates */

void print(void)
{
   int i, j ;

   for (i=0; i<N; i++) {
      printf("%d", s[i][0]) ;
      for (j=1; j<N; j++)
         printf(" %d", s[i][j]) ;
      printf("\n") ;
   }

   printf("\n") ;
}

int canbefilled(int r, int c, int nextD)
{
   int ans, si, sj, i, j ;

   if (r>=0&&r<=2) si = 0 ;
   else if (r>=3&&r<=5) si = 3 ;
   else if (r>=6&&r<=8) si = 6 ;

   if (c>=0&&c<=2) sj = 0 ;
   else if (c>=3&&c<=5) sj = 3 ;
   else if (c>=6&&c<=8) sj = 6 ;

   ans = nextD ;

   for (i=0; i<N; i++)
      if (s[r][i] == nextD)
         ans=0 ;

   for (i=0; i<N; i++)
      if (s[i][c] == nextD)
         ans=0 ;

   for (i=si; i<si+n; i++)
      for (j=sj; j<sj+n; j++)
         if (s[i][j] == nextD)
            ans=0 ;

   return ans ;
}

int compute_possible_candidates(void)
{
   int i, j, nextD, k, min=10, d, ans=0 ;

   for (i=0; i<N; i++) {
      for (j=0; j<N; j++) {
         if (o[i][j]==0) {
            k = 0 ;
            for (nextD=1; nextD<=9; nextD++) {
               if (canbefilled(i, j, nextD)) {
                  d = nextD ;
                  k++ ;
               }
            }

            if (k==1) {
               o[i][j] = d ;
               s[i][j] = d ;
               ans = 1 ;
            }
            else if (k<min) {
               min = k ;
               first_r = i ;
               first_c = j ;
            }
         }
      }
   }

   return ans ;
}

/* Return the next square which is not originally filled */
int getnext(int *nr, int*nc)
{
   int r, c ;

   if (*nc==N) {
      *nr = *nr+1 ;
      *nc=0 ;
   }

   if (*nr==N)
      *nr=0 ;

   for (r=*nr; r<N; r++) {
      for (c=*nc; c<N; c++)
         if (o[r][c]==0)
         {
            *nr = r ;
            *nc = c ;
            return 1 ;
         }
      *nc = 0 ;
   }

   for (r=0; r<N; r++) {
      for (c=0; c<N; c++)
         if (o[r][c]==0)
         {
            *nr = r ;
            *nc = c ;
            return 1 ;
         }
      *nc = 0 ;
   }

   return 0 ;
}

int nf ;
int fillpos(int r, int c)
{
   int i, j, ans, nextD, nr, nc ;
   nf++ ;
   do {
      for (nextD=(s[r][c]?s[r][c]:1); nextD<=N; nextD++)
         if (canbefilled(r, c, nextD)) {
            s[r][c] = nextD ;
            break ;
         }

      if (nextD>N) {
         if (r==first_r && c==first_c) {
         /* We tried everything, backtracking every path.
            Now even first_r,first_c can't be filled */
            nosolution = 1 ;
            return 1 ;
         }
         s[r][c] = 0 ;
         return 0 ;
      }

      if (nextS[r][c].res==0)
         return 1 ;
      else {
         nr = nextS[r][c].r ;
         nc = nextS[r][c].c ;
      }

      ans = fillpos(nr, nc) ;
   }
   while (!ans);

   return 1 ;
}

int main()
{
   int i, j, a, b, cases ;

   freopen("sudoku.in", "r", stdin) ;
   freopen("sudoku.out", "w", stdout) ;

   scanf("%d", &cases) ;
   while (cases--) {
      for (i=0; i<N; i++)
         for (j=0; j<N; j++) {
            scanf("%d", &s[i][j]) ;
            o[i][j] = s[i][j] ;
            nextS[i][j].res = 0 ;
         }

      first_r = first_c = 0 ;
      while (compute_possible_candidates()) ;

      i = first_r ;
      j = first_c ;
      a = first_r ;
      b = first_c + 1 ;
      while (getnext(&a, &b)) {
         if (a==first_r && b==first_c)
            break ;

         nextS[i][j].res = 1 ;
         nextS[i][j].r = a ;
         nextS[i][j].c = b ;
         i = a ;
         j = b ;
         b = b+1 ;
      }

      a = first_r ;
      b = first_c ;
      nosolution = 0 ;
      if (getnext(&a, &b))
         fillpos(a, b) ;
      if (nosolution)
         printf("NO SOLUTION\n") ;
      else print() ;
   }

   return 0;
}

/* sudoku.in */

1

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