软件工程基础-个人项目-数独

任务：实现一个能够生成数独局并且能求解数独问题的控制台程序。

1、GitHub：https://github.com/MiaoZhou48/SoftwareEngineeringProject

2、时间耗费

3、解题思路：

　　此项目可以细分为两个功能：生成数独、解数独。

　　生成数独我考虑采用的是回溯的方法，对残缺数独不断求解，从而得到相应数量的完善的数独。

　　确定好方法之后便是漫长的学习之路，参考了相应的回溯算法的博客以及其他算法的数独生成博客。

　　在学习过程中也见识到了很多新的思路生成数独，比如说对一个已经合理的数独进行变换，然后判断其在变换之后是否依然是符合数独规范。通过这种方式生成数独，首先会保证结果的互异性，其次相比于回溯不需要大量的计算，节省了大量的时间。

　　但是由于已经开始用回溯算法写了，所以之后的改进阶段会再尝试一下敢变思路。

4、设计实现过程

　　程序主体是3个函数

　　judge（）：解数独函数中用此函数判断回溯条件。

　　solve（）：具体的解函数本体。

　　construct（）：构建函数。

　　封装成函数有利于代码的复用，与此同时提升了程序的简洁性和可读性。

　　函数逻辑说明：

　　生成数独函数construct（）：首先进入函数判断目前生成的数独是否数量达标，若符合标准则结束函数体，否则进入下一步。下一步判断一下1-9个数字是否经过遍历数字全排列完，若是则跳到行间的全排列判断，若行全排完就结束函数体，否则改变行的排列顺序再初始化数排列进行终局输出。若判断数字全排未完，就改变数字的顺序再进行终局生成。也就是两个嵌套的判断，数字全排和行数组的全排。

　　解数独函数solve（）：解数独首先加一个判断条件，看是否已经生成了需求规定的9×9数独，若是输出数独并结束；否则进行递归：利用judge函数判断防止条件，能放就放并进入下一层递归，不能就回溯到上一层遍历到下一个数再进行递归，最终递归结束返回最初的判断，进行数独输出。

　　其实思路很简单但是实际运行的话，若给定的数独数量是1000000或更大跑的时间差不多是在20s，所以还是有待提升的。

5、性能改进及思路

　　测试程序的时候，同学建议我优化一下数字的输出，construct函数其实是最耗时的，所以优化也是从这里着手。

　　之前使用的printf输出格式，但其实putchar（）这种以字符形式输出会更节省时间，所以我替换了之前的printf输出方式，结果生成时间减少到了7s左右，相较之前的20多秒提升了很多。

　　性能测试：

　　这是输入为1000000时的性能情况

6、代码说明（思路解释+注释说明）

　　旁边的小铭同学提供给我一种非常好的思路：就是对任意的一个终局数独，任意交换1-3、4-6、7-9行的顺序得到的依然是满足需求的数独，这也就弥补了8！=40320远远小于1000000这样的大数字的尴尬境地。

　　下面是具体的construct（）函数代码

　　下面是具体的solve（）函数代码

　　解数独就是要有一个判断函数judge（）用来在遍历的阶段看是否能够发放置这个数，思路就是回溯法~

7、实际耗时

　　具体的时间消耗见最上方的表格。

相关资源：基于java的GUI图形化界面的汽车油耗软件-Java代码类资源-CSDN文库