DFS之剪枝与优化AcWing 166. 数独

迷南。 2024-04-07 11:30 65阅读 0赞

## DFS之剪枝与优化AcWing 166. 数独 ##

### 原题链接 ###

[AcWing 166. 数独][AcWing 166.]

### 算法标签 ###

搜索 深度优先搜索 DFS

### 思路 ###

优化搜索顺序: 从当前能填合法数字最少的位置开始填数字  
排除等效冗余: 任意一个状态下,我们只需要找一个位置填数即可,而不是找所有的位置和可填的数字.  
位运算:由于涉及大量check判定（即判断数字放在该行， 列， 九宫格）,对check进行优化,  
优化方式  
对于每一行,每一列,每一个九宫格,利用一个九位二进制数保存,当前还有哪些数字可以填写.  
lowbit: 取出当前可以能填的数字.

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N=9, M=1<<N;
    //ones表示0-2^9（二进制）里1的个数，mp找出该行哪一列可以填写数字，如mp[(10)2] = 1则第二列可以填1
    int ones[M], mp[M];
    //分别表示行，列，大方格中尚未填写的数字
    int r[N], c[N], cell[3][3];
    char str[86];
    //int t, n, m, cnt, ans; 
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    void init(){
    	//初始状态9位二进制全是1 即所有位置可填写
        rep(i, 0, N){
            r[i]=c[i]=(1<<N)-1;
        }
        rep(i, 0, 3){
            rep(j, 0, 3){
                cell[i][j]=(1<<N)-1;
            }
        }
    }
    // is_set = true表示（x, y）填上t, 否则则把x,y处的数字删掉, t 是0-8
    void draw(int x, int y, int t, bool is_set){
        if(is_set){
            str[x*N+y]='1'+t;
        }else{
            str[x*N+y]='.';
        }
        int v=1<<t;
        if(!is_set){
            v=-v;
        }
        //如果某位尚未选择，对应二进制位为1， 故应减v， 将1变为0
        //如果某位已选择，它的二进制为0，经上面取反，负负得正，将0变为1
        r[x]-=v;
        c[y]-=v;
        cell[x/3][y/3]-=v;
    }
    int lowbit(int x){
        return x&-x;
    }
    // 对于位于（x, y）的格子 合法数字选择
    int get(int x, int y){
        return r[x]&c[y]&cell[x/3][y/3];
    }
    // cnt表示还剩余未填写格子数
    bool dfs(int cnt){
        if(!cnt){
            return true;
        }
        // 最多可以填数字个数
        int minv=10;
        int x, y;
        rep(i, 0, N){
            rep(j, 0, N){
                if(str[i*N+j]=='.'){
                 //可填的数字状态，如010001，是1则表示可以填
                    int state=get(i, j);
                     //选择个数最少的1，使分支数量最少
                    if(ones[state]<minv){
                        minv=ones[state];
                        x=i, y=j;
                    }
                }
            }
        }
        int state=get(x, y);
        // 做lowbit操作，选择每个分支
        for(int i=state; i; i-=lowbit(i)){
         // t为填充的数字
            int t=mp[lowbit(i)];
            // 填充数字t
            draw(x, y, t, true);
            // 填充成功，则返回
            if(dfs(cnt-1)){
                return true;
            }
            // 失败回溯 
            draw(x, y, t, false);
        }
        return false;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	//打表，得知该位置可以填写哪一个数字
    	rep(i, 0, N){
    	    mp[1<<i]=i;
    	}
    	rep(i, 0, 1<<N){
    	    rep(j, 0, N){
    	        ones[i]+=i>>j&1;
    	    }
    	}
    	while(scanf("%s", str), str[0]!='e'){
    	    init();
    	    int cnt=0;
    	    for(int i=0, k=0; i<N; ++i){
    	        for(int j=0; j<N; ++j, ++k){
                if(str[k]!='.'){
                    int t=str[k]-'1';
                    draw(i, j, t, true);
                }else{
                    cnt++;
                }
    	        }
    	    }
    	    dfs(cnt);
    	    puts(str);
    	}
    	return 0;
    }

参考文献  
[AcWing 166. 数独（算法提高课）y总讲解][AcWing 166. _y]  
[AcWing 166. 数独题解][AcWing 166. 1]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 166.]: https://www.acwing.com/problem/content/168/
[AcWing 166. _y]: https://www.acwing.com/video/479/
[AcWing 166. 1]: https://www.acwing.com/solution/content/31873/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6d26568cc5704a2eb59df9e2d868e45e.png