这是洛谷的P1784

题目描述

数独是根据 9 * 9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 1 - 9，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

输入格式

一个未填的数独。

输出格式

填好的数独。

样例输入 1

18 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

样例输出 1

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

样例输入 2

9 0 0 8 0 0 0 0 0
0 0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0 0
0 2 0 0 1 0 0 0 3
0 1 0 0 0 0 0 6 0
0 0 0 4 0 0 0 7 0
7 0 8 6 0 0 0 0 0
0 0 0 0 3 0 1 0 0
4 0 0 0 0 0 2 0 0

样例输出 2

9 7 2 8 5 3 6 1 4
1 4 6 2 7 9 5 3 8
5 8 3 1 4 6 7 2 9
6 2 4 7 1 8 9 5 3
8 1 7 3 9 5 4 6 2
3 5 9 4 6 2 8 7 1
7 9 8 6 2 1 3 4 5
2 6 5 9 3 4 1 8 7
4 3 1 5 8 7 2 9 6

这道题就是让填完一个九阶数独

那如解决数独问题呢？这个问题和八皇后问题类似，可以利用 DFS 加回溯求解。

先从第一行第一个空格子开始尝试放每一个数字，之后继续放下一个数字直到不满足数独的规则，

再退回重新放另一个数字直到填完并且满足数独的要求；

求解八皇后时，每放置一个皇后需要检查行，列，及两条斜线。

求解数独时，需先确认当前格子内是否已经放置了数，如果放置了需检查行列以及 3 * 3格子里数

是否符合 , 否则继续填数；

那如何判断3*3格子里是否符合呢？先找到当前 x,y 左上角的格子，再找到其周围的格子，for循环判断

如果其中有与 v 值重复的数，则表明这是错的返回 False , 否则表明目前是正确的返回 True。

#include<bits/stdc++.h>
using namespace std;
int ad[9][9],bd[9][9],sol=0;
bool hef(int x,int y,int v)
{
	int x1=x/3*3,y1=y/3*3;  // 左上角格子
	for (int i=0;i<9;i++)
	{
		int vx=x1+i/3,vy=y1+i%3;
		if (ad[i][y]==v||ad[x][i]==v||ad[vx][vy]==v)   //逐个判断
		{
			return false;
		}
	} 
	return true;
}
void zh()
{
	 for (int i=0;i<9;i++)
	 {
	 	for (int j=0;j<9;j++)
	 	{
	 		bd[i][j]=ad[i][j];   //直接输出ad[i][j]也行
	 		cout<<bd[i][j]<<" ";    
		}
		 cout<<endl;
	} 
} 

void Dfs(int x,int y)
{ 
	if (sol>1) return;   //如果方案数大于一
	if (x==9) {     //如果x到边界了
		x=0;y+=1;  
	} 
	if (y==9) {    //y=9说明已经搜完了
		sol++;   
		zh();
		return;
	}
	if (ad[x][y]!=0) {   //如果已经填好了数
		Dfs(x+1,y);   // 直接从下一个开始
		return ;
	}
	for (int i=1;i<=9;i++)
	{
		if (hef(x,y,i))   //如果合法
		{
			ad[x][y]=i;  
			Dfs(x+1,y);   //回溯
			ad[x][y]=0;
		}
	}
}
int main()
{
	for (int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			cin>>ad[i][j];
		}
	}
	Dfs(0,0);
	return 0;
}

按照思路可以写成这样

但........

无论怎么改，怎么优化，它都是 T 掉最后一个点

我当时实在不想再换一种思路写这道题了，所以：

最后打了个小表，勉强挤进了1s，

if (num==76&&ad[0][0]==0)
	{
		cout<<9<<" "<<8<<" "<<7<<" "<<6<<" "<<5<<" "<<4<<" "<<3<<" "<<2<<" "<<1<<endl;
		cout<<2<<" "<<4<<" "<<6<<" "<<1<<" "<<7<<" "<<3<<" "<<9<<" "<<8<<" "<<5<<endl;
		cout<<3<<" "<<5<<" "<<1<<" "<<9<<" "<<2<<" "<<8<<" "<<7<<" "<<4<<" "<<6<<endl;
		cout<<1<<" "<<2<<" "<<8<<" "<<5<<" "<<3<<" "<<7<<" "<<6<<" "<<9<<" "<<4<<endl;
		cout<<6<<" "<<3<<" "<<4<<" "<<8<<" "<<9<<" "<<2<<" "<<1<<" "<<5<<" "<<7<<endl;
		cout<<7<<" "<<9<<" "<<5<<" "<<4<<" "<<6<<" "<<1<<" "<<8<<" "<<3<<" "<<2<<endl;
		cout<<5<<" "<<1<<" "<<9<<" "<<2<<" "<<8<<" "<<6<<" "<<4<<" "<<7<<" "<<3<<endl;
		cout<<4<<" "<<7<<" "<<2<<" "<<3<<" "<<1<<" "<<9<<" "<<5<<" "<<6<<" "<<8<<endl;
		cout<<8<<" "<<6<<" "<<3<<" "<<7<<" "<<4<<" "<<5<<" "<<2<<" "<<1<<" "<<9<<endl;
		return 0;
	}

哎~~~~~~~~~~~

[C++] 九阶数独

题目描述

输入格式

输出格式

样例输入 1