网站安全维护公司,成都市住建局,东莞建站公司速推全网天下首选,推广方案100个数独 时间限制#xff1a;1000 ms | 内存限制#xff1a;65535 KB难度#xff1a;4描述数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据99盘面上的已知数字#xff0c;推理出所有剩余空格的数字#xff0c;并满足每一行、每一列、每一个3*3宫内的数字均含1-91000 ms | 内存限制65535 KB 难度4 描述 数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字推理出所有剩余空格的数字并满足每一行、每一列、每一个3*3宫内的数字均含1-9不重复。 每一道合格的数独谜题都有且仅有唯一答案推理方法也以此为基础任何无解或多解的题目都是不合格的。 有一天hrdv碰到了一道号称是世界上最难的数独的题目作为一名合格的程序员哪能随随便便向困难低头于是他决定编个程序来解决它。。 输入第一行有一个数n0 n 100表示有n组测试数据每组测试数据是由一个9*9的九宫格构成0表示对应的格子为空输出输出一个9*9的九宫格为这个数独的答案样例输入 1
0 0 5 3 0 0 0 0 0
8 0 0 0 0 0 0 2 0
0 7 0 0 1 0 5 0 0
4 0 0 0 0 5 3 0 0
0 1 0 0 7 0 0 0 6
0 0 3 2 0 0 0 8 0
0 6 0 5 0 0 0 0 9
0 0 4 0 0 0 0 3 0
0 0 0 0 0 9 7 0 0 样例输出 1 4 5 3 2 7 6 9 8
8 3 9 6 5 4 1 2 7
6 7 2 9 1 8 5 4 3
4 9 6 1 8 5 3 7 2
2 1 8 4 7 3 9 5 6
7 5 3 2 9 6 4 8 1
3 6 7 5 4 2 8 1 9
9 8 4 7 6 1 2 3 5
5 2 1 8 3 9 7 6 4 来源原创上传者 TC_胡仁东 #include stdio.h
#include string.h
int map[9][9];
bool row[9][10]; //列
bool col[9][10]; //行
bool block[3][3][10]; //块
bool flag;
void DFS(int x)
{if(flag)return;int r x / 9;//将一维的位置信息变为二维的位置信息 int c x % 9;int i, j;if(81 x)//当位置为第81个说明结果已出 {for(i 0; i 9; i){for(j 0; j 9; j)printf(%d , map[i][j]);printf(\n);}flag 1;return;}if(0 map[r][c])//当前位置不是题目给出的数据 {for(i 1; i 9; i){//从1到9试验数据能否填入。 假如1-9都不满足条件则回到x-1步 if(!(row[r][i] || col[c][i] || block[r / 3][c / 3][i])){//标记数字已存在 map[r][c] i;row[r][i] col[c][i] block[r / 3][c / 3][i] 1;DFS(x 1);//在x位置数字为i的情况下往后遍历得到状态xxxxxxxx并不能得到解//去掉对x位置数字为i的标记 row[r][i] col[c][i] block[r / 3][c / 3][i] 0;map[r][c] 0;}}}elseDFS(x 1);
}
int main()
{int i, j, n;scanf(%d, n);while(n--){flag 0;//初始化 memset(row, 0, sizeof(row)); memset(col, 0, sizeof(col)); memset(block, 0, sizeof(block));//读入数据 for(i 0; i 9; i){for(j 0; j 9; j){scanf(%d, map[i][j]); if(map[i][j]){//标记数据在 行 列 块是否存在 row[i][map[i][j]] 1; col[j][map[i][j]] 1;block[i/3][j/3][map[i][j]] 1;}}}DFS(0);//从0位置开始深搜 }return 0;
}
