AcWing 166. 数独(dfs,位运算 剪枝集萃）

#include<bits/stdc++.h>
using namespace std;
const int N=100,M=9;
char s[N];
int ma[1<<M],ones[1<<M];
int col[M],row[M],cell[3][3];
int lb(int x){
    return x& -x;
}
void init(){
    for(int i=0;i<M;i++){
        col[i]=row[i]=(1<<M)-1;
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cell[i][j]=(1<<M)-1;
        }
    }
}
int get(int x,int y){
    return row[x]&col[y]&cell[x/3][y/3];
}
void draw(int x,int y,int t,int flag){
    if(flag)s[x*M+y]=t+'1';
    else s[x*M+y]='.';
    
    int v=1<<t;
    if(!flag)v=-v;
    row[x]-=v;
    col[y]-=v;
    cell[x/3][y/3]-=v;
    
}
bool dfs(int cnt){
    if(!cnt)return 1;
    int minv=10,x,y;
    for(int i=0;i<M;i++){
        for(int j=0;j<M;j++){
            if(s[i*M+j]=='.'){
                int tep=get(i,j);
                if(ones[tep]<minv){
                    x=i,y=j;
                    minv=ones[tep];
                }
            }
        }
    }
    int state=get(x,y);
    for(int i=state;i;i-=lb(i)){
        int tep=ma[lb(i)];
        draw(x,y,tep,1);
        if(dfs(cnt-1))return 1;
        draw(x,y,tep,0);
        
    }
    return 0;
}
int main(){
    for(int i=0;i<M;i++)ma[1<<i]=i;
    for(int i=0;i<1<<M;i++){
        for(int j=0;j<M;j++){
            ones[i]+=i>>j&1;
        }
    }
    while(cin>>s,s[0]!='e'){
        init();
        int cnt=0;
        for(int i=0,k=0;i<M;i++){
            for(int j=0;j<M;j++,k++){
                if(s[k]!='.'){
                    int num=s[k]-'1';
                    draw(i,j,num,1);
                }
                else cnt++;
                
            }
        }
        dfs(cnt);
        cout<<s<<endl;
    }
}