自动搬运

查看原文

来自洛谷，原作者为

	stone_juice石汁 敲稀有滴物种石汁qaq

搬运于2025-08-24 21:30:18，当前版本为作者最后更新于2018-12-30 10:54:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我来凑热闹了OvO

其实我刷完这道题的时候，看到有一些DALAO做的方法差不多哎，但是都不是很详细，一部分人可能看不懂哦..。 所以，我写的以下题解会超多，做好心理准备吧。QWQ

数独规则（懂规则的可以跳过）

按照百度上的说法是这样子的：

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3×3）内的数字均含1-9，不重复。

如上图

重点部分我都用黑体标出来了。规则是这样的，虽然数独是需要逻辑推算的，但是对于计算机来说，就直接枚举每个格子的可能性就可以了（真暴力...）。那么我们如何通过程序实现呢？

判断重复

数独要求每一行、每一列、每一个3×3方阵内的数字，不重复。

行和列重复判断是相当简单的。我们可以定义两个bool型二维数组，当此行（或列）填充数字时，我们可以直接把这行的这个数字打上true表示有数字了。

//譬如第一行第三列填入数字2
bool p[][],l[][];//p:行,l:列;
p[1][2]=l[3][2]=true;

如果后面再填充数字，就判断此行（或列）是否填过这个数字即可。

重点：判断方阵中数字重复

如果判断方阵中数字重复？怎样用行列来表示是几方阵成了个问题。但是不用怕，我们有van能的数学。

观察下面这个数独：

可以看到，每过3列，方阵的序号+1，每过3行，方阵的序号+3。

于是我们有了这样的表达式：

方阵序号=（行数-1）/3*3+（列数-1）/3+1
//注意！行数列数要-1，因为3的整数倍数/3会比原方阵大1，不能满足上述需求。

如果填充了数字，就用这个表达式把相应方阵的相应数字打上true标记就可以了。

有了上述方法，就可以写个深搜函数来解决问题了！

至于剩下的，代码里批注讲哦！上代码！

//stone_juice P1784 数独 
#include <bits/stdc++.h>//华丽的开头~ 
using namespace std;
int sd[11][11];//数独方阵定义 
bool p[11][11],l[11][11],fz[11][11];//行（排？），列，方阵。 
void _out()//优美地输出~ 
{
	for(int i=1;i<=9;i++)
	{	
  		for(int j=1;j<=9;j++)
			cout<<sd[i][j]<<" ";
		cout<<endl;
	}
	exit(0);//注意，此处要用exit(0)。用return的话不会退出dfs函数，会增加运算量。 
}
void dfs(int x,int y)//神奇的深搜~
{
	if(sd[x][y]!=0)//如果原来这个位置有数字，跳过。 
		if(x==9&&y==9)_out();//当行列都为9，填充完成，输出~
		else if(y==9)dfs(x+1,1);//当列数为9，搜索下一排。 
		else dfs(x,y+1);//搜下一列啦~ 
	else//原来的地方没有数字，准备填充！ 
		for(int i=1;i<=9;i++)
			if((!p[x][i])&&(!l[y][i])&&(!fz[(x-1)/3*3+(y-1)/3+1][i]))
			//判断是不是重复了。方法题解有讲！ 
			{
				sd[x][y]=i;//填充！ 
				p[x][i]=l[y][i]=fz[(x-1)/3*3+(y-1)/3+1][i]=true;//打上标记。 
				if(x==9&&y==9)_out();//全部填完！输出~ 
				else if(y==9)dfs(x+1,1);//同上！搜下一行。
				else dfs(x,y+1);//搜下一列！ 
				sd[x][y]=0; //恢复标记。 
				p[x][i]=l[y][i]=fz[(x-1)/3*3+(y-1)/3+1][i]=false;//恢复标记。 
			}
}
int main()
{
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
		{
			int t;//定义tmp（防止下面代码太长？） 
			cin>>t;//炫酷地输入 
			if(t!=0)
				p[i][t]=l[j][t]=fz[(i-1)/3*3+(j-1)/3+1][t]=true;
			//填充的不是0的话，表示原来有数字了。打上标记。	
			sd[i][j]=t;//填充进数独。 
		}	
	dfs(1,1);//搜搜搜！ 
	return 0;//完美地结束~ 
}

虽然我的方法不是最优解，但是看我写的这么认真，各位DALAO给个赞呗！祝愿你们早日AC!!

#include <致管理员：我不小心把图弄挂了...请重新审核一下吧谢谢QWQ>