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

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
const int M = (1 << 10) + 10; // 2^10 个可能出现的数字

int g[N][N]; // 棋盘
// 行，列，九宫格分别用的状态压缩桶
// 索引：行，列，九宫格是0~8的索引
// 内容值：1~9位，状态压缩,0位没有用，不用管它。
int r[N], c[N], w[N];
bool flag;  // 是不是搜索到了第一个答案，如果是，则让其它搜索快速返回，剪一下枝
int one[M]; // 每个0~ 2^10-1 的数字当中，每个数字的二进制表示法中数字1的个数

// 方法1
#define lowbit(x) (x & -x)
int count(int x) {
    int cnt = 0;
    while (x) x -= lowbit(x), cnt++;
    return cnt;
}

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

void getPos(int &x, int &y) {
    int res = -1; // 每个位置上，已经占用数字最多的是多少个
    // 每次通过9*9的双重循环，枚举出每次哪个位置上需要尝试的数字数量是最少的
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (g[i][j]) continue;      // 如果已经填充过，就不用理
            int u = get(i, j);          // 第几个九宫格
            int t = r[i] | c[j] | w[u]; // 三者并集生成的数字
            if (one[t] > res) {         // 这个数字里面的数字1的个数如果大于当前值，修改之。找到1最多的位置
                res = one[t];           // 更新个数最大值
                x = i, y = j;           // 记录当前的坐标
            }
        }
    }
}

// cnt:还有多少个点需要填充
void dfs(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 x, y; // 记录当前找到的可能性最少的那个点,nx,ny:坐标，nu:哪个九宫格

    // 查询获取到最合理的位置作为尝试顺序
    getPos(x, y);

    // 这是第几个九宫格
    int u = get(x, y);
    for (int i = 1; i <= 9; i++) {
        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(cnt - 1);
        // 恢复现场
        r[x] -= 1 << i, c[y] -= 1 << i, w[u] -= 1 << i, g[x][y] = 0;
    }
}

int main() {
    // 预处理 0~ 2^N 中每个数字二进制表示中数字1的个数
    for (int i = 0; i < 1 << N; i++) one[i] = count(i);

    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);
        // 当前测试数据，还没有找到第一个合理解
        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;
            int u = get(x, y);
            g[x][y] = str[i] - '0';
            r[x] += 1 << g[x][y];
            c[y] += 1 << g[x][y];
            w[u] += 1 << g[x][y];
        }
        dfs(cnt);
    }
    return 0;
}