acwing166. 数独

题目

题解

类比leetcode37解数独，这里时间要求比较高，所以不能穷举每一种情况，需要提前打表

每行每列以及每个小的九宫格初始状态：111111111
表示这列或者这行或者这个小九宫格的为1的位置可以填的数：0,1,2,3,4,5,6,7,8
所以只需要维护这个数值state即可。

刚开始所有的位置都为111111111,然后在init（）中将是数字的位置对应的二进制除去，如第一个样例：4…8.5.3…7…2…6…8.4…1…6.3.7.5…2…1.4…

第一个数（0,0）填的4，那么第一行和第一列的状态就变成了011111111

以后在没有填数的地方开始填，填的时候取三个数字的与得到的state，然后就可以知道这个位置可以填哪些状态，这里可以优化，填的时候向最少的方案数填，这样可以减少分支数，填了再将这个位置对应的二进制数所在的位置变0。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9,M=1<<9; 
char str[100];
int row[N],col[N],cell[3][3];
int ones[M],map[M];
int lowbit(int x){
    return x&-x;
}
void draw(int x,int y,int t,bool is_set){
    if(is_set)str[x*N+y]=t+'1';
    else str[x*N+y]='.';
    int v=1<<t;
    if(!is_set)v=-v;
    row[x]-=v;
    col[y]-=v;
    cell[x/3][y/3]-=v;
}
int get(int x,int y){
    return row[x]&col[y]&cell[x/3][y/3];
}
int init(){
    int cnt=0;//表示还有多少个位置要填
    int state=(1<<N)-1;
    fill(row,row+N,state);
    fill(col,col+N,state);
    fill(cell[0],cell[0]+N,state);
    for(int i=0,k=0;i<N;i++){
        for(int j=0;j<N;j++,k++){
            if(str[k]!='.'){
                draw(i,j,str[k]-'1',true);
            }else cnt++;
        }
    }
    return cnt;
}
bool dfs(int cnt){
    if(cnt==0)return true;
    int minv=10;
    int x,y;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(str[i*N+j]=='.'){
                int state=get(i,j);
                if(ones[state]<minv){
                    x=i,y=j;
                    minv=ones[state];
                }
            }
        }
    }
    for(int i=get(x,y);i;i-=lowbit(i)){
        int t=map[lowbit(i)];
        draw(x,y,t,true);
        if(dfs(cnt-1))return true;
        draw(x,y,t,false);
    }
    return false;
}
int main(){
    for(int i=0;i<N;i++){
        map[1<<i]=i;
    }
    for(int i=0;i<M;i++){
        for(int j=i;j;j-=lowbit(j)){
            ones[i]++;
        }
    }
    while(cin>>str,str[0]!='e'){
        int cnt=init();
        dfs(cnt);
        puts(str);
    }
    
    return 0;
}