题目：AcWing 166. 数独

这是一道很复杂的题

之前一直喜欢下标从 $1$ 开始，因为这样很多时候能避免下标越界等问题，关键是符合我们一般的思维。

直到遇到了这道题......

大部分同学一开始应该都是按照y总代码的下标从 $0$ 写的，但我偏不，因为这不符合我的习惯。

$two$ $thousands$ $years$ $later$ $......$

我写好代码后，调了 $4$ 个小时也没有调 $AC$ 😵

最后，我还是向下标从 $0$ 开始屈服了，因为这道题里确实下标从 $0$ 开始更方便（bushi）

以后要长记性~~~

这是下标从 $0$ 开始的 $AC$ 代码：

#include <bits/stdc++.h>

using namespace std;

int mp[1 << 9]; // mp[1 << i]表示2的几次方是1 << i
int ones[1 << 9]; // ones[i]表示数字i的二进制中有几个1
char s[81];
int hang[9], lie[9], cell[3][3];
// hang[2] = 000001000表示第一行还剩数字2^3需要填
// 这里把原来数独中的1~9映射为0~8

inline int lowbit(int x) {
    return x & -x;
}

// 取三个条件下“可以使用的数字”的交集
int get(int x, int y) {
    return hang[x] & lie[y] & cell[x/3][y/3];
}

int dfs(int op) {
    if (!op)
        return 1;
    // 找出可选方案数最少的空格
    int x, y, leave_min = 8 + 1;
    for (int i = 0, k = 0; i <= 8; i ++) {
        for (int j = 0; j <= 8; j ++, k ++) {
            if (s[k] == '.') {
                int t = get(i, j); // 这是一个9位二进制数
                if (ones[t] < leave_min) {
                    leave_min = ones[t];
                    x = i;
                    y = j;
                }
            }
        }
    }
    for (int i = get(x, y); i; i -= lowbit(i)) {
        s[9 * x + y] = mp[lowbit(i)] + '0' + 1;
        // 后边+1是因为0~8数字只是映射，实际是1~9
        hang[x] -= lowbit(i);
        lie[y] -= lowbit(i);
        cell[x / 3][y / 3] -= lowbit(i);
        if (dfs(op - 1))
            return 1;
        s[9 * x + y] = '.';
        hang[x] += lowbit(i);
        lie[y] += lowbit(i);
        cell[x / 3][y / 3] += lowbit(i);
    }

    return 0; 
}

int main() {

    for (int i = 0; i <= 8; i ++) {
        mp[1 << i] = i; // mp[1 << i]表示2的几次方是1 << i
    }
    for (int i = 0; i <= 1 << 9; i ++) {
        int j = i;
        while (j) {
            if (j & 1) {
                ones[i] ++;
            }
            j >>= 1;
        }
    }

    while (cin >> s, *s != 'e') {
        // 还原为初始状态（每个小格子都可以使用0~8所有数字）
        for (int i = 0; i <= 8; i ++) {
            hang[i] = lie[i] = (1 << 9) - 1;
        }
        for (int i = 0; i <= 2; i ++) {
            for (int j = 0; j <= 2; j ++) {
                cell[i][j] = (1 << 9) - 1;
            }
        }
        // 初始化
        int op = 0; // 需要填充/操作的次数
        for (int i = 0, k = 0; i <= 8; i ++) {
            for (int j = 0; j <= 8; j ++, k ++) {
                if (s[k] != '.') {
                    int t = s[k] - '0' - 1; // 0 ~ 8
                    hang[i] -= 1 << t;
                    lie[j] -= 1 << t;
                    cell[i/3][j/3] -= 1 << t;
                }
                else {
                    op ++;
                }
            }
        }
        // dfs填充op次数独
        dfs(op);
        // 输出新数独
        cout << s << endl;
    }

    return 0;
}