超详细注释,一看就懂
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
const int N=9;
const int M=1<<N;
int one[M],st[M];
int row[N],col[N],cell[3][3];
char str[100];
// 主要进行可行性剪枝,和优化搜索顺序
// 这题中,根据上述优化思路,可行性剪枝就是在一个空点可以填的数是同一行列和小方格没出现的数字,
// 优化搜索顺序是先遍历能填充数字可能数小的空格子点
void init(){ //初始化row等数组
for(int i=0;i<N;i++) col[i]=row[i]=(1<<N)-1;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
cell[i][j]=(1<<N)-1;
}
}
}
int lowbit(int x){ // lowbit函数 作用:返回一个数的二进制表示最低一位1的对应十进制数 比如lowbit(6)=2 ; 6=110 =>2^1=2
return x&-x;
}
void draw(int x,int y,int t,bool flag){ // 该函数用于填充数独,和更新标记数组row,col,cell
if(flag) {
str[x*N+y]='1'+t;
}
else str[x*N+y]='.';
int v=1<<t;
if(!flag) v=-v;
row[x]-=v;
col[y]-=v;
cell[x/3][y/3]-=v;
}
int get(int x,int y){ // 获取这一个格点能够填的数字是多少,要套一下st数组才能得到具体有多少个。
return row[x] & col[y] & cell[x/3][y/3];
}
bool dfs(int cnt){
if(!cnt) return true; // 当遇到结果是一致return返回,不在遍历
int minv=10;
int x,y;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(str[i*N+j]=='.'){
int t=one[get(i,j)]; // 找到分支数最少的空格点
if(t<minv){
minv=t;
x=i,y=j;
}
}
}
}
int s=get(x,y);
for(int i=s;i;i-=lowbit(i)){
int t=st[lowbit(i)]; // 依次填充可以填的数字,t
draw(x,y,t,true);
if(dfs(cnt-1)) return true;
draw(x,y,t,false);
}
return false;
}
int main(){
for(int i=0;i<N;i++) st[1<<i]=i;
for(int i=0;i<1<<N;i++){
for(int j=0;j<N;j++){
one[i]+=i>>j & 1;
}
}
while(cin>>str , str[0]!='e'){
int cnt=0;
init();
for(int i=0,k=0;i<N;i++){
for(int j=0;j<N;j++,k++){
if(str[k]!='.'){
draw(i,j,str[k]-'1',true);
}
else cnt++;
}
}
dfs(cnt);
puts(str);
}
system("pause");
return 0;
}