数独问题初探_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数独问题初探
上传于||文档简介
&&数​独​问​题​初​探
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩1页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢回溯法解数独问题_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
回溯法解数独问题
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩2页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢Interview（30）
数独（すうどく，Sūdoku），是源自18世纪瑞士发明，流传到美国，再由日本发扬光大的一种数学游戏。是一种运用纸、笔进行演算的。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。
上机笔试题目描述如下：
数独是一个我们都非常熟悉的经典游戏，运用计算机我们可以很快地解开数独难题，现在有一些简单的数独题目，请编写一个程序求解。
输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的。
输出九行，每行九个空格隔开的数字，为解出的答案。
解题思路：此题与dfs（深度优先搜索）问题有相似之处，所有的空格单元可以看作图的节点，遍历所有节点，从1~9之间选取数值填充，然后判断是否符合数独规则，若符合向更深一层遍历，否则返回上一层继续判断其他数值，并清除深层更新的数值，这个搜索方法是利用递归方法实现的，也是一种暴利解决方案，不多对于计算机而言这点计算不是难事，仍然保持较高的时间效率。具体的程序代码如下所示：
#include &iostream&
#include &vector&
#include &algorithm&
/* run this program using the console pauser or add your own getch, system(&pause&) or input loop */
vector&pair&int,int& &
//int a[9][9];
int a[9][9] = {
  {7,2,6,9,0,4,0,5,1},
  {0,8,0,6,0,7,4,3,2},
  {3,4,1,0,8,5,0,0,9},
  {0,5,2,4,6,8,0,0,7},
  {0,3,7,0,0,0,6,8,0},
  {0,9,0,0,0,3,0,1,0},
  {0,0,0,0,0,0,0,0,0},
  {9,0,0,0,2,1,5,0,0},
  {8,0,0,3,0,0,0,0,0}
int candidate[9]={1,2,3,4,5,6,7,8,9};
void printsoduku(){
&span style=&white-space:pre&& &/span&for(int i=0;i&9;i++){
&span style=&white-space:pre&&
&/span&for(int j=0;j&9;j++){
&span style=&white-space:pre&&
&/span&cout&&a[i][j]&&& &;
&span style=&white-space:pre&&
&span style=&white-space:pre&&
&/span&cout&&
&span style=&white-space:pre&& &/span&}
&span style=&white-space:pre&& &/span&cout&&
bool judge(int x,int y){
&span style=&white-space:pre&& &/span&//该行没有问题 
&span style=&white-space:pre&& &/span&for(int i=0;i&9;i++){
&span style=&white-space:pre&&
&/span&if(a[x][i]==a[x][y]&&i!=y)
&span style=&white-space:pre&&
&span style=&white-space:pre&& &/span&}
&span style=&white-space:pre&& &/span&//该列没有问题
&span style=&white-space:pre&& &/span&for(int i=0;i&9;i++){
&span style=&white-space:pre&&
&/span&if(a[i][y]==a[x][y]&&i!=x)
&span style=&white-space:pre&&
&span style=&white-space:pre&& &/span&}
&span style=&white-space:pre&& &/span&//该九宫格没有问题
&span style=&white-space:pre&& &/span&for(int i=x/3*3;i&x/3*3+3;i++){
&span style=&white-space:pre&&
&/span&for(int j=y/3*3;j&y/3*3+3;j++){
&span style=&white-space:pre&&
&/span&if(a[i][j]==a[x][y]&&(i!=x||j!=y))
&span style=&white-space:pre&&
&span style=&white-space:pre&&
&span style=&white-space:pre&& &/span&}
&span style=&white-space:pre&& &/span&
void clearblank(int depth){
&span style=&white-space:pre&& &/span&for(int i=depth-1;i&blank.size();i++){
&span style=&white-space:pre&&
&/span&a[blank[i].first][blank[i].second]=0;
&span style=&white-space:pre&& &/span&}
void dfs(pair&int,int& pos,int depth){
&span style=&white-space:pre&& &/span&for(int i=0;i&9;i++){
&span style=&white-space:pre&&
&/span&a[pos.first][pos.second]=candidate[i];//逐个测试所有候选值
&span style=&white-space:pre&&
&/span&bool pass=judge(pos.first,pos.second);
&span style=&white-space:pre&&
&/span&if(pass)
&span style=&white-space:pre&&
&span style=&white-space:pre&&
&/span&if(depth==blank.size()){
&span style=&white-space:pre&&
&/span&printsoduku();
&span style=&white-space:pre&&
&/span&//exit(0);
&span style=&white-space:pre&&
&/span&}&span style=&white-space:pre&&
&span style=&white-space:pre&&
&/span&if(depth&blank.size())
&span style=&white-space:pre&&
&/span&dfs(blank[depth],depth+1);
&span style=&white-space:pre&&
&span style=&white-space:pre&&
&/span&clearblank(depth);//将深度遍历更新的空白值复原为0 
&span style=&white-space:pre&& &/span&}&span style=&white-space:pre&&
int main(int argc, char** argv) {
&span style=&white-space:pre&& &/span&
//&span style=&white-space:pre&& &/span&输入二维数组 
//&span style=&white-space:pre&& &/span&for(int i=0;i&9;i++){
//&span style=&white-space:pre&&
&/span&for(int j=0;j&9;j++){
//&span style=&white-space:pre&&
&/span&cin&&a[i][j];
//&span style=&white-space:pre&&
//&span style=&white-space:pre&& &/span&}
&span style=&white-space:pre&& &/span&printsoduku();
&span style=&white-space:pre&& &/span&//统计数组中为0的元素的横纵坐标，保存到blank容器中 
&span style=&white-space:pre&& &/span&for(int i=0;i&9;i++){
&span style=&white-space:pre&&
&/span&for(int j=0;j&9;j++){
&span style=&white-space:pre&&
&/span&if(a[i][j]==0){
&span style=&white-space:pre&&
&/span&blank.push_back(make_pair(i,j));&span style=&white-space:pre&&
&span style=&white-space:pre&&
&span style=&white-space:pre&&
&span style=&white-space:pre&& &/span&}
&span style=&white-space:pre&& &/span&//深度优先搜索，遍历所有的空白之处，并填写测试 
&span style=&white-space:pre&& &/span&dfs(blank[0],1) ;
&span style=&white-space:pre&& &/span&return 0;
}实验结果如下：
回顾这道题，关键点在于将数独的空白格遍历问题与图数据结构的深度优先搜索遍历问题联系起来，利用递归函数的方法，记录之前访问的节点在出现异常时及时返回同时复原改变的节点值。以上方法为暴利解决方法，优化方法则是缩小每个空白节点的候选集合范围，动态更新每个空白节点的候选值集合，然后逐个元素代入测试数据表的准确与否。判定规则类似于本文中的judge方法，即每行每列每个9宫格都不能出现重复的数字。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3358次
排名：千里之外
原创：52篇
转载：28篇
(2)(13)(24)(35)(6)数独高手帮忙解解_百度知道问大家一个数独问题 题目是中间的第6题 这是我们班推理社的题目_百度知道}