P1784 数独 C语言（普遍超时写法）

题目：

https://www.luogu.com.cn/problem/P1784

题目描述

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

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

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

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

输入格式

一个未填的数独。

输出格式

填好的数独。

代码：

#include<iostream>
#include<algorithm>
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))//穿入当前坐标(i，j)，选入判断的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;}