判断是否可行的时候，只要看横竖和九格和当前填的数是否有重复就够了。
注意有可能输入数据没按规则来，一开始就可以否定掉。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
struct node
{
int x,y;
node(int xx,int yy)
{
x=xx;
y=yy;
}
};
vector<node> sd;
int mp[10][10];
bool isok(int x,int y,int k)
{
for(int i=0;i<9;i++) //判断行列重复
if((mp[x][i]==k&&i!=y)||(mp[i][y]==k&&i!=x)) return false;
int tot=0; //判断九宫格重复
for(int i=x/3*3;i<x/3*3+3;i++)
for(int j=y/3*3;j<y/3*3+3;j++)
{
if(mp[i][j]==k) tot++;
if(tot==2) return false;
}
return true;
}
void print(){for(int i=0;i<9;i++){for(int j=0;j<9;j++)printf("%d",mp[i][j]);puts("");}}
bool dfs(int now)
{
if(now==sd.size()) {print();return true;}
for(int i=1;i<=9;i++)
{
int x=sd[now].x;
int y=sd[now].y;
mp[x][y]=i;
if(isok(x,y,i))
{
if(dfs(now+1))
return true;
}
mp[x][y]=0;
}
return false;
}
int main()
{
int cas;
char tmp[20];
cin>>cas;
for(int ca=1;ca<=cas;ca++)
{
for(int i=0;i<9;i++){
scanf("%s",tmp);
for(int j=0;j<9;j++)
mp[i][j]=tmp[j]-'0';
}
sd.clear();
bool flag=true;
for(int i=0;flag&&i<9;i++)
for(int j=0;flag&&j<9;j++)
{
if(mp[i][j])
flag=isok(i,j,mp[i][j]);
else sd.push_back(node(i,j));
}
if(!flag||!dfs(0)) puts("Could not complete this grid.");
if(ca!=cas) puts("");
}
return 0;
}