Íŕçŕä ę ëó÷řčě đĺřĺíč˙ě Status: AC, problem ZSUD, contest ZEL07. By tourist (Gennady Korotkevitch), 2007-02-27 16:50:11.
{$R-,S-,Q-,I-,O+}
const maxn = 9;
type list = array [1..maxn,1..maxn] of word;
     listyes = array [1..maxn,1..maxn*3] of boolean;
     listchar = array [1..maxn,1..maxn] of char;
var
  kol,i,j,qq,tt: longint;
  ch: char;
  found: boolean;
  a: listchar;
  raj1,raj2,raj: array [1..maxn,1..maxn] of longint;
  yes: listyes;
  kraj,kv,last,kc,lst: array [1..maxn] of longint;
 
procedure rec(kol:longint);
var
  min,ki,kj,kp,r,p,e,i,j: longint;
  tmpa: listchar;
  tmpyes: listyes;
procedure updyes(i,j:longint);
var c: longint;
begin
  c:=Ord(a[i,j])-48;
  yes[c,i]:=True;
  yes[c,9+j]:=True;
  yes[c,18+raj[i,j]]:=True;
  dec(kol);
end;
begin
  if found then exit;
  for r:=1 to 9 do
  begin
    fillchar(kv,sizeof(kv),0);
    fillchar(last,sizeof(last),0);
    fillchar(kc,sizeof(kc),0);
    fillchar(lst,sizeof(lst),0);
    for j:=1 to 9 do
      if a[raj1[r,j],raj2[r,j]] = '.' then
      begin
        for p:=1 to 9 do
          if not (yes[p,raj1[r,j]] or yes[p,9+raj2[r,j]] or yes[p,18+r]) then
          begin
            inc(kv[p]);
            last[p]:=j;
            inc(kc[j]);
            lst[j]:=p;
          end;
      end
      else kv[Ord(a[raj1[r,j],raj2[r,j]])-48]:=-100;
    for i:=1 to 9 do
      if kv[i] = 0 then exit else
      if kv[i] = 1 then
      begin
        a[raj1[r,last[i]],raj2[r,last[i]]]:=Chr(i+48);
        updyes(raj1[r,last[i]],raj2[r,last[i]]);
        kv[i]:=-100;
        kc[last[i]]:=0;
      end;
    for i:=1 to 9 do
      if (a[raj1[r,i],raj2[r,i]] = '.') and (kc[i] = 0) then exit else
      if kc[i] = 1 then
      begin
        a[raj1[r,i],raj2[r,i]]:=Chr(lst[i]+48);
        updyes(raj1[r,i],raj2[r,i]);
        kc[i]:=0;
        kv[lst[i]]:=-100;
      end;
  end;
  for e:=1 to 9 do
  begin
    fillchar(kv,sizeof(kv),0);
    fillchar(kc,sizeof(kc),0);
    for j:=1 to 9 do
      if a[e,j] = '.' then
      begin
        for p:=1 to 9 do
          if not (yes[p,e] or yes[p,9+j] or yes[p,18+raj[e,j]]) then
          begin
            inc(kv[p]);
            last[p]:=j;
            inc(kc[j]);
            lst[j]:=p;
          end;
      end
      else kv[Ord(a[e,j])-48]:=-100;
    for i:=1 to 9 do
      if kv[i] = 0 then exit else
      if kv[i] = 1 then
      begin
        a[e,last[i]]:=Chr(i+48);
        updyes(e,last[i]);
        kv[i]:=-100;
        kc[last[i]]:=0;
      end;
    for i:=1 to 9 do
      if (a[e,i] = '.') and (kc[i] = 0) then exit else
      if kc[i] = 1 then
      begin
        a[e,i]:=Chr(lst[i]+48);
        updyes(e,i);
        kc[i]:=0;
        kv[lst[i]]:=-100;
      end;
  end;
  for e:=1 to 9 do
  begin
    fillchar(kv,sizeof(kv),0);
    fillchar(kc,sizeof(kc),0);
    for j:=1 to 9 do
      if a[j,e] = '.' then
      begin
        for p:=1 to 9 do
          if not (yes[p,j] or yes[p,9+e] or yes[p,18+raj[j,e]]) then
          begin
            inc(kv[p]);
            last[p]:=j;
            inc(kc[j]);
            lst[j]:=p;
          end;
      end
      else kv[Ord(a[j,e])-48]:=-100;
      for i:=1 to 9 do
        if kv[i] = 0 then exit else
        if kv[i] = 1 then
        begin
          a[last[i],e]:=Chr(i+48);
          updyes(last[i],e);
          kv[i]:=-100;
          kc[last[i]]:=0;
        end;
      for i:=1 to 9 do
        if (a[i,e] = '.') and (kc[i] = 0) then exit else
        if kc[i] = 1 then
        begin
          a[i,e]:=Chr(lst[i]+48);
          updyes(i,e);
          kc[i]:=0;
          kv[lst[i]]:=-100;
        end;
  end;
//  writeln((Now-td)*86400:0:3);
  if kol = 0 then
  begin
    writeln('Y');
    for i:=1 to 9 do
      for j:=1 to 9 do write(a[i,j]);
    writeln;
    found:=True;
    exit;
  end;
  min:=maxlongint;
  ki:=0; kj:=0;
  for i:=1 to 9 do
    for j:=1 to 9 do
      if a[i,j] = '.' then
      begin
        kp:=0;
        for e:=1 to 9 do
          if not (yes[e,i] or yes[e,9+j] or yes[e,18+raj[i,j]]) then inc(kp);
        if kp < min then
        begin
          min:=kp;
          ki:=i;
          kj:=j;
        end;
      end;
  i:=ki; j:=kj;
  tmpa:=a;
  tmpyes:=yes;
  for e:=1 to 9 do
    if not (yes[e,i] or yes[e,9+j] or yes[e,18+raj[i,j]]) then
    begin
      a[i,j]:=Chr(e+48);
      yes[e,i]:=True;
      yes[e,9+j]:=True;
      yes[e,18+raj[i,j]]:=True;
      rec(kol-1);
      yes:=tmpyes;
      a:=tmpa;
    end;
  a[i,j]:='.';
end;
 
begin
  read(tt);
  for qq:=1 to tt do
  begin
    for i:=1 to 9 do
      for j:=1 to 9 do
      begin
        read(ch);
        while not (ch in ['1'..'9','.']) do read(ch);
        a[i,j]:=ch;
      end;
    fillchar(yes,sizeof(yes),False);
    kol:=0;
    fillchar(kraj,sizeof(kraj),0);
    for i:=1 to 9 do
      for j:=1 to 9 do
      begin
        raj[i,j]:=((i-1) div 3)*3+(j-1) div 3+1;
        inc(kraj[raj[i,j]]);
        raj1[raj[i,j],kraj[raj[i,j]]]:=i;
        raj2[raj[i,j],kraj[raj[i,j]]]:=j;
        if a[i,j] <> '.' then
        begin
          yes[Ord(a[i,j])-48,i]:=True;
          yes[Ord(a[i,j])-48,9+j]:=True;
          yes[Ord(a[i,j])-48,18+raj[i,j]]:=True;
        end
        else inc(kol);
      end;
    found:=False;
    rec(kol);
  end;
end.