分析

• 我们可以依次填写每个空格，枚举所有情况即可。

• 考虑如何剪枝：

（1）优化搜索顺序：我们应该分支较少的格子，即可填数字较少的格子。

（2）排除等效冗余：无

（3）可行性剪枝：当前空位中所填写的内容不能与所在行、列、九宫格有重复数组。

（4）最优性剪枝：无。

• 另外我们还可以使用位运算优化：

我们可以使用一个9位的二进制数据表示某一行或者某一列或者某个九宫格的状态，二进制位是0代表可以该行中已经有该数据了，比如0b110100000代表该行（或者该列、或者该九宫格）还可以填写9或者8或者6。

求解二进制中最右侧的1可以使用lowbit操作。

#include <iostream>

using namespace std;

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

int ones[M], map[M];  // ones[i]表示i二进制表示中1的个数; map[i]表示log2(i)
int row[N], col[N], cell[3][3];  // 二进制优化
char str[100];

// 将row, col, cell二进制标识全部置为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;
}

// is_set = true的话，在(x, y)放置上数字t，否则取消放置
void draw(int x, int y, int t, bool is_set) {
    if (is_set) str[x * N + y] = '1' + t;
    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 lowbit(int x) {
    return x & -x;
}

// 获取(x, y)位置可以放置的数据
int get(int x, int y) {
    return row[x] & col[y] & cell[x / 3][y / 3];
}

// cnt: 目前剩余需要填写位置的数量
bool dfs(int cnt) {

    if (!cnt) 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) {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    int state = get(x, y);
    for (int i = state; 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 < 1 << N; i++)
        for (int j = 0; j < N; j++)
            ones[i] += i >> j & 1;

    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';
                    draw(i, j, t, true);
                }
                else cnt++;

        dfs(cnt);

        puts(str);
    }

    return 0;
}