题解 | #Sudoku#

#include <iostream>
#include <vector>
using namespace std;

bool isValid(vector<vector<int>>& mat, int r, int c, char x){
    int N = 9;
    for(int i = 0; i < N; i++){
        if(mat[r][i] == x || mat[i][c] == x) return false;
    }
    int startRow = (r / 3) * 3;
    int startCol = (c / 3) * 3;
    for(int i = startRow; i < startRow + 3; i++){
        for(int j = startCol; j < startCol + 3; j++){
            if(mat[i][j] == x) return false;
        }
    }
    return true;
}

bool backtracking(vector<vector<int>>& mat, int i, int j){
    int N = 9;
    if(j == N){
        // return backtracking(mat, i + 1, 0);
	  i++;j = 0;
    }
    if(i == N){
        return true;
    }
    if(mat[i][j] != 0){
        return backtracking(mat, i, j + 1);
    }
    for(int x = 1; x <= N; x++){
        if(!isValid(mat, i, j, x)) continue;
        mat[i][j] = x;
        if(backtracking(mat, i, j + 1)){
            return true;
        } 
        mat[i][j] = 0;
    }
    return false;
}


int main() {
    const int N = 9;
    vector<vector<int>> mat(N, vector<int>(N));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> mat[i][j];
        }
    }
    backtracking(mat,0,0);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }

}
// 64 位输出请用 printf("%lld")