1.抽象处理。对99数独图进行抽象成九宫格，每个九宫格中是一个33的小九宫格。九个小九宫格中1-3列与1-3行的交集为第一个小九宫格cell[0][0]，那么cell[i/3][j/3]表示小九宫格。
2.对输入输出进行字符串处理，str[9*9]-‘1’转化0~8数值。
3.用row[i]表示行，每个row[i]取值范围为0~1<< N，二进制数位下标代表填数，列同理。
4.在做数独题时会优先选填方案数最少的空位，把可能填入的值遍历一遍，直到空格填满，假设本题有唯一解。

输入样例：

.2738..1..1…6735.......293.5692.8...........6.1745.364.......9518…7..8..6534.
......52..8.4......3…9…5.1…6..2..7........3.....6…1..........7.4.......3.
end
输出样例：

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

/
https://mp.weixin.qq.com/s/_vU8aaQ7BjfpySAOz61IMA
/

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N= 9;
int col[N],row[N],cell[3][3];
int one[1<<N],map[1<<N];//选择个数最少的，有多少种选择
char str[100];

void  init(){//全为1
    for(int i=0;i<N;i++) col[i]=row[i]=(1<<N)-1;
    for(int i=0;i<3;i++)
      for(int j=0;j<3;j++)
      {
          cell[i][j]=(1<<N)-1;
      }
}
int lowbit(int x){
    return x&-x;
}
//可选方案交集
int get(int x,int y)
{
    return row[x]&col[y]&cell[x/3][y/3];
}
bool dfs(int k)
{
    if(k==0)return true;
    //寻找方案数最少的位置（x,y）
    int minv=10;//总的方案数是9，即每个位置能填的数是1到9
    int x,y;//记录方案数最小的位置

    for(int i=0;i<9;i++)
     for(int j=0;j<9;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)];//回溯
            row[x]-=1<<t;
            col[y]-=1<<t;
            cell[x/3][y/3]-=1<<t;
            str[x*9+y]=t+'1';
            if(dfs(k-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和one 进行优化剪枝用下标对应所填数值，初始所有位当置1
    for(int i=0;i<N;i++) map[1<<i]=i; //最低位的1是在第几位

    //统计第i位可选的方案数
    for(int i=0;i<1<<N;i++){
       int s=0;
       for(int j=i;j;j-=lowbit(j)) s++;  //统计第i个位置可选的方案数
       one[i]=s;
    } 


    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] !='.')
          {//当在（i,j）处有数时，行i列j下标对应的二进制位以及所在的小九宫格位 置0
             int t=str[k]-'1';
             row[i] -= 1<<t;
             col[j] -= 1<<t;
             cell[i/3][j/3] -= 1<<t;
          }
          else  cnt++;//统计有几个空位置

    dfs(cnt); //  对所有空格遍历并填数，规则：可选择的填数方案最少位置优先

      cout<<str<<endl;
    }
    return 0;
}