题解 | #Sudoku# 位运算+DFS+回溯

#include <iostream>
using namespace std;
char board[9][9];
int rs[9], cs[9], bs[9];
void set(int i, int j, int b, int n) {
    rs[i] |= (1 << n), cs[j] |= (1 << n), bs[b] |= (1 << n);
}
void reset(int i, int j, int b, int n) {
    rs[i] ^= (1 << n), cs[j] ^= (1 << n), bs[b] ^= (1 << n);
}
bool dfs(int i, int j) {
    if (j == 9) return dfs(i + 1, 0);
    if (i == 9) return true;
    if (board[i][j] != '0') return dfs(i, j + 1);
    for (int k = 1; k <= 9; ++k) { 
        int b = i / 3 * 3 + j / 3;
        if (!(rs[i] >> k & 1) && !(cs[j] >> k & 1) && !(bs[b] >> k & 1)) {
            set(i, j, b, k);
            board[i][j] = k + '0';
            if (dfs(i, j + 1)) return true;
            board[i][j] = '0';
            reset(i, j, b, k);
        }
    }
    return false;
}
int main() {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> board[i][j]; 
            if (board[i][j] != '0')
                set(i, j, i / 3 * 3 + j / 3, board[i][j] - '0');
        }
    }
    dfs(0, 0);
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (j != 0) cout << " ";
            cout << board[i][j];
        }
        cout << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")