数独程序 运行正常 但结果无限循环 求助!

代码如下:// 111.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "stdio.h"#include "string.h" #include "math.h" #include "conio.h"int dfs(int x,int y);//深度优先 bool judge(int i,int j,int num); int a[15][15];//声明数组int main(int argc, char* argv[]){ int i,j; char b[10]; for(i=1;i<=9;i++) { gets(b); for(j=1;j<=9;j++) a[i][j]=b[j-1]-48;//录入 } dfs(1,1); return 0; } int dfs(int x,int y) { int i; if(x==10)//满足条件输出 { for(i=1;i<=9;i++) { for(int j=1;j<=9;j++) printf("%d",a[i][j]); printf("尀n"); } return 0; } if(a[x][y]==0)//判断是否有数 { for(i=1;i<=9;i++) { if(judge(x,y,i)) { a[x][y]=i; dfs(x+(y+1)/10,(y+1)%10);//往后一个数,到头换行 } } a[x][y]=0;//回溯 } else dfs(x+(y+1)/10,(y+1)%10);//有数则下一个 return 0; } bool judge(int i,int j,int num)//判断是否满足条件 { int k,x,y,l; if(i%3==0) y=i/3;//得出第几个方块(纵) else y=i/3+1; if(j%3==0) x=j/3;//得出横着第几个方块 else x=j/3+1; for(k=1;k<=9;k++)//判断一行是否有重复的 if(a[i][k]==num&&k!=j) return false ; for(k=1;k<=9;k++) //判断一列是否有重复的 if(a[k][j]==num&&k!=i) return false ; for(k=(y-1)*3+1;k<=y*3;k++)//判断该方块中是否有重复的 for(l=(x-1)*3+1;l<=x*3;l++) if(a[k][l]==num&&k!=i&&l!=j) return false; return true; }
2026年09月22日 01:13
有1个网友回答
网友(1):

提问者是想通过编程的方法,由电脑迅速得到数独的答案。虽然很厉害,但本人认为不过瘾,还是通过自己思考,推导出数独的结果比较好。这更能体现做数独的意义。
数独是一种运用纸、笔进行演算的逻辑数学游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3×3)内的数字均含1-9,不重复。数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。数独起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵。19世纪80年代,一位美国的退休建筑师格昂斯根据这种拉丁方阵发明了一种填数趣味游戏,这就是数独的雏形。20世纪70年代,人们在美国纽约的一本益智杂志《Math Puzzles and Logic Problems》上发现了这个游戏,当时被称为填数字,这也是目前公认的数独最早的见报版本。1984年一位日本学者将其介绍到了日本,发表在Nikoli公司的一本游戏杂志上,当时起名为“数字独身限”,后来就改名为“数独”,其中“数”是数字的意思,“独”是唯一的意思。后来一位前任香港高等法院的新西兰籍法官高乐德在1997年3月到日本东京旅游时,无意中发现了。他首先在英国的《泰晤士报》上发表,不久其他报纸也发表,很快便风靡全英国,之后他用了6年时间编写了电脑程序,并将它放在网站上(这个网站也就是著名的数独玩家论坛),后来因一些原因,网站被关闭,幸好数独大师Glenn Fowler恢复了数据,玩家论坛有了新处所。在90年代国内就有部分的益智类书籍开始刊登,南海出版社在2005年出版了《数独1-2》,随后日本著名数独制题人西尾彻也的《数独挑战》也由辽宁教育出版社出版。《北京晚报》、《扬子晚报》、《羊城晚报》、《新民晚报》、《成都商报》等等报纸媒体也先后刊登了数独游戏。
解题手法:
一、直观法就是不做任何记号,直接从数独的盘势观察线索,推论答案的方法。
二、候选数法就是删减等位群格位已出现的数字,将剩余可填数字填入空格做为解题线索的参考,可填数字称为候选数(Candidates,或称备选数)。
三、排除法(摒除法)
摒除法:用数字去找单元内唯一可填空格,称为摒除法,数字可填唯一空格称为排除法 (Hidden Single)。
根据不同的作用范围,摒余解可分为下述三种:
数字可填唯一空格在「宫」单元称为宫排除(Hidden Single in Box),也称宫摒除法。
数字可填唯一空格在「行」单元称为行排除法(Hidden Single in Row),也称行摒除法。
数字可填唯一空格在「列」单元称为列排除法(Hidden Single in Column),也称列摒除法。
四、唯一余数法:用格位去找唯一可填数字,称为余数法,格位唯一可填数字称为唯余解。
余数法是删减等位群格位(Peer)已出现的数字的方法,每一格位的等位群格位有 20 个,如图七所示。

五、进阶解法:是在补基本解法之不足,所以又称辅助解法。
进阶解法包括:区块摒除法(Locked Candidates)、数组(Subset/Tuple)、二链列(X-Wing)、唯一矩形(Unique Rectangle)、全双值格致死解法(Bivalue Universal Grave)、同数链(X-Chain)、异数链(Multidigit Chain)及其他数链的高级技巧等等。已发展出来的方法有近百种之多。
其中前三种加上基础解法为一般数独书中介绍并使用的方法,同时也是大部分人可以理解并掌握的数独解题技法。
通过基础解法出数只需一种解法,摒除法或唯余法,超出此范围而需要施加进阶解法时,解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数,该解题点的解法需要多个步骤协力完成,因此称做组合解法。
解题必须以逻辑为依归,提倡数独的本意。

六、区块摒除法:区块摒除法包括宫区块摒除法(Pointing)与行列区块摒除法。
在基础题里,利用区块摒除可以替代一些基础解法的观察,或辅助基础解法寻找焦点。
在非基础题里,区块可以隐藏任何其他结构,简单的可以把基础解法隐藏起来,难的可以隐藏数对等等其他进阶技巧。
七、数对法:当一个单元(行、列、宫)的某两个数字仅可能在某两格时,我们称这两个格为这两个数的数对(Pairs)。
数对出现在宫称为宫数对;数对出现在行列成为行列数对。
用候选数法的观点去看,数对有两种,一种是在同单元内其中两格有相同的双候选数,一看就明白,因此称为显性数对(Naked Pair),另一种是,同单元内有两个候选数占用了相同的两格,该两格因为还有其它候选数很难辨认,因此称为隐性数对(Hidden Pair)。