题解 P1784 【数独】

· · 题解

先献上我的提交记录

我现在还觉得，数独的依靠算法建立的正解是位运算+dfs剪枝，所以我这次又下意识的敲了这种写法，没开o2跑了14ms(这道题直接被我写成了蓝题)

这道题的数据是很水的，只有3个点，所以一般的搜索应该也能过。但是我看了一遍题解以及最优提交记录，发现不是打表就是DLX，还有一些玄学优化，而且码长也都比较长，这使本蒟蒻找到了一些优越感。

9*9的数独，常规做法时间复杂度很高，如果是POJ3074的数据还很容易TLE。所以我们采用位运算来存储当前位置是否能填下这个数字，便于处理。

1.对于每行，每列，每个九宫格，我们使用一个9位二进制数(全局int变量)存下哪些数还可以填(后文用1表示可以填，代码中会提到原因)

2.对于每个位置，将该位置所在行，列，九宫格的二进制数做&(位与)运算，可以得到该位置可填哪些数。(因为根据数独规则，在该行不能填，定然不能填，符合&运算的短路性质)

e.g:

上图中被框住的位置，它所在行row所能填的数字(1,2,4,5,7,8,9)，9位二进制数表示[111011011]，所在列col所能填的数字(1,2,3,5,6,7,8),9位二进制数表示[011110111],其所在九宫格grid所能填的数字(1,2,3,4,5,7,8),9位二进制数表示[011011111]。 综合得出该位置可填(1,2,5,7,8),也可通过计算得出row&col&grid=[011010011],得出相同结果。

3.一个位置填上某个数后，把该位置所在的行,列,九宫格记录的对应二进制位改为0，表示不可填入该数字，回溯时改回1，(同bool数组)。

4.盲目搜索耗费时间，如果是人来填数独肯定选能填数字最少的位置，所以我们可以优先搜索这些位置。但切忌搜索时枚举所有的位置和可填的数字，这样会重复遍历同一状态的搜索树，降低搜索效率。

建议看完这些思想后先自己动手敲一遍，如果是做完了看题解的也权当了解一下，印象会更深刻，毕竟与DLX这样的数据结构相比,以及直接抄题解相比，算法思想的锻炼才是最重要的。

代码飞来~~

#include<bits/stdc++.h>
using namespace std;
int row[9],col[9],grid[9];//000000000~111111111 可行性数组 1表示可以填 
//2^9=32*16=512     2^8+5=256+5=261
int cnt[512],num[261];//二进制数中含有1的个数(各个状态中可选择的数的个数)  lowbit对应的hash
int rec[9][9];
inline int g(int x,int y){//很灵性的公式 
    return ((x/3)*3)+(y/3);
}
void flip(int x,int y,int z){//对该位置填z后的回溯和标记(xor) 
    //未标记->标记->未标记(xor的可逆性) 
    row[x]^=1<<z;//1<<z=pow(2,z)
    col[y]^=1<<z;
    grid[g(x,y)]^=1<<z;
}
bool dfs(int now){//当前有now个数可填的状态 
    if(!now)    return true;//填完了
    int temp=10,x,y;
    for(int i=0;i<9;++i){
        for(int j=0;j<9;++j){
            if(rec[i][j])   continue;
            int val=row[i]&col[j]&grid[g(i,j)];//该位置上可以填的数的个数
            if(!val)    return false;//1个也不能填，回溯
            if(temp>cnt[val]){//temp取当前位置可以填的最少的数的个数，并记录下这个位置
                temp=cnt[val];
                x=i;y=j;
            }
        }
    }
    //(x,y)可以填的数的个数
    int val=row[x]&col[y]&grid[g(x,y)];
    for(;val;val-=val&(-val)){
        int z=num[val&(-val)];
//      rec[x][y]=z;//Error
        rec[x][y]=z+1; //之所以加1与二进制标记数组的定义有关 
        flip(x,y,z);
//      flip(x,y,z-1);//Error 
        if(dfs(now-1))  return true;
        rec[x][y]=0;
        flip(x,y,z);
//      flip(x,y,z-1);//Error 
    }
    return false;//无解，返回上一层 
}
int main(){
    for(int i=0;i<(1<<9);++i){
        //i的二进制数中含有1的个数 即各个状态中可选择的数的个数
        //预处理降低时间复杂度
        //e.g:cnt[100010001(二进制数)] = 3
        for(int j=i;j;j-=j&(-j)){
            ++cnt[i];
        }
    }
    for(int i=0;i<9;++i){
        //lowbit(1 << i)的hash,能找出lowbit(1 << i)所对应的第一个1的位置 
        num[1<<i]=i;
    }
    for(int i=0;i<9;++i){
        //初始化行，列，九宫格标记数组
        //每个数都可以填 
        row[i]=col[i]=grid[i]=(1<<9)-1;
    }
    for(int i=0;i<9;++i){
        for(int j=0;j<9;++j){
            scanf("%d",&rec[i][j]);
        }
    }
    //初始化计数器 
    int tot=0;
    for(int i=0;i<9;++i){
        for(int j=0;j<9;++j){
            if(rec[i][j]) flip(i,j,rec[i][j]-1);//进行标记  之所以 -1与flip函数的定义有关 
            else    ++tot;//如果rec[i][j]是0，表示该位置还没有填数 
        }
    }
    dfs(tot);
//  printf("\n");
    for(int i=0;i<9;++i){
        for(int j=0;j<9;++j){
            printf("%d ",rec[i][j]);
        }
        printf("\n");
    }
    return 0;
}