用二进制搜数独同时维护分数

用闫老师数独那题的板子

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N=9,M=(1<<N);
int g[10][10];
int h[N],l[N],k[3][3];
int one[M],log_[M];
int ans=-1;

int lowbit(int x){
    return x&-x;
}
int get(int x,int y){
    return h[x]&l[y]&k[x/3][y/3];
}
void draw(int x,int y,int t,bool flag){
    if(flag){
        g[x][y]=t;
        h[x]-=(1<<(t-1));
        l[y]-=(1<<(t-1));
        k[x/3][y/3]-=(1<<(t-1));
    }
    else {
         g[x][y] = 0;
        h[x]+=(1<<(t-1));
        l[y]+=(1<<(t-1));
        k[x/3][y/3]+=(1<<(t-1));
    }
}
 int gets(int x, int y, int t)
{
    if(x==4&&y==4) return t*10;
    if(x>=3&&x<=5&&y>=3&&y<=5) return t*9;
   if(x>=2&&x<=6&&y>=2&&y<=6) return t*8;
      if(x>=1&&x<=7&&y>=1&&y<=7) return t*7;
      return t*6;
}

void dfs(int cnt,int scr){
    if(cnt==0){
        ans=max(ans,scr);
    }
    int minv=10;
    int x,y;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(g[i][j]==0){
                if(one[get(i,j)]<minv){
                minv = one[get(i,j)];
                x=i,y =j;
            }
            }

        }
    }
    int st = get(x,y);
    for(int i=st;i;i-=lowbit(i)){
        int t=log_[lowbit(i)]+1;
        draw(x,y,t,true);
        dfs(cnt-1,scr+gets(x,y,t));
        draw(x,y,t,false);
    }
}
int main(){
    for(int i=0;i<9;i++)
        h[i]=l[i]=(1<<N)-1;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++) 
        k[i][j] = (1<<N)-1;
   for(int i=0;i<N;i++) log_[1<<i] = i;
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
        if(i>>j&1) one[i]++; //一的个数
    for(int i=0;i<9;i++)
    for(int j=0;j<9;j++)
    cin>>g[i][j];
    int cnt=0,scr=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(g[i][j]!=0){
                int t=g[i][j];
                draw(i,j,t,true);
                scr+=gets(i,j,t);
            }
            else cnt++;
        }
    }
    dfs(cnt,scr);
    cout<<ans;
    return 0;
}