详细请看注释内容

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

int map[M], ones[M];
int row[N], col[N], cell[3][3];
char g[100];

/*
    二进制优化：
        1：表示待填
        0：表示已填

    搜索+剪枝
        优化搜索顺序：从分支少的点开始搜，即可选填法最少的开始搜索
        可行性剪枝：自然行列和九宫格不能重复
        位运算优化：使用位运算（九个二进制位）表示行列九宫格已填数字
            对于当前位置可选方案的判断：row[x] & col[y] & cell[x / 3][y / 3] 
                ---> 即可得到该位置在三个方向共同可以填的数的方案！

        为了方便获得对应二进制位1的个数用于统计是否是分支最少的点的时候，可以使用数组预处理0-2^9的数中的1的个数
        为了方便获得对应二进制位1对应的0-9可以预处理map得到2^i与i的映射关系！--> 对应数组 t = map[lowbit(x)]

*/

// 初始化操作：全部设置为9个1
void init(){
    // 行列
    for(int i = 0; i < N; i ++) row[i] = col[i] = (1 << N) - 1;
    // 九宫格
    for(int i = 0; i < 3; i ++)
        for(int j = 0; j < 3; j ++) 
            cell[i][j] = (1 << N) - 1;
}

// 填充和恢复操作
// x,y点处填入数字t，is_set：表示是填充还是恢复
void draw(int x, int y, int t, bool is_set){

    // 1. 处理字符串填充和恢复
    if(is_set) g[x * N + y] = '1' + t;
    else g[x * N + y] = '.';

    // 2. 处理二进制标记数组填充和恢复
    // 使用二进制表示哪个位置填了或未填！
    int v = 1 << t;
    // 若为恢复则取相反数，即原来-v，恢复则为-(-v)即为+v，即可恢复回去！
    if(!is_set) v = -v;
    row[x] -= v, col[y] -= v, cell[x / 3][y / 3] -= v;
}

// 返回最后一个1
int lowbit(int x){
    return x & -x;
}

// 返回x行j列该位置的可填数字情况
int get(int x, int y){
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt){
    // 没有需要填的位置，直接返回
    if(!cnt) return true;

    // 选择可选分支最少的，属于剪枝优化之优化搜索顺序！
    int minv = 10, x, y;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            if(g[i * N + j] == '.'){
                int status = get(i, j);
                // ones：表示当前状态的1的个数，即可填方案数
                if(ones[status] < minv){
                    minv = ones[status];
                    x = i, y = j;
                }
            }

    int status = get(x, y);
    // 枚举每一种填法
    for(int i = status; i; i -= lowbit(i)){
        // 获取最后一位1对应的2的指数幂对应的幂，即获取该位置应该填 1-9的谁
        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(){

    // 预处理 2^i 与 i 的映射
    for(int i = 0; i < N; i ++) map[1 << i] = i;
    // 预处理0-2^9的数中每个数中1的个数
    for(int i = 0; i < 1 << N; i ++)
        for(int j = 0; j < N; j ++)
            ones[i] += i >> j & 1;

    while(cin >> g, g[0] != 'e'){
        // 初始化行列和九宫格二进制位都为1
        init();

        // 统计需要填充位置
        int cnt = 0;
        for(int i = 0, k = 0; i < N; i ++)
            for(int j = 0; j < N; j ++, k ++)
                if(g[k] != '.'){
                    // 将一长串字符串转化到 行列九宫格 的二进制为用0表示
                    int t = g[k] - '1';
                    draw(i, j, t, true);
                }else cnt ++;

        dfs(cnt);
        cout << g << endl;
    }
    return 0;
}