DFS

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

思路： DFS

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

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

3

点：

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

~~怎么这么八皇后啊。~~
前两点好解决，开个数组记一下。
第三点有些麻烦，我看很多大佬打了个表。其实不用那么麻烦，建一个

3 \times 3

的数组存大格子，设小格子下标为

x

，

y

，调用的时候用

(x + 2) \div 3

，

(y + 2) \div 3

作为大格子下标就行了。

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

1

（包括输入），加到

81

就代表填满了。

代码：（仅供参考）

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

CPP

#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;//完结撒花
}

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

文章操作

DFS

思路： DFS

代码：（仅供参考）

相关推荐

评论

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