题意：
完成数独
思路：
看到题目，这肯定是搜索，但是试了一发普通的直接就超时了，肯定要加一些剪枝和优化，首先是位运算优化可以将每一行,每一列,每一个九宫格,都利用一个九位二进制数保存,当前还有哪些数字可以填写，再一个我们肯定是从限制性最高的那个点开始填的，其实每次都是填限制最多的那个数， 涉及到一个lowbit函数：当前得需要用lowbit运算取出当前可以能填的数字.
AC代码：
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int maxn
=1e6+10;
char mp
[10][10];
int c
[10],r
[10],g
[10];
int cnt
[1100],num
[1100];
int k
,tot
;
int lowbit(int x
) {
return x
&(-x
);
}
int get(int x
,int y
) {
return ((x
/3)*3)+(y
/3);
}
void fun(int x
,int y
,int z
) {
r
[x
]^=1<<z
;
c
[y
]^=1<<z
;
g
[get(x
,y
)]^=1<<z
;
}
int dfs(int now
) {
if(now
== 0) return 1;
int tmp
= 10,x
,y
;
for(int i
=0;i
<9;i
++) {
for(int j
=0;j
<9;j
++) {
if(mp
[i
][j
]!='.') continue;
int val
= r
[i
] & c
[j
] & g
[get(i
,j
)];
if(!val
) return 0;
if(cnt
[val
]<tmp
) {
tmp
= cnt
[val
];
x
= i
,y
= j
;
}
}
}
int val
= r
[x
] & c
[y
] & g
[get(x
,y
)];
for(;val
;val
-=lowbit(val
)) {
int z
= num
[lowbit(val
)];
mp
[x
][y
] = z
+'1';
fun(x
,y
,z
);
if(dfs(now
-1)) return 1;
fun(x
,y
,z
);
mp
[x
][y
] = '.';
}
return 0;
}
int main()
{
for(int i
=0;i
<1<<9;i
++) {
for(int j
=i
;j
;j
-=lowbit(j
)) {
cnt
[i
]++;
}
}
for(int i
=0;i
<9;i
++) num
[1<<i
] = i
;
char s
[100];
while(scanf("%s",s
)&&s
[0]!='e') {
for(int i
=0;i
<9;i
++) c
[i
] = r
[i
] = g
[i
] = (1<<9)-1;
for(int i
=0;i
<9;i
++) {
for(int j
=0;j
<9;j
++) {
mp
[i
][j
] = s
[i
*9+j
];
}
}
tot
=0;
for(int i
=0;i
<9;i
++) {
for(int j
=0;j
<9;j
++) {
if(mp
[i
][j
]!='.') {
fun(i
,j
,mp
[i
][j
]-'1');
} else {
tot
++;
}
}
}
dfs(tot
);
for(int i
=0;i
<9;i
++) {
for(int j
=0;j
<9;j
++) {
s
[i
*9+j
] = mp
[i
][j
];
}
}
puts(s
);
}
}
