题解：P10481 Sudoku

LostKeyToReach · 2024-05-16 17:52:50 · 题解

这是一道搜索题。

虽然我们直接搜索，不用优化也能通过此题，但我在这里讲一下位运算优化。

考虑分别用 9 个二进制数来表示每行、每列、每格哪些数用过了，那么我们想给某个数 x 打上标记，只需异或上 2^{x-1} 即可。

代码如下：

#include <iostream>
#include <bitset>
using namespace std;
int a[10][10];
#define bi bitset <9>
bool dfs(int h, int l);
int A[9], B[9], C[9];
void print() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            putchar(a[i][j] + '0');
        }
        putchar('\n');
    }
}
bool solve() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (a[i][j] != 0) {
                int num = a[i][j] - 1;
                A[i] ^= (1 << num);
                B[j] ^= (1 << num);
                C[i / 3 * 3 + j / 3] ^= (1 << num);
            }
        }
    }
    return dfs(0, 0);
}
bool dfs(int h, int l) {
    if (h == 9) return 1;
    if (l == 9) {
        return dfs(h + 1, 0);
    }
    if (a[h][l] != 0) {
        return dfs(h, l + 1);
    }
    for (int i = 0; i < 9; i++) {
        int idx = h / 3 * 3 + l / 3;
        if ((A[h] & (1 << i)) == 0 && (B[l] & (1 << i)) == 0 && (C[idx] & (1 << i)) == 0) {
            a[h][l] = i + 1;
            A[h] ^= (1 << i);
            B[l] ^= (1 << i);
            C[h / 3 * 3 + l / 3] ^= (1 << i);
            if (dfs(h, l + 1)) return 1;
            a[h][l] = 0;
            A[h] ^= (1 << i);
            B[l] ^= (1 << i);
            C[h / 3 * 3 + l / 3] ^= (1 << i);
        }
    }
    return 0;
}
int t;
int main() {
    ios::sync_with_stdio(0);
    cin >> t;
    while (t--) {
        for (int i = 0; i < 9; i++) A[i] = B[i] = C[i] = 0;
        for (int i = 0; i < 9; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < 9; j++) {
                a[i][j] = s[j] ^ 48;
            }
        }
        if (solve()) {
            print();
        }
    }
    return 0;
}