# include <iostream>
# include <cstring>
using namespace std;
# define N 250000
struct node
{
	int row,col;
	int l,r,d,u;
}buf[N];
int ccc=324;
int co=0,head=0,row,col,cn[1000];
inline int posr(int a)
{
	return 1+col+a;
}
inline int posc(int a)
{
	return 1+a;
}
inline int block(int r,int c)
{
	return r/3*3+c/3;
}
void init(int r,int c)
{
	int i;
	row=r;
	col=c;
	buf[0].u=row+col;
	buf[0].l=col;
	buf[0].row=buf[0].col=-1;
	buf[0].r=1;
	buf[0].d=col+1;
	for(i=2;i<=col;i++)
		buf[i].l=i-1;
	for(i=1;i<col;i++)
		buf[i].r=i+1;
	for(i=1;i<=col;i++)
		buf[i].u=buf[i].d=i,buf[i].row=-1,buf[i].col=i-1;
	buf[col].r=0;
	buf[col+1].u=0;
	for(i=col+2;i<=col+row;i++)
		buf[i].u=i-1;
	for(i=col+1;i<col+row;i++)
		buf[i].d=i+1;
	for(i=col+1;i<=col+row;i++)
		buf[i].l=buf[i].r=i,buf[i].row=i-col-1,buf[i].col=-1;
	buf[row+col].d=0;
	co=row+col+1;
	memset(cn,0,sizeof(cn));
}
void insert(int r,int c)
{
	buf[co].row=r;
	buf[co].col=c;
	buf[co].u=posc(c);
	buf[co].d=buf[posc(c)].d;
	buf[co].l=posr(r);
	buf[co].r=buf[posr(r)].r;
	buf[posc(c)].d=co;
	buf[buf[co].d].u=co;
	buf[posr(r)].r=co;
	buf[buf[co].r].l=co++;
	cn[c]++;
}
void remove(int c)
{
	int i,j;
	buf[buf[posc(c)].l].r=buf[posc(c)].r;
	buf[buf[posc(c)].r].l=buf[posc(c)].l;
	ccc--;
	for(i=buf[posc(c)].d;i!=posc(c);i=buf[i].d)
	{
		for(j=buf[i].r;j!=i;j=buf[j].r)
		{
			buf[buf[j].u].d=buf[j].d;
			buf[buf[j].d].u=buf[j].u;
			if(buf[j].col!=-1)
				cn[buf[j].col]--;
		}
	}
}
void resume(int c)
{
	int j,i;
	ccc++;
	for(i=buf[posc(c)].u;i!=posc(c);i=buf[i].u)
	{
		for(j=buf[i].l;j!=i;j=buf[j].l)
		{
			buf[buf[j].d].u=j;
			buf[buf[j].u].d=j;
			if(buf[j].col!=-1)
			    cn[buf[j].col]++;
		}
	}
	buf[buf[posc(c)].r].l=posc(c);
	buf[buf[posc(c)].l].r=posc(c);
}
int ans[100][2];
char str[100];
int dfs(int level)
{
	if(buf[head].r==head)
	{
		for(int i=0;i<level;i++)
		{
		   str[ans[i][1]]=ans[i][0]%9+'1';
		}
		for(int i=0;i<81;i++)
		{
			cout<<str[i];
			if(i%9==8)
				cout<<endl;
			
		}
		return 1;
	}
	else
	{
		int maxnum=0xfffffff,pos,i,j;
		for(i=buf[head].r;i!=head;i=buf[i].r)
			if(cn[buf[i].col]<maxnum)
				maxnum=cn[buf[i].col],pos=buf[i].col;

		remove(pos);
		for(i=buf[posc(pos)].d;i!=posc(pos);i=buf[i].d)
		{
			ans[level][0]=buf[i].row;
			if(pos<81) ans[level][1]=buf[i].col;
			for(j=buf[i].r;j!=i;j=buf[j].r)
				if(buf[j].col!=-1)
				{
				   remove(buf[j].col);
				   if(buf[j].col<81)
					   ans[level][1]=buf[j].col;
				}
		//	chk();
			if(dfs(level+1)) return 1;
			for(j=buf[i].l;j!=i;j=buf[j].l)
				if(buf[j].col!=-1)
					resume(buf[j].col);
		}
		resume(pos);
		return 0;
	}


}
int main()
{	 
	 int testcase;
	 cin>>testcase;
	 while(testcase--)
	 {
         char tmp[20];
		 str[0]='\0';
		 for(int i=0;i<9;i++)
		 {
			 cin>>tmp;
			 strcat(str,tmp);
		 }
		 init(729,324);
		 for(int i=0;i<9;i++)
		 {
			 for(int j=0;j<9;j++)
				 for(int k=0;k<9;k++)
				 {
					 insert(i*81+j*9+k,i*9+j);
					 insert(i*81+j*9+k,81+i*9+k);
					 insert(i*81+j*9+k,81+81+9*j+k);
					 insert(i*81+j*9+k,81+81+81+9*block(i,j)+k);
				 }
		 }
		 for(int i=0;i<9;i++)
			 for(int j=0;j<9;j++)
			   if(str[i*9+j]!='0')
			   {
				   remove(i*9+j);
				   int k;
				   for(k=buf[posc(i*9+j)].d;k!=posc(i*9+j)&&buf[k].row!=i*81+j*9+str[i*9+j]-'1';k=buf[k].d);
				   for(int l=buf[k].r;l!=k;l=buf[l].r)
						   if(buf[l].col!=-1)
							   remove(buf[l].col);					   
			   }
		dfs(0);
	 }
	return 0;
}

• 多谢啊,正好要自己看看舞蹈 (7) kaitian5201314 2010-08-29 16:00:06
• 好人啊 (3961) lisency 2012-04-06 18:32:07