题解 | #Sudoku#

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

vector<vector<int>> sudoku(9, vector<int>(9, 0));
vector<vector<int>> result(9, vector<int>(9, 0));

bool isvalid(vector<vector<int>> &sudoku, int row, int col, int num){
    for(int i = 0; i < 9; i++){
        if(sudoku[i][col] == num){ // 看列合不合法
            return false;
        }
        if(sudoku[row][i] == num){ // 看行合不合法
            return false;
        }
        if(sudoku[(row/3)*3 + i/3][(col/3)*3 + i%3] == num){ // 看3 * 3中小正方形合不合法
            return false;
        }
    }
    return true;
}

void backtrack(vector<vector<int>> &sudoku, int i, int j){
    int m = 9, n = 9;
    if(j == n){
        // 一行一行遍历，遍历到最后一列就换到下一行重新开始。
        backtrack(sudoku, i + 1, 0);
        return;
    }
    // 如果i走到最后一行，表示找到一个结果，找到一个就保存起来
    //（可能有多个，会覆盖，只留下一个即可）
    if(i == m){
        for(int i=0;i<9;i++){
            for(int j=0; j<9; j++){
                result[i][j] = sudoku[i][j];
            }
        }
        return;
    }
    // sudoku[i][j] == 0表示这个数需要填入1-9, 否则就下一个
    if(sudoku[i][j] != 0){
        backtrack(sudoku, i, j + 1);
        return;
    }
    // 这里sudoku[i][j] == 0， 从1-9中选择数字填入
    for(int num = 1; num <= 9; num++){
        if(!isvalid(sudoku, i, j, num)){ // 不合法就跳过
            continue;
        }
        sudoku[i][j] = num; // 合法就先标记
        backtrack(sudoku, i, j + 1); // 接着回溯下一个
        sudoku[i][j] = 0; // 恢复现场
    }
}

int main(){
    sudoku.clear();
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cin >> sudoku[i][j];
        }
    }
    backtrack(sudoku, 0, 0);
    for(int i=0;i<9;i++){
        for(int j=0; j<8; j++){
            cout << result[i][j] << " ";
        }
        cout << result[i][8] << endl;
    }
    return 0;
}