C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=9, M=1<<N;

int ones[M];// 表示i的二进制表示中有多少位1
int map[M];// 表示一个二进制数的1在第几位
int row[N], col[N], cell[3][3];//每一行每一列每一个九宫格用一个2进制串表示状态
char str[100];

//返回二进制数的最后一位以1开头的数，如10100则返回100
inline int lowbit(int x)
{
    return x&(-x);
}

//初始化状态
void init()
{
    //刚开始1-9都没有用过，全部都为1
    for(int i=0; i<N; i++) row[i]=col[i]=(M-1);
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            cell[i][j]=M-1;
}

//求x,y位置对应的行、列、九宫格的可选可能的交集
inline int get(int x, int y)
{
    return row[x] & col[y] & cell[x/3][y/3];
}

//对cnt个位置进行填充
bool dfs(int cnt)
{
    if(cnt==0) return true;

    //优化:先对可选方案数最少的空格进行填
    int minv=10;//10就是无穷大
    int x, y;//记录位置
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            if(str[i*9+j]=='.')
            {
                int t=ones[get(i, j)];//看看这个位置有多少个数可选
                if(t< minv)
                {
                    minv=t;
                    x=i, y=j;
                }
            }

    //进行选数填充
    for(int i=get(x, y); i; i-=lowbit(i))//每次减去一个可选状态
    {
        int t=map[lowbit(i)];//记录1所在的位置是第一个，对应到0-8；

        //修改各个状态
        row[x]-=1<<t;
        col[y]-=1<<t;
        cell[x/3][y/3]-=1<<t;
        str[x*9+y]='1'+t;//0-8, 所以映射要从1开始

        //继续往下搜
        if(dfs(cnt-1)) return true;

        //恢复现场
        row[x]+=1<<t;
        col[y]+=1<<t;
        cell[x/3][y/3]+=1<<t;
        str[x*9+y]='.';
    }

    return false;
}

int main()
{
    //初始化map和ones
    for(int i=0; i<N; i++) map[1<<i]=i;
    for(int i=0; i<M; i++)
    {
        int sum=0;
        for(int j=i; j; j-=lowbit(j)) sum++;//统计每个二进制数有多少个1
        ones[i]=sum;
    }

    while(cin>>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';//映射到从0-8，所以要减一
                    row[i]-=1<<t;//有数的话，相应位置标记为0
                    col[j]-=1<<t;
                    cell[i/3][j/3]-=1<<t;
                }
                else cnt++;
        }

        dfs(cnt);

        puts(str);
    }

    return 0;
}

作者：sailor
链接：https://www.acwing.com/activity/content/code/content/1109507/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。