POJ - 3074 Sudoku （搜索）剪枝+位运算优化

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstring>
#define Swap(a,b) a^=b^=a^=b
#define cini(n) scanf("%d",&n)
#define cinl(n) scanf("%lld",&n)
#define cinc(n) scanf("%c",&n)
#define cins(s) scanf("%s",s)
#define coui(n) printf("%d",n)
#define couc(n) printf("%c",n)
#define coul(n) printf("%lld",n)
#define speed ios_base::sync_with_stdio(0)
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define mem(n) memset(n,0,sizeof(n))
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=1e6+10;
const double esp=1e-9;
//-------------------------------------------------------//

const int N=9;
char a[N*N+N];
int R[9],L[9],C[3][3];
int one[1<<N],mp[1<<N];//通过lowbit，找到每一位1对应的位置
inline int lowbit(int n)
{
    return n&-n;
}
inline void init()//初始化，每个状态位赋值为1
{

    for(int i=0; i<N; i++){
        R[i]=L[i]=(1<<N)-1;
    }

    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            C[i][j]=(1<<N)-1;
}
inline int get(int x,int y) // 找到当前位置能填的状态
{
    return L[y]&R[x]&C[x/3][y/3];
}
bool dfs(int n)
{
    if(n==0)
        return 1;
   //cout<<n<<‘ ‘;
    int x,y,mini=10;
    for(int i=0; i<N; i++) //寻找最少填数点
    {
        for(int j=0; j<N; j++)
        {
            if(a[i*N+j]!=‘.‘)
                continue;
            int minT=one[get(i,j)];
            if(minT<mini)
            {
                x=i;
                y=j;
                mini=minT;
            }
        }
    }
    //cout<<x<<‘ ‘<<y<<endl;
    int T=get(x,y);
   //cout<<T<<endl;
    for(int i=T; i; i-=lowbit(i)) //遍历每一位1所代表的的状态，看不懂状态，打个表就行了。
    {
        int w=mp[lowbit(i)];
        a[x*N+y]=w+‘1‘;
        R[x]-=1<<w;
        L[y]-=1<<w;
        C[x/3][y/3]-=1<<w;
        if(dfs(n-1))
            return 1;
        a[x*N+y]=‘.‘;
        R[x]+=1<<(w);
        L[y]+=1<<(w);
        C[x/3][y/3]+=1<<w;
    }
    return 0;
}
int main()
{
    for(int i=0; i< 1<<N; i++)
    {
        int s=0;
        for(int j=i; j; j-=lowbit(j))s++;
        one[i]=s; //统计2的N次方内所有的数的1的个数，这样用到时就不用算了
    }
    for(int i=0;i<N;i++) mp[1<<i]=i;
    while(cin>>a&&a[0]!=‘e‘)
    {
        int k=0,cnt=0;
        init();
        for(int i=0; i<N; i++) //预处理，得到还有多少数需要填，处理一下状态
        {
            for(int j=0; j<N; j++,k++)
            {
                if(a[i*N+j]==‘.‘)
                {
                    cnt++;
                    continue;
                };
                int T=(1<<(a[k]-‘1‘));
                R[i]-=T;//代表这一行的状态中填了a[k]这个数了
                L[j]-=T;
                C[i/3][j/3]-=T;
            }
        }
        if(dfs(cnt))
            cout<<a<<endl;
    }
}