题解 | #Sudoku#

#include <array>
#include<iostream>
#include <vector>

using namespace std;
vector<vector<int>> matrix(9, vector<int>(9,0));
bool flag = false;

bool check(int n){
    int h = n / 9;
    int l = n % 9;

    // 检查行， 这时需要保持列不变
    for(int x = 0; x < 9; x++){
        if(x!=h && matrix[x][l] == matrix[h][l] ){
            return false;
        }
    }

    // 检查列， 这时需要保持行不变
    for(int x = 0; x < 9; x++){
        if(x!=l && matrix[h][x] == matrix[h][l] ){
            return false;
        }
    }

    // 检查九宫格内的数字
    for(int i = h / 3 * 3; i < h/3*3+3; i++){
        for(int j = l / 3 * 3; j < l/3*3+3; j++){
            if((i != h || j != l) && matrix[i][j] == matrix[h][l]){
                return false;
            }
            
        }
    }

    return true;
}

void dfs(int n){
    if(n == 81){
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 8; ++j){
                cout << matrix[i][j] << " ";
            }
            cout << matrix[i][8] << endl;
        }

        flag = true;
        return;
    }

    int h = n / 9;
    int l = n % 9;
    if(matrix[h][l] == 0){
        for(int i = 1; i <= 9; ++i){
            matrix[h][l] = i;
            if(check(n)){
                dfs(n+1);
                if(flag) return;
            }
        }
        matrix[h][l] = 0;
    }else{
        dfs(n+1);
    }
}

int main(){
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            cin >> matrix[i][j];
        }
    }

    dfs(0);

}