题解
一道很经典的题。
用的是NOIP2009的程序，没加修改就过了。
总体上来说有2个大优化
- 记录了每一个空的位置
- 每次找可能的数字最少的空搜
0ms过，还行1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using namespace std;
int vis[3][11][11]={0},sd[10][10]={0};
int lis[81][2],tot=0,flag=0;
void get(int at){
int i,mini=99,p,j,x,y,o;
for(i=at+1;i<tot;i++){
x=lis[i][0],y=lis[i][1],o=0;
for(j=1;j<=9;j++){
if(vis[0][x][j]||vis[1][y][j]||vis[2][(x/3)*3+y/3][j])continue;
else o++;
}
if(o<mini)
mini=o,p=i;
}
x=lis[at+1][0],y=lis[at+1][1],lis[at+1][0]=lis[p][0];
lis[at+1][1]=lis[p][1],lis[p][0]=x,lis[p][1]=y;
}
//0 行 1 列 2 宫
void print(){
if(flag)return ;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++)
printf("%d",sd[i][j]);
printf("\n");
}
flag=1;
}
void dfs(int at){
int i,x=lis[at][0],y=lis[at][1];
for(i=1;i<=9;i++){
if(vis[0][x][i]||vis[1][y][i]||vis[2][(x/3)*3+y/3][i])continue;
vis[0][x][i]=vis[1][y][i]=vis[2][(x/3)*3+y/3][i]=1;
sd[x][y]=i;
if(at<tot-1){
if(at!=tot-2)get(at);
dfs(at+1);
}
else print();
vis[0][x][i]=vis[1][y][i]=vis[2][(x/3)*3+y/3][i]=0;
sd[x][y]=0;
if(flag)break;
}
}
int main(){
int T,tmp;
scanf("%d",&T);
while(T--){
tot=0,flag=0;
memset(vis,0,sizeof(vis));
memset(sd,0,sizeof(sd));
memset(lis,0,sizeof(lis));
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
scanf("%1d",&tmp);
if(tmp)
sd[i][j]=tmp,vis[0][i][tmp]=
vis[1][j][tmp]=vis[2][(i/3)*3+j/3][tmp]=1;
else
lis[tot][0]=i,lis[tot++][1]=j;
}
dfs(0);
}
return 0;
}