题解 | #Sudoku#

用bitset标记每个行、列、组 1~9的出现，暴力搜索即可

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 15;
int a[N][N];
bitset<N>row[N], column[N], group[N];
vector<pair<int,int>>vec;

void setVal(int i, int j, int pos, int val) {
    row[i].set(pos, val);
    column[j].set(pos, val);
    group[i/3*3+j/3].set(pos, val);
}

bool tryToSet(int i, int j, int pos, int val) {
    if (!row[i][pos] && !column[j][pos] && !group[i/3*3+j/3][pos]) {
        setVal(i, j, pos, val);
        return true;
    }
    return false;
}

bool dfs(int id) {
    if(id == vec.size()) return true;
    for (int i = 1; i <= 9; ++i) {
        if (tryToSet(vec[id].first, vec[id].second, i, 1)) {
            if(dfs(id + 1)) {
                a[vec[id].first][vec[id].second] = i;
                return true;
            }
            setVal(vec[id].first, vec[id].second, i, 0);
        }
    }
    return false;
}

int main() {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            scanf("%d", &a[i][j]);
            if (a[i][j] != 0) {
                setVal(i, j, a[i][j], 1);
            } else {
                vec.push_back({i, j});
            }
        }
    }
    if(!vec.empty()) dfs(0);
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j, j==9?printf("\n"):printf(" ")) {
            printf("%d", a[i][j]);
        }
    }
}
// 64 位输出请用 printf("%lld")