题解 | Sudoku

暴力枚举

#include <bits/stdc++.h>

using namespace std;

int a[10][10];

bool dfs(int n) {
    if(n >= 81) return true;
    int x = n / 9, y = n % 9;
    if(!a[x][y]) {
        int mask = 0;
        for(int i=0; i<9; i++) {
            if(a[i][y]) mask |= 1 << a[i][y] - 1;
            if(a[x][i]) mask |= 1 << a[x][i] - 1;
        }
        int tx = x / 3, ty = y / 3;
        for(int i=tx*3; i<tx*3+3; i++) {
            for(int j=ty*3; j<ty*3+3; j++) {
                if(a[i][j]) mask |= 1 << a[i][j] - 1;
            }
        }
        for(int i=0; i<9; i++) {
            if(!(mask >> i & 1)) {
                a[x][y] = i + 1;
                if(dfs(n + 1)) return true;
                a[x][y] = 0;
            }
        }
        return false;
    }
    if(dfs(n + 1)) return true;
    return false;
}

int main() {
    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            cin >> a[i][j];
        }
    }
    dfs(0);
    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}