P10482 Sudoku2 题解

xiaomo8125 · 2024-11-28 21:35:18 · 题解

P10482 Sudoku2

蓝书上来的，看到没有人写 DFS 位运算常数优化，于是来写一下，帮助其他和我一样不会的蒟蒻

常数优化

对于每行、每列、每个九宫格，分别用一个 9 位二进制数（全局整数变量）保存哪些数字还可以填

对于每个位置，把它所在行、列、九宫格的 3 个二进制数做位与运算（&），就可以得到该位置能填哪些数，用 lowbit 运算就可以把能填的数字取出

当一个位置填上某数后，把该位置所在的行、列、九宫格记录的二进制数的对应位改为 0 ，即可更新当前状态；回溯时改回 1 即可还原现场。

——《算阶》

更多细节下见代码

#include<iostream>
#define N (1 << 9)//如果写define位运算一定要记得写括号！！！
#define lowbit(x) (x & -x)
using namespace std;
int T,n,a[10][10];
int cnt[N],f[N],x[9],y[9],z[9];
char c;
int gon(int i,int j){//在第几个九宫格
    return i / 3 * 3 + j / 3;
}
int get_cnt(int i){//二进制下有多少个1，即为可填的数字个数
    int ans=0;
    while(i) ans++ , i-=lowbit(i);
    return ans;
}
void work(int i,int j,int v){
    x[i] ^= (1<<v);//异或的成对变换的运用
    y[j] ^= (1<<v);
    z[gon(i,j)] ^= (1<<v);
}
bool dfs(int tot){
    if(!tot)return true;//找到则返回
    int t=10,nx,ny;
    for(int i=0;i<=8;i++){
        for(int j=0;j<=8;j++){
            if(!a[i][j]){
                int w = x[i] & y[j] & z[gon(i,j)];
                if(cnt[w]<t) nx=i,ny=j,t=cnt[w];//找到能填数目最小的
            }
        }
    }   
    int w=x[nx]&y[ny]&z[gon(nx,ny)];
    while(w){
        int now=f[lowbit(w)];
        a[nx][ny]=now+1;
        work(nx,ny,now);
        if(dfs(tot-1)) return true;
        a[nx][ny]=0;
        work(nx,ny,now);//回溯
        w-=lowbit(w);
    }
    return false;
}
int main(){
    for(int i=0;i<N;i++){
        cnt[i]=get_cnt(i);
    }
    for(int i=0;i<=8;i++){
        f[1<<i]=i;
    }
    while(1){
        int tot=0;
        for(int i=0;i<=8;i++){
            x[i]=y[i]=z[i]=N-1;
        }
        for(int i=0;i<=8;i++){
            for(int j=0;j<=8;j++){
                cin>>c;
                if(c=='e'){
                    return 0;
                }
                else if(c=='.')
                    a[i][j]=0;
                else{
                    a[i][j]=c-'0';
                }
                if(a[i][j]) work(i,j,a[i][j]-1);
                else{
                    tot++;
                }
            }
    }
        if(dfs(tot)){
            for(int i=0;i<=8;i++){
                for(int j=0;j<=8;j++){
                    printf("%d",a[i][j]);
                }
            }
        }
        cout<<endl;
    }
    return 0;
}