题解：B4279 [蓝桥杯青少年组国赛 2023] 数独填数

· · 题解

DFS

这个题DFS题解已经很多了，所以这篇题解的侧重点会在我认为比较巧妙的细节上。

思路： DFS

遍历每一个格子，若格子为空，遍历每一种符合要求的数，数独填满后结束遍历。
DFS 不用我说了吧，我来讲一些细节：

一、判断一个数是否符合要求：
要求有 3 点：

  1. 每一行包含 1∼9 且不重复；
  2. 每一列包含 1∼9 且不重复；
  3. 每一个 3 \times 3 的大格子包含 1∼9 且不重复。

怎么这么八皇后啊。
前两点好解决，开个数组记一下。
第三点有些麻烦，我看很多大佬打了个表。其实不用那么麻烦，建一个 3 \times 3 的数组存大格子，设小格子下标为 x，y，调用的时候用 (x + 2) \div 3，(y + 2) \div 3 作为大格子下标就行了。

二、判断数独是否填满：
很多人用扫完数独作为 DFS 的结束条件，其实，只要数独填满了就可以结束了。
问题又来了，怎么判断数独是否填满了呢？
我们可以建一个变量，每填上一个格子就让他加 1（包括输入），加到 81 就代表填满了。

代码：（仅供参考）

讲思路我本来不想发代码的 

#include <bits/stdc++.h>
using namespace std;
bool h[10][10];
bool l[10][10];
bool g[4][4][10];//大格子
int sd[10][10];
int cnt;//填了几个格子
bool ans=0;
void dfs(int x,int y){
    if(cnt==81){//填满了就结束
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                cout<<sd[i][j];
            }
            cout<<"\n";
        }
        ans=1;
        return;
    }
    if(sd[x][y]!=0){
        if(y==9) dfs(x+1,1);
        else dfs(x,y+1);
        return;
    } 
    for(int j=1;j<=9;j++){
        if(!h[x][j]&&!l[y][j]&&!g[(x+2)/3][(y+2)/3][j]){
            h[x][j]=1,l[y][j]=1,g[(x+2)/3][(y+2)/3][j]=1,sd[x][y]=j,cnt++;
            dfs(x,y);
            if(ans)return;
            h[x][j]=0,l[y][j]=0,g[(x+2)/3][(y+2)/3][j]=0,sd[x][y]=0,cnt--;//回溯
        }
    }
}
int main() {
    char x;
    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++) {
            cin>>x; 
            if(x>='0'&&x<='9'){
                int xx=x-'0';
                sd[i][j]=xx;
                h[i][xx]=1;
                l[j][xx]=1;
                g[(i+2)/3][(j+2)/3][xx]=1;//上面提到过的公式
                cnt++;//一定一定要有
            }
        }
    }
    dfs(1,1);
  return 0;//完结撒花
}