python/TangDou/AcWing/JianZhi/166_1.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 10;
int g[N][N]; // 棋盘
// 行，列，九宫格分别用的状态压缩桶
// 索引：行，列，九宫格是0~8的索引
// 内容值：1~9位，状态压缩,0位没有用，不用管它。
int r[N], c[N], w[N];
bool flag; // 是不是搜索到了第一个答案，如果是，则让其它搜索快速返回，剪一下枝

// 返回九宫格的编号
int get(int x, int y) {
    x /= 3, y /= 3;   // 注意两个都是/3，表示是第几个小方块，可以理解为0~8，共9个小方块
    return x * 3 + y; // 通过上面的变换，映射到0~8数字上
}

// x,y这个坐标开始暴搜
// cnt:还有多少个点需要填充
void dfs(int x, int y, int cnt) {
    if (flag) return; // 快速返回，剪枝
    if (cnt == 0) {   // 没有空格子了
        // 输出答案
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                cout << g[i][j];
        cout << endl;
        // 修改第一次完成的标识
        flag = true;
        return;
    }

    int nx = x, ny = y + 1;    // 下一个位置,默认是向右
    if (ny == 9) nx++, ny = 0; // 越界了就从下一行开始

    if (g[x][y] == 0) {                // 如果此位置是空白
        int u = get(x, y);             // 这是第几号九宫格
        for (int i = 1; i <= 9; i++) { // 尝试填充1~9
            if (r[x] >> i & 1) continue;
            if (c[y] >> i & 1) continue;
            if (w[u] >> i & 1) continue;
            // 修改状态，修改棋盘
            r[x] += 1 << i, c[y] += 1 << i, w[u] += 1 << i, g[x][y] = i;
            // 尝试下一个位置
            dfs(nx, ny, cnt - 1);
            // 恢复状态
            r[x] -= 1 << i, c[y] -= 1 << i, w[u] -= 1 << i, g[x][y] = 0;
        }
    } else // 如果此位置不是空白，那么就尝试下一个位置
        dfs(nx, ny, cnt);
}
int main() {
    string str; // 输入的棋盘
    while (cin >> str && str[0] != 'e') {
        // 初始化
        memset(g, 0, sizeof g); // 清空地图
        memset(r, 0, sizeof r); // 清空行的标识
        memset(c, 0, sizeof c); // 清空列的标识
        memset(w, 0, sizeof w); // 清空9个小方块的标识
        // 找到第一个方案的停止标识
        flag = false;

        // 记录需要填充的空位数量
        int cnt = 0;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '.') {
                cnt++;
                continue;
            }
            // 转换为行列坐标
            int x = i / 9, y = i % 9; // x:行，y:列
            int u = get(x, y);        // 0~8哪个九宫格
            g[x][y] = str[i] - '0';   // 棋盘上放上数字
            r[x] += 1 << g[x][y];     // 本质上是一个状态压缩，用二进制方式描述 x行上 g[x][y]这个数字的占用情况，1表示已使用，0表示未使用
            c[y] += 1 << g[x][y];     // 列也用状态压缩描述
            w[u] += 1 << g[x][y];     // 九宫格也用状态压缩描述
        }
        // 从左上角暴搜,cnt描述还有多少个位置需要搜索，当cnt==0时停止
        dfs(0, 0, cnt);
    }
    return 0;
}