题解 | #数独挑战#

#include <bits/stdc++.h>


using namespace std;

const int maxn = 10;
struct Node {
    int x;
    int y;
    int val;
}node[maxn*maxn];
int n = 0;
bool across[maxn][maxn];
bool vertical[maxn][maxn];
bool a[maxn][maxn];
bool flag = false;
int ans[maxn][maxn];
int xiao[maxn][maxn] {
    {0,0,0,0,0,0,0,0,0,0},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
};

void solve(int num) {
//     cout<<num<<endl;
    if (num==n) {
        flag = true;
        return ;
    }
    for (int i=1;i<=9;i++) {
        if (!across[node[num].x][i]&&!vertical[i][node[num].y]&&!a[xiao[node[num].x][node[num].y]][i]) {
            across[node[num].x][i]=true;
            vertical[i][node[num].y]=true;
            a[xiao[node[num].x][node[num].y]][i]=true;
            node[num].val = i;
            solve(num+1);
            if (flag) {
                break;
            }
            node[num].val = 0;
            across[node[num].x][i]=false;
            vertical[i][node[num].y]=false;
            a[xiao[node[num].x][node[num].y]][i]=false;
        }
    }
}

int main() {
    int k;
    for (int i=1;i<=9;i++) {
        for (int j=1;j<=9;j++) {
            cin>>k;
            ans[i][j] = k;
            if (k==0) {
                //记录缺少的空
                node[n].x = i;
                node[n].y = j;
                node[n].val = 0;
                n++;
            } else {
                across[i][k] = true;
                vertical[k][j] = true;
                a[xiao[i][j]][k] = true;
            }
        }
    }
    //开始形成node的真正结果
    solve(0);
    for (int i=0;i<n;i++) {
        ans[node[i].x][node[i].y] = node[i].val;
    }
    for (int i=1;i<=9;i++) {
        for (int j=1;j<=9;j++) {
            if (j==1) cout<<ans[i][j];
            else cout<<" "<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}