Íŕçŕä ę ëó÷řčě đĺřĺíč˙ě Status: AC, problem ZSUD, contest ZEL07. By levlam (Levin Aleksey), 2007-02-26 16:01:55.
#include <stdio.h>
#include <memory.h>
#define ONLINE_JUDGE
#define update(i, j)\
   if (a[i][j]=='.')\
   {\
      t=can[i][j][pp]++;\
      if (!t) B[i][j]++;\
      if (B[i][j]==8 && !b[i][j])\
      {\
         q[qf++]=(i<<4)+j;\
         b[i][j]=1;\
         if (qf>=100) qf-=100;\
      }\
      else if (B[i][j]==9) err=1;\
  }
 
int a[9][9];
char b[9][9], eh[9][9], ev[9][9], ec[3][3][9];
int B[9][9], k, can[9][9][9];
int added[100], q[105], qe, qf;
int D[9]={3,3,3,6,6,6,9,9,9};
int DD[9]={0,0,0,1,1,1,2,2,2};
 
int rand(void);
 
#ifndef ONLINE_JUDGE
void debugoutput(int z)
{
   int i, j;
   printf("%d %d:\n", z, k);
   for (i=0; i<9; i++)
   {
      for (j=0; j<9; j++)
         printf("%c", a[i][j]);
      printf("\n");
   }
   printf("\n");
}
#endif
 
void undo(void);
void obr(void);
 
void addcell(int x, int y, int z, int p)
{
   int i, j, k1=D[x], k2=D[y], t, pp=p-'1', l, d, tt;
   char *dd=ec[DD[x]][DD[y]];
   int err=0;
   a[x][y]=p;
   eh[x][pp]=1;
   ev[y][pp]=1;
   dd[pp]=1;
   for (i=0; i<9; i++)
   {
      update(x,i);
      update(i,y);
   }
   for (i=k1-3; i<k1; i++)
      for (j=k2-3; j<k2; j++)
         update(i,j);
 
   added[k++]=(x<<4)+y+(z<<8);
   #ifndef ONLINE_JUDGE
   debugoutput(z);
   #endif
 
   if (err) undo();
   else
   {
      while (qe!=qf) obr();
 
     for (i=k1-3; i<k1; i++)
         if (!eh[i][pp])
         {
            for (l=j=0; j<9 && l<2; j++)
               if (a[i][j]=='.' && !can[i][j][pp]) l++, t=j;
            if (l==0) undo();
            else if (l==1 && !b[i][t])
               addcell(i, t, 1, p);
         }
 
      for (i=k2-3; i<k2; i++)
         if (!ev[i][pp])
         {
            for (l=j=0; j<9 && l<2; j++)
               if (a[j][i]=='.' && !can[j][i][pp]) l++, t=j;
            if (l==0) undo();
            else if (l==1 && !b[t][i])
               addcell(t, i, 1, p);
         }
 
      for (d=0; d<9; d++)
         if (!dd[d])
         {
            l=0;
            for (i=k1-3; i<k1 && l<2; i++)
               for (j=k2-3; j<k2 && l<2; j++)
               {
                  if (a[i][j]=='.' && !can[i][j][d]) l++, t=i, tt=j;
                  if (a[i][j]==d+'1') l=2;
               }
            if (l==0) undo();
            else if (l==1 && !b[t][tt])
               addcell(t, tt, 1, d+'1');
         }
/*      for (ii=3; ii<=9; ii+=3)
         for (jj=3; jj<=9; jj+=3)
            if ((ii==k1 && jj!=k2) || (ii!=k1 && jj==k2))
            {
               l=0;
               for (i=ii-3; i<ii && l<2; i++)
                  for (j=jj-3; j<jj && l<2; j++)
                  {
                     if (a[i][j]=='.' && !can[i][j][pp]) l++, t=i, tt=j;
                     if (a[i][j]==p) l=2;
                  }
               if (l==0) undo();
               else if (l==1 && !b[t][tt])
                  addcell(t, tt, 1, p);
            }*/
   }
}
 
int deletecell(int *x, int *y, int *p)
{
   int z, i, j, k1, k2, t, pp;
   *x=added[--k];
   z=(*x)>>8;
   *y=(*x)&15;
   *x=(*x>>4)&15;
   (*p)=a[*x][*y];
   pp=(*p)-'1';
   k1=D[*x], k2=D[*y];
   eh[*x][pp]=0;
   ev[*y][pp]=0;
   ec[DD[*x]][DD[*y]][pp]=0;
   for (i=0; i<9; i++)
   {
      if (a[*x][i]=='.')
      {
         t=--can[*x][i][pp];
         if (!t) B[*x][i]--;
      }
      if (a[i][*y]=='.')
      {
         t=--can[i][*y][pp];
         if (!t) B[i][*y]--;
      }
   }
   for (i=k1-3; i<k1; i++)
      for (j=k2-3; j<k2; j++)
         if (a[i][j]=='.')
         {
            t=--can[i][j][pp];
            if (!t) B[i][j]--;
         }
   a[*x][*y]='.';
 
   #ifndef ONLINE_JUDGE
   debugoutput(1000+z);
   #endif
   return z;
}
 
void undo(void)
{
   int x, y, p, i, *t;
   while (deletecell(&x, &y, &p)) ;
   t=can[x][y];
   for (i=p+1-'1'; i<9 && t[i]; i++) ;
   if (i>=9) undo();
   else addcell(x, y, 0, i+'1');
}
 
void obr(void)
{
   int i, x, y, *t;
   x=q[qe++];
   if (qe>=100) qe-=100;
   y=x&15;
   x>>=4;
   b[x][y]=0;
   if (B[x][y]==8)
   {
      t=can[x][y];
      for (i=0; i<9 && t[i]; i++) ;
      addcell(x, y, 1, i+'1');
   }
}
 
void solve(int x, int y)
{
   int i, *t=can[x][y];
   for (i=0; i<9 && t[i]; i++) ;
   addcell(x, y, 0, i+'1');
}
 
int main(void)
{
   int i, j, l, mi, mj, tn, nt;
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
   scanf("%d\n", &nt);
   for (tn=0; tn<nt; tn++)
   {
      k=0;
//      memset(a, '.', sizeof(a));
      for (i=0; i<9; i++)
         for (j=0; j<9; j++)
            a[i][j]='.';
      memset(B, 0, sizeof(B));
      memset(can, 0, sizeof(can));
      memset(eh, 0, sizeof(eh));
      memset(ev, 0, sizeof(ev));
      memset(ec, 0, sizeof(ec));
      for (i=0; i<9; i++)
         for (j=0; j<9; j++)
         {
            l=getchar();
            if (l!='.' && a[i][j]=='.') addcell(i, j, 1, l);
         }
      scanf("\n");
 
      while (k<81)
      {
         mi=mj=0;
         for (i=0; i<9; i++)
            for (j=0; j<9; j++)
               if (a[i][j]=='.' && (B[i][j]>B[mi][mj] || a[mi][mj]!='.'))
                  mi=i, mj=j;
         solve(mi,mj);
      }
      if (k==81)
      {
         printf("Y\n");
         for (i=0; i<9; i++)
            for (j=0; j<9; j++)
               printf("%c", a[i][j]);
         printf("\n");
      }
      else
         printf("N\n");
   }
   return 0;
}