题解 | #Sudoku#

1. 这种填数字的都是回溯。
2. 可以使用整除的方式然后*法的方式定位到边界。
3. 最终回溯复原，是指我在本次，所有选择和对应业务都处理完之后（有时候是没法返回true的时候），就复原（此时返回false，因为所有选择都做完了）。

#include<bits/stdc++.h>

using namespace std;


bool check(vector<vector<int>> res, int i, int j){
    //同行
    for(int k = 0; k< 9;k++){
        if(res[i][j]==res[i][k]&&j!=k){
            return false;
        }
    }

    //同列
    for(int k = 0; k< 9;k++){
        if(res[i][j]==res[k][j]&&i!=k){
            return false;
        }
    }

    //3x3区域
    int top = i/3*3;
    int left = j/3*3;

    for(int t = top; t<top+3;t++ ){
        for(int l = left; l < left+3;l++){

            if((t!=i||l!=j)&&res[i][j]==res[t][l]){
                return false;
            }

        }
    }

    return true;


}




bool DFS(vector<vector<int>>& res, int i, int j){
    //base case
    if(i==9){//全部遍历完成
        return true;
    }


    //入口
    if(res[i][j]==0){

        for(int k = 1; k<=9; k++){
            res[i][j] = k;
            if(check(res,i,j)&&DFS(res, j==8? i + 1:i,  j==8? 0:j+1)){//从左到右，从上到下进行尝试
                return true;
            }

        }

        res[i][j] = 0;//尝试完成之后
        return false;
    }else{
        return DFS(res, j==8? i + 1:i,  j==8? 0:j+1);//就看下一步
    }

}



int main(){

    vector<vector<int>> res(9, vector<int>(9,0));

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

    DFS(res,0,0);

    for(int i=0; i< 9; i++){
        for(int j=0; j< 9; j++){
            if(j!=8){
                cout<<res[i][j]<<" ";
            }else{
                cout<<res[i][j]<<endl;
            }

        }

    }


    return 0;
}