数独游戏

解析

用结构体记录每个空格的位置，把已填过的空格数量作为搜索的深度，处理宫的时候可以打表进行坐标到宫的编号的转换，dfs即可

代码

#include<bits/stdc++.h>
using namespace std;
struct ty{
    int x,y;
}space[90];
int mp[12][12];
int h[12][12],l[12][12],gong[12][12];
int cnt=0;
const int g[10][10]={{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 print(){
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            cout<<mp[i][j];
            if(j==9)cout<<'\n';
            else cout<<" ";
        }
    }
}
void dfs(int dep){
    if(dep>cnt) {
        print();
        return ;
    }
    else{
        int xx=space[dep].x,yy=space[dep].y;
        for(int i=1;i<10;i++){//一开始习惯性从0开始，没发现
            if(h[xx][i]==0&&l[yy][i]==0&&gong[g[xx][yy]][i]==0){
                h[xx][i]=1;
                l[yy][i]=1;
                gong[g[xx][yy]][i]=1;
                mp[xx][yy]=i;
                dfs(dep+1);
                h[xx][i]=0;
                l[yy][i]=0;
                gong[g[xx][yy]][i]=0;
                mp[xx][yy]=0;
            }
        }
    }
}
int main(){
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            cin>>mp[i][j];
            if(mp[i][j]==0){
                space[++cnt].x=i;
                space[cnt].y=j;
            }else{
                h[i][mp[i][j]]=1;
                l[j][mp[i][j]]=1;
                gong[g[i][j]][mp[i][j]]=1;
            }
        }
    }
    dfs(1);
    return 0;
}