纯静态网站模板,网站右下角图片广告代码,建设网站的时候,网站导航条题目#xff1a;
https://www.luogu.com.cn/problem/P1784
题目描述
数独是根据 99 盘面上的已知数字#xff0c;推理出所有剩余空格的数字#xff0c;并满足每一行、每一列、每一个粗线宫内的数字均含 1−9 #xff0c;不重复。每一道合格的数独谜题都有且仅有唯一答案…题目
https://www.luogu.com.cn/problem/P1784
题目描述
数独是根据 9×9 盘面上的已知数字推理出所有剩余空格的数字并满足每一行、每一列、每一个粗线宫内的数字均含 1−9 不重复。每一道合格的数独谜题都有且仅有唯一答案推理方法也以此为基础任何无解或多解的题目都是不合格的。
芬兰一位数学家号称设计出全球最难的“数独游戏”并刊登在报纸上让大家去挑战。
这位数学家说他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。
据介绍目前数独游戏的难度的等级有一到五级一是入门等级五则比较难。不过这位数学家说他所设计的数独游戏难度等级是十一可以说是所以数独游戏中难度最高的等级。他还表示他目前还没遇到解不出来的数独游戏因此他认为“最具挑战性”的数独游戏并没有出现。
输入格式
一个未填的数独。
输出格式
填好的数独。 代码
#includeiostream
#includealgorithm
using namespace std;
bool check(int x,int y,int k,int map[10][10])
{for(int i 0 ; i 9 ;i)//检查行 {if(map[x][i] k)return false; }for(int j 0 ; j 9 ; j)//检查列 {if(map[j][y] k)return false;}//检查自身九宫格 int startx (x/3)*3; int starty (y/3)*3;for(int i startx ; i startx 3; i){for(int j starty ; j starty 3 ; j){if(map[i][j] k)return false;}} return true;
}
bool dfs(int map[][10])
{for(int i 0 ; i 9 ; i){for(int j 0 ; j 9 ; j){if(map[i][j] 0) //遍历map找0为填数字的格子。{for(int k 1 ; k 9 ; k){if(check(i,j,k,map))//穿入当前坐标(ij)选入判断的k数组map{map[i][j] k;//选kif(dfs(map))//回溯return true;//传递true到上一层递归map[i][j] 0;//回溯} }return false;//这里有一个隐形条件当前格子1-9数字都满足不了条件的时候说明这个数独没有解所以可以直接返回false。}}}return true;//代码运行到这里说明数独的每一个格子都填入了相应的数了。不断回溯传递true到树顶
}
int main(void)
{int map[10][10];for(int i 0 ; i 9 ; i){for(int j 0 ; j 9 ; j){cin map[i][j];}}if(dfs(map)){for(int i 0 ; i 9 ; i){for(int j 0 ; j 9 ; j){cout map[i][j] ;}cout endl;} }else{cout -1 endl;}return 0;}
