//======================================================C
//   9x9マス 数独(sudoku)　解法プログラム                C
//------------------------------------------------------C
//    Input File:   input.txt                           C
//    Output File:  output.txt                          C
//------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2012/04/03          C
//    　後 保範 ( 早稲田大学, Waseda University )        C
//======================================================C
#include <stdio.h>
int debug = 0;
FILE *fp1, *fp2;
int A[9][9], W[9][9][9], NO[9][9];
int AS[9][9], WS[9][9][9], NOS[9][9];
int R[3][9], CV[12][4];   // (val,i,j1,j2)
void reduce(int v, int WK[9], int *N)
{ int i, k, n;
  if(v != 0) {
     n = *N;
     for (k=0; k<n; k++)
       { if(WK[k] == v) 
           { *N = n - 1;
             for (i=k; i<*N; i++)
               { WK[i] = WK[i+1]; }
           }
   }   }
}
void Wreset()
{ int i, j, k, l, I, J;
  for (i=0; i<9; i++)
   { for (j=0; j<9; j++)
      { I = (i/3)*3;  J = (j/3)*3;
        for (k=0; k<9; k++)
         { reduce(A[i][k], &W[i][j][0], &NO[i][j]);
           reduce(A[k][j], &W[i][j][0], &NO[i][j]); }
        for (k=I; k<I+3; k++)
         { for (l=J; l<J+3; l++)
            { reduce(A[k][l], &W[i][j][0], &NO[i][j]); }
         }
   }  }
}
void Areset()
{ int i, j;
  Wreset();
  for (i=0; i<9; i++)
    { for (j=0; j<9; j++)
        { if(NO[i][j] == 1) 
            { A[i][j] = W[i][j][0];  Wreset(); } 
        }
    }
}
void debugs(int id, int i)
{ int k;
  if(debug >= 2)
    { if(id == 0) fprintf(fp2,"Rcheck debug\n");
      else if(id == 1) fprintf(fp2,"Ccheck debug\n");
           else   fprintf(fp2,"Bcheck debug\n");
      fprintf(fp2,"i=%d,",i);
      for (k=0; k<9; k++)
        { fprintf(fp2,"%2d",R[0][k]); }
      fprintf(fp2,"\n    ");
      for (k=0; k<9; k++)
        { fprintf(fp2,"%2d",R[1][k]); }
      fprintf(fp2,"\n");
    }
}
void Rcheck()
{ int i, j, k, l;
  Wreset();
  for (i=0; i<9; i++)
    { for (k=0; k<9; k++)
        { R[0][k] = 0; }
      for (j=0; j<9; j++)
        { for (k=0; k<NO[i][j]; k++)
            { l = W[i][j][k] - 1;
              R[0][l] += 1;  R[1][l] = j; }
        }
      debugs(0, i);
      for (k=0; k<9; k++)
        { if(R[0][k] == 1)  { j = R[1][k];
              A[i][j] = k + 1;   NO[i][j] = 0; }
        }
    }
}
void Ccheck()
{ int i, j, k, l;
  Wreset();
  for (j=0; j<9; j++)
    { for (k=0; k<9; k++)
        { R[0][k] = 0; }
      for (i=0; i<9; i++)
        { for (k=0; k<NO[i][j]; k++)
            { l = W[i][j][k] - 1;
              R[0][l] += 1;  R[1][l] = i; }
        }
      debugs(1, j);
      for (k=0; k<9; k++)
        { if(R[0][k] == 1) { i = R[1][k];
              A[i][j] = k + 1;  NO[i][j] = 0; }
        }
    }
}
void Bcheck()
{ int i, j, k, l, I, J, i1, j1;
  Wreset();
  for (i=0; i<9; i++)
    { I = i/3;  J = i%3;
      for (k=0; k<9; k++)
        { R[0][k] = 0; }
      for (j=0; j<9; j++)
        { i1 = 3*I + j/3;  j1 = 3*J + j%3;
          for (k=0; k<NO[i1][j1]; k++)
            { l = W[i1][j1][k] - 1;
              R[0][l] += 1;  R[1][l] = j; }
        }
      debugs(2, i);
      for (k=0; k<9; k++)
        { if(R[0][k] == 1)
            { j = R[1][k];
              i1 = 3*I + j/3;     j1 = 3*J + j%3; 
              A[i1][j1] = k + 1;  NO[i1][j1] = 0;  }
        }
    }
}
int Rcheck2()
{ int i, j, k, l, n;
  n = 0;  Wreset();
  for (i=0; i<9; i++)
    { for (k=0; k<9; k++)
        { R[0][k] = 0; }
      for (j=0; j<9; j++)
        { for (k=0; k<NO[i][j]; k++)
            { l = W[i][j][k] - 1;
              if(R[0][l] == 1) R[2][l] = R[1][l];
              R[0][l] += 1;    R[1][l] = j;    }
        }
      debugs(0, j);
      for (k=0; k<9; k++)
        { if(R[0][k] == 2)
            { CV[n][0] = k + 1;       // val
              CV[n][1] = i;           // i
              CV[n][2] = R[2][k];     // j1
              CV[n][3] = R[1][k];     // j2
              if(debug >= 2)
                { fprintf(fp2,"v,i,j1,j2=%2d%2d%2d%2d\n",
                   CV[n][0],CV[n][1],CV[n][2],CV[n][3]); }
              n ++;
            }
        }
      if(n >= 2) break;
    }
  return n; 
}
void output()
{ int i, j;
  fprintf(fp2," x-------x-------x-------x\n");
  for (i=0; i<9; i++)
    { for (j=0; j<9; j++)
        { if(j%3 == 0) fprintf(fp2," |");
          if(A[i][j] == 0) fprintf(fp2,"  ");
             else  fprintf(fp2,"%2d",A[i][j]);  }
      fprintf(fp2," |\n");
      if(i%3 == 2) fprintf(fp2," x-------x-------x-------x\n");
    }
} 
void dout1()
{ int i, j, k;
  for (i=0; i<9; i++)
    { for (j=0; j<9; j++)
        { fprintf(fp2,"i,j=%d %d,",i,j);
          for (k=0; k<NO[i][j]; k++)
            { fprintf(fp2,"%2d",W[i][j][k]); }
          fprintf(fp2,"\n");
    }   }
}
void initial()
{ int i, j, k;
  for (i=0; i<9; i++)
    { for (j=0; j<9; j++)
        { if(A[i][j] != 0) 
            { W[i][j][0] = A[i][j];  NO[i][j] = 1;   }
          else 
            { NO[i][j] = 9;
              for (k=0; k<9; k++)
                { W[i][j][k] = k + 1; }  }
        }
    }
  if(debug >= 3) {
     fprintf(fp2,"Before Wreset\n");
     dout1();    }
  Wreset(); 
  if(debug >= 2) {
     fprintf(fp2,"After Wreset\n");
     dout1();    }
}
int step1()
{ int i, j, k, n, T, t;
  T = 0;
  for (k=1; k<30; k++)
    { Areset();  Rcheck();
      Areset();  Ccheck();
      Areset();  Bcheck();
      t = T;  T = 0;
      for (i=0; i<9; i++)
        { for (j=0; j<9; j++)
           { if(A[i][j] != 0) T++; }
        }
      if(T == t)  break;
      if(debug >=1) fprintf(fp2,"  k=%d, nonzero=%d\n",k,T);
      if(T >= 81) break;
    }
  return T;
}
void copy()
{ int i, j, k;
  for (i=0; i<9; i++)
    { for (j=0; j<9; j++)
        { AS[i][j]  = A[i][j];
          NOS[i][j] = NO[i][j];
          for (k=0; k<9; k++)
            { WS[i][j][k] = W[i][j][k]; }
        }
    }
} 
void recopy()
{ int i, j, k;
  for (i=0; i<9; i++)
    { for (j=0; j<9; j++)
        { A[i][j]  = AS[i][j];
          NO[i][j] = NOS[i][j];
          for (k=0; k<9; k++)
            { W[i][j][k] = WS[i][j][k]; }
        }
    }
} 
int step21()
{ int i, j, k, T;
// CV[][*]: (val,i,j1,j2)
  i = CV[0][1];
  for (k=0; k<2; k++)
    { recopy(); 
      j = CV[0][k+2];
      A[i][j] = CV[0][0];
      if(debug >= 1) { fprintf(fp2,
                 "step2 i,j,v=%2d%2d%2d\n",i,j,A[i][j]); }
      initial();  T = step1(); 
      if(T >= 81) break; 
    }
  return T;
}
int step22()
{ int i, j, i1, j1, k, l, T;
// CV[][*]: (val,i,j1,j2)
  for (l=0; l<2; l++)
    { i  = CV[0][1];
      i1 = CV[1][1];
      for (k=0; k<2; k++)
        { recopy(); 
          j  = CV[0][l+2];  A[i][j]   = CV[0][0];
          j1 = CV[1][k+2];  A[i1][j1] = CV[1][0];
          if(debug >= 1) { fprintf(fp2,
                 " step2 i,j,v=%2d%2d%2d,%2d%2d%2d\n"
                  ,i,j,A[i][j],i1,j1,A[i1][j1]); }
          initial();  T = step1(); 
          if(T >= 81) break; 
        }
      if(T >=81) break;
    }
  return T;
}
int main()
{ int i, j, k, I, J, n, T;
// Initial set
  fp1 = fopen("input.txt","r");
  fp2 = fopen("output.txt","w");
  for (i=0; i<9; i++)
    { fscanf(fp1,"%d%d%d%d%d%d%d%d%d",&A[i][0],&A[i][1],
                    &A[i][2],&A[i][3],&A[i][4],&A[i][5],
                    &A[i][6],&A[i][7],&A[i][8]);   }     
  fprintf(fp2,"  ** 数独インプット **\n");
  output();
// step 1 
  copy();
  if(debug >= 1) fprintf(fp2,"\n step1\n");
  initial();
  T = step1();
// step 2
  if (T < 81) 
    { n = Rcheck2(); 
      if(n == 1) T = step21();
      else if(n >= 2) T = step22();
    } 
  if(T >= 81) fprintf(fp2,"\n  ** 数独結果(完了) **\n");
    else      fprintf(fp2,"\n  ** 数独結果(未完) **\n");
  output();
  return 0; 
}