题解 | #Sudoku#

#include <bits/stdc++.h>
using namespace std;
int cnt_line[9][10];
int cnt_row[9][10];
int matrix[9][9];
int cnt_3[3][3][10];
int sz;
vector<pair<int,int> > blank;

bool isLegal(int i,int j,int num){//判断填入当前数字num是否合法
    if(!cnt_line[i][num]&&!cnt_row[j][num]&&!cnt_3[i/3][j/3][num])
        return true;
    return false;
}
bool dfs(int i,int j,int k){
    int t=1;
    for(t=1;t<=9;t++){
        if(isLegal(i, j, t)&&k<sz){
            matrix[i][j]=t;
            cnt_line[i][t]=cnt_row[j][t]=cnt_3[i/3][j/3][t]=1;
            if(k==sz-1)    return true;
            if(k<sz-1){
                int x=blank[k+1].first,y=blank[k+1].second;
                if(dfs(x,y,k+1))
                    return true;
                //恢复现场,应该是恢复当前i,j而不是x,y因为x,y在自己失败之后就会恢复
                matrix[i][j]=cnt_line[i][t]=cnt_row[j][t]=cnt_3[i/3][j/3][t]=0;
            }
        }
    }
    return false;

}
int main(){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            int a;
            cin>>a;
            matrix[i][j]=a;
            if(a){
                cnt_line[i][a]=1;
                cnt_row[j][a]=1;
                cnt_3[i/3][j/3][a]=1;
            }
            else
                blank.push_back({i,j});
        }
    }
    if((sz=blank.size())){
        int x=blank[0].first,y=blank[0].second;
        dfs(x,y,0);
    }
    for(int i=0;i<9;i++){
        cout<<matrix[i][0];
        for(int j=1;j<9;j++)
            cout<<" "<<matrix[i][j];
        cout<<"\n";
    }

}