#include <stdio.h>
long long int counter, tt;
int permutation[10][400000][10];
int n; int a[100];
int b[10][10];   // Board for sudoku
int cand[10][10]; // cand[i][*]: candidates for row i
int size[10];  // size[i]: size of the i-th candidate list
int pos[10][10]; // pos[i][*]: candidate positions for row i
out1(){int i, j;  // Solution is output
  printf("Solution time= %lld millisec\n", (clock()-tt)/1000);
  for(i=1;i<=9;i++){
    for(j=1;j<=9;j++)printf("%d ", b[i][j]);
    printf("\n");
  }
}
int factorial(int n){int i, s;  //n! is computed
  s=1; for(i=1;i<=n;i++)s=i*s; return s;
}
/*** a permutation is output for row i as the counter-th permutation ***/
out(int i, int a[], int n){
int j;
  counter++;
  for(j=1;j<=n;j++)permutation[i][counter][j]= a[j];
}
/*** permutation generation in lexic-graphic order ***/
swap(int a[], int i, int j){
int w;
  w=a[i]; a[i]=a[j]; a[j]=w;
}
reverse(int a[], int k, int n){
int i;
  for(i=k;i<=(k+n-1)/2;i++)swap(a, i, n-i+k);
}
int minimum(int a[], int k, int n){
int i,j,temp;
  j=0; temp=99;
  for(i=k;i<=n;i++){
    if ((a[i]<temp) && (a[i]>a[k-1])){ temp=a[i]; j=i; }
  }
  return j;
}
perm(int i, int a[], int k, int n){
int ii,j;
  for(ii=k;ii<=n;ii++){
    perm(i, a, k+1, n);
    if(ii<n){
      reverse(a, k+1, n);
      j=minimum(a, k+1, n);
      swap(a, k,j);  out(i, a, n); 
    }
  }
}
permmain(int i, int n){int j;  // n is size of permutation, not always 9
  int a[10];
  for(j=1;j<=n;j++)a[j]=j;
  out(i, a, n);
  perm(i, a, 1, n);
}
/*** Check if there is duplicate in array "store" of size n=9 ***/
/*** Store items in block b[i..i+2][j..j+2] into "store" ***/
/*** Then check is there is duplicate by calling "sortcheck ***/
int sortcheck(int store[]){int i, j, k, t, min;
  t=0;
  for(i=1;i<=8; i++){  /** minimum selection sort **/
    min=store[i]; j=i;
    for(k=i+1;k<=9;k++)if(store[k]<min){min=store[k]; j=k;}
    store[j]=store[i]; store[i]=min;
  }
  for(i=1;i<=8;i++)if(store[i]==store[i+1]){t=1; return t;}
  return t;
}
int blockcheck(int bound){int i,j,k,l,t,ii;
  int store[10]; t=0; /* 9 items are stored in store */
  for(i=1;i<=bound;i=i+3)
  for(j=1;j<=9;j=j+3){
    ii=0;
    for(k=i;k<=i+2;k++)for(l=j;l<=j+2;l++)
      { ii++; store[ii]=b[k][l]; }
    if(sortcheck(store)==1){t=1; return t;}
  }
  return t;
}
int check(int i, int k){
  int ii, j, t, p[10], test[10];
  t=0;
  for(j=1;j<=size[i];j++)p[j]=permutation[i][k][j];
  for(j=1;j<=size[i];j++)test[j]=cand[i][p[j]];
/*** check upward ***/
  for(ii=i-1;ii>=1;ii--){
    for(j=1;j<=size[i];j++)
      if(test[j]==b[ii][pos[i][j]]){t=1; return t;}
  }
/*** check downward ***/
  for(ii=i+1;ii<=9;ii++){
    for(j=1;j<=size[i];j++)
      if(test[j]==b[ii][pos[i][j]]){t=1; return t;}
  }
  if(t==0) for(j=1;j<=size[i];j++)b[i][pos[i][j]]=test[j];
/*** block check ***/
  if((i/3)*3==i){t=blockcheck(i); if(t==1)return t;}
  return t;
}
search(int i){
  int j, k; int b1[10];
  for(j=1;j<=9;j++)b1[j]=b[i][j];
  if(i<=9){
    for(k=1;k<=factorial(size[i]);k++){ // k-th permutation in row i
      if(check(i, k)==0)search(i+1);
    }
  for(j=1;j<=9;j++)b[i][j]=b1[j];
  }else out1(); 
}
int find_cand(int cand[], int pos[], int i){int j, k;
  int count=0; 
  int member, c;
  for(k=1;k<=n;k++){ 
    member=0;
    for(j=1;j<=n;j++) if(b[i][j]==k){member=member+1; }
    if(member==0) {count++; cand[count]=k; }
  }
  c=0;
  for(j=1;j<=n;j++)if(b[i][j]==0){c++; pos[c]=j;} 
  return c;
}
main(){int i, j, k;
char filename[10];
FILE *in_file;
  int tempcand[10], temppos[10]; int tempsize;
  printf("Input file name ");
  scanf("%s", filename);
  in_file=fopen(filename, "r");
  n=9;
  for (i=1;i<=n;i++) {
    for (j=1;j<=n;j++) fscanf(in_file, "%d ",&b[i][j]);
    fscanf(in_file, "\n");
  }
  printf("b=\n");
  for (i=1;i<=n;i++) {
    for (j=1;j<=n;j++) printf("%d ",b[i][j]);
    printf("\n");
  }
  for(i=1;i<=9;i++){
    tempsize=find_cand(tempcand, temppos, i);
    size[i]=tempsize;  /* No. of non-vacant positions of row i */
    for (j=1;j<=tempsize;j++){ cand[i][j]=tempcand[j];}
    for (j=1;j<=tempsize;j++){ pos[i][j]=temppos[j];}
  }
  for(i=1;i<=9;i++){
    counter=0;
    permmain(i, size[i]); 
  }
  tt=clock();
  search(1);
  printf("\n");
  for(k=1;k<=9;k++){
  for(i=1;i<=9;i++)printf("%d ",b[k][i]);
  printf("\n");
  }
  printf("total time = %d millisec\n", (clock()-tt)/1000);
}