P1784 数独 参考代码

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

#define endl '\n'

typedef long long LL;
const int maxn = 10 + 100;
int n;
bool flag;
int num[maxn][maxn];
bool visRow[10][10], visCol[10][10], visBlock[10][10];

inline int calBlockIdx(int x, int y) {
    return x / 3 * 3 + y / 3;
}

void output() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << num[i][j] << " ";
        }
        cout << endl;
    }
}

void fillin(int r, int c, int x) {
    num[r][c] = x;
    visRow[r][x] = true;
    visCol[c][x] = true;
    visBlock[calBlockIdx(r, c)][x] = true;
}

void rm(int r, int c) {
    int x = num[r][c];
    visRow[r][x] = false;
    visCol[c][x] = false;
    visBlock[calBlockIdx(r, c)][x] = false;
    num[r][c] = 0;
}

bool judge(int r, int c, int x) {
    if (visRow[r][x]) {
        return false;
    }
    if (visCol[c][x]) {
        return false;
    }
    int block = calBlockIdx(r, c);
    return !visBlock[block][x];
}

void dfs(int depth) {
    if (depth == n * n) {
        flag = true;
        output();
        return ;
    }
    int x = depth / 9;
    int y = depth % 9;
    if (num[x][y] != 0) {
        dfs(depth + 1);
        return ;
    }
    for (int i = 1; i <= n; ++i) {
        if (judge(x, y, i)) {
            fillin(x, y, i);
            dfs(depth + 1);
            if (flag) {
                return ;
            }
            rm(x, y);
        }
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    n = 9;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int x;
            cin >> x;
            fillin(i, j, x);
        }
    }
    dfs(0);

    return 0;
}