http://acm.pku.edu.cn/JudgeOnline/problem?id=2676
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int a[10][10];
bool row[10][10],col[10][10],square[10][10];
struct node
{
int x,y;
}q[81];
int top;
int getsquare(const int & x,const int & y)
{
return x/3*3+y/3;
}
bool check(const int & x,const int & y,const int & k)
{
return ( !row[x][k] && !col[y][k] && !square[getsquare(x,y)][k] );
}
bool dfs()
{
node tmp;
if(top!=0)
{
tmp=q[--top];
for(int i=1;i<10;i++)
{
if(check(tmp.x,tmp.y,i))
{
row[tmp.x][i]=1;
col[tmp.y][i]=1;
square[getsquare(tmp.x,tmp.y)][i]=1;
if(dfs())
{
a[tmp.x][tmp.y]=i;
return 1;
}
else
{
row[tmp.x][i]=0;
col[tmp.y][i]=0;
square[getsquare(tmp.x,tmp.y)][i]=0;
}
}
}
q[top++]=tmp;
return 0;
}
return 1;
}
int main()
{
int t;
char s[10];
scanf("%d",&t);
getchar();
while(t--)
{
memset(col,false,sizeof(col));
memset(row,false,sizeof(row));
memset(square,false,sizeof(square));
top=0;
for(int i=0;i<9;i++)
{
gets(s);
for(int j=0;j<9;j++)
{
a[i][j]=s[j]-'0';
if(a[i][j]!=0)
{
row[i][a[i][j]]=1;
col[j][a[i][j]]=1;
square[getsquare(i,j)][a[i][j]]=1;
}
else
{
q[top].x=i,q[top].y=j;
top++;
}
}
}
dfs();
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
printf("%d",a[i][j]);
printf("\n");
}
}
}