|
|
 #include <iostream>
using namespace std;
const int M=10;
bool userow[M][M],usecol[M][M],useblock[M][M];
int map[M][M];
  struct node {
 int x,y;
int num;
 }sudu[M*M];
int find(int x,int y)
{
int row=x/3;
int col=y/3;
return 3*row+col;
}
bool dfs(int n,int cnt)
{
if(n==cnt)return 1;
int i;
for(i=1;i<M;i++)
  {
if(!userow[sudu[n].x][i]&&!usecol[sudu[n].y][i]&&!useblock[find(sudu[n].x,sudu[n].y)][i])
{
userow[sudu[n].x][i]=true;
usecol[sudu[n].y][i]=true;
useblock[find(sudu[n].x,sudu[n].y)][i]=true;
sudu[n].num=i;
if(dfs(n+1,cnt))
return 1;
userow[sudu[n].x][i]=false;
usecol[sudu[n].y][i]=false;
useblock[find(sudu[n].x,sudu[n].y)][i]=false;
sudu[n].num=0;
 }
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(userow,false,sizeof(userow));
memset(usecol,false,sizeof(usecol));
memset(useblock,false,sizeof(useblock));
int i,j;
int cnt=0;
for(i=0;i<M-1;i++)
{
char mess[M];
scanf("%s",&mess);
for(j=0;j<M-1;j++)
{
map[i][j]=mess[j]-'0';
if(map[i][j])
{
userow[i][map[i][j]]=true;
usecol[j][map[i][j]]=true;
useblock[find(i,j)][map[i][j]]=true;
}
else
{
sudu[cnt].x=i;
sudu[cnt].y=j;
sudu[cnt].num=0;
cnt++;
}
}
}
dfs(0,cnt);
for(i=0;i<cnt;i++)
map[sudu[i].x][sudu[i].y]=sudu[i].num;
for(i=0;i<M-1;i++){
for(j=0;j<M-1;j++)
printf("%d",map[i][j]);
printf("\n");
}
}
return 0;
}
|