c语言解数独程序

《c语言解数独程序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一緒论本课题的内容是解数独，数独作为一种经典的数字类游戏，具有很强的逻辑性和趣味性,效率高的解题方法对于程序算法的逻辑要求较高。而试填入法方法简单，只是操作繁琐，但适合计算机进行。我们小组釆用的就是回溯法，利用栈和找出很明显的可唯一填入数使得运算更快一些，普通计算机解最难的17位数独题目一般不会超过5秒钟。组内分工大致为：程序主体一起完成，另外一人负责文件导入的部分，一人负责美化，两人负责找唯一可填入数的部分。二.数学模型们采用的数独解决的方法是直接填入加上回溯法，而主要使用回溯法。对整个算法來说,首先输入待求解的九宫格矩阵，空白位置用0表示。然后定义一个A

2、lterArr二维数组，原数独的每一个小九宫格对应新数组的每一行，将已有的数字的项替换成0。接着进行直接填入部分，对原数独逐九宫格进行查找数据。这部分首先检索新数组，当为非零项时，开始对数独中对应九宫格的空缺部位进行检验，当发现某个空位行与列不冲突吋，计算该位置能填入数的个数，若唯一则直接填入，不回溯，并回到开头位置重新检索以防遗漏；若否，则判断下一位置。当直接填入完成后若仍有未填的就进入回溯部分。该部分准备工作一样，当进行到某个空位可以填入时，将此位置记录储存，用以回溯。当之后赋值错误时，可以返回原始位置,将数字清零，并对下一位置进行赋值。如此循环直至结束

3、。三.程序设计确定了算法后，我们就开始程序的设计。为了整个功能的实现，我们定义了许多函数來解决不同的部分。ChangeAlter用来将新数组中已有位置的数变为零；Input函数导入题目；Count函数用来计算每一个能填数字的个数，若唯一返冋0；反Z返冋1;CheckData函数雨来检查填入数字与每行每列数字是否重复，不重复返回0；ScanData函数用来检索新数组中需要填入的数及其位置；ScanPosition函数用來确定数据能够填入的位置；CheckEnd函数检查数独是否完成，完成就返冋0o对冋溯算法，还要加入Push和Pop函数來进行数字位置的储存与释放

4、。整个程序就由这几个部分组合而成，通过if函数来对是否进行下一步做出判断。同时，冋溯用来储存位置的栈我们选用了结构体数组来实现；函数间参数的传值也通过指针来实现。整个代码大致完成目标后，我们又加入了报错部分，分别使每个if判断后出现相应错误的提示，同时也对栈溢出的情况作了标示。最后我们为整个代码添加注释，使其易懂，并进行不断的调试，完善程序。四•撰写实现与调试相比于上次的加密算法而言，这次我们的算法可以说是更上了一个层次，所以也变得更加复杂了。所以我们选择采取分块的方式将其写为一个个函数，然后再在main函数中调用来完成这个髙端的任务。对于实现的方法，我们选

5、择了回溯法这一粗暴有效的方式，这是根据计算机计算能力强这一特点，通过填入并在出错吋返回的方法进行循环，以达到解决题目的目的。我们撰写这个函数的一个优点就是网上有大量的资料可以参考，甚至还有许多学语言的同好者在网上可以进行现场的答疑，所以我们在写这个程序的时候就是是根据网上现有的一些函数，因此某个函数模块在调试过程中不会出现一个太大的问题，但是我们自己改进所加的函数就不同了，在第一次项目报告后，老师根据我们所将的内容提出了我们存在的不足和需要改进的点，而我们根据这个就在原有基础上增加一次填入过程，即当填入的数唯一时,跳过回溯步骤，减少运算时间。添加了这个部分后

6、，我们程序的运算也显得更有效率了。相比较原来的计算时间可以说有了一个质的飞跃。五.程序结果的展示与分析1、如下图所示首先是解一个简单的数独：0*719*0000*30*4*0*0*0*0*0第一次填充就解开了:所用时I'可大概不到一•秒。3■2、换一个更难的数独:第一次填充:第一次坏I后X-7I«I0一^1IMIM(9I1IViXVtViVIWMI5IMMIHIMX一臼

7、1.

8、々*»—■———■—■■——xW(4IMIMX3IMIMw2IMI7X_—_M11MxxM

9、(4

10、M(4

11、M

12、MH

13、M

14、M—最终结果:这次用时较长，需半分钟左右。虽然我们的算法是

15、回溯法，原理简单而代码繁琐，但是由多次实验结果证明对于简单的数独第一次填充就会结束，而换用其它难度较人的数独的话填充次数可能会多儿次，但是时间上不会延长太多，经过多次试验后我们可以大概确认时间的范围最长约为半分钟，绝大多数数独的解决时I'可在十秒以内，这说明了程序的性能良好C但是,这是在数独有解的情况下，如果数独无解，程序会陷入死循环，最后自行结束，这是程序的缺陷之一。以上实验结果的展示可以直观的说明程序的一些具体的优缺点。六.总结与展望第二次项目在短短的6个周内很顺利的完成了，有了第一次的磨合，这一次分工更加明确，效率更高，只用了一半的时间就完成了程序的大

16、部分。为了项目，每个人都学会了数独，一次次在草稿纸上