一、项目介绍

首先附上项目的GitHub地址：https://github.com/Nevermore5421/PersonalProjectSudoku

拿到题目后，发现该项目的需求与数独有关，要求：

1）高效生成多个（1-1e6个）不重复的数独终局，并输出到文件。

2）高效解出多个（1-1e6个）有空缺的数独问题，并将结果输出到文件。

其中数独终局指的是一个9*9的盘面上每一行，每一列，每一宫（即3*3的小方形）中没有重复的数字。而解一个数独问题就是要从已经给好的数字中推测出一种可行的数独终局，得到一个可行解即可。

下面将展示我完成这个项目各项内容的思路描述以及制作过程。

1.PSP表格预估时间

PSP表格实际时间将在博文结尾处写出

2.解题思路描述

1）生成数独终局思路

拿到这道题后，我最先想到的思路就是暴搜，但是显而易见这样的效率极低，尤其是在应对1e6的数独终局的要求时。接着我便想到了对暴搜进行一定程度的优化，想到了如下两个思路：

• 用回溯法配合剪枝减少搜索层数和次数
• 用多线程进行优化，加快搜索速度

由于多线程此前我并未熟练使用过，故先用回溯法进行了小规模的数据试验，效率确实有所增加，但由于算法时间复杂度的限制，生成1e6的数独终局至少也要在1min以上的时间，这显然还远未达到期望值，故我对数独的特点进行了一定的观察，并从 络上查阅了一些资料后才有了我最终实现这个需求的思路：

一个完整的数独可以通过一个1-9的无重复的排列通过平移一定列数来生成。

意思就是例如698754321这个排列数，把他作为数独的第一行，我可以把下面的2-9行分别用第一行向右平移3,6,1,4,7,2,5,8列来得到一个完整的数独如下：

6 9 8 7 5 4 3 2 13 2 1 6 9 8 7 5 47 5 4 3 2 1 6 9 82 1 6 9 8 7 5 4 35 4 3 2 1 6 9 8 79 8 7 5 4 3 2 1 61 6 9 8 7 5 4 3 24 3 2 1 6 9 8 7 5

8 7 5 4 3 2 1 6 9

这种生成方法的原理如下：

• 一个无重复的1-9的排列可以保证每行中没有重复的数字。
• 将第一行（即原排列）进行平移，只要不平移与之前某行相同的列数（第一行可认为平移了0列），则每列中一定不会有重复的数字。
• 在前两条的基础上，每三行（即123,456,789三组）平移时都采用间隔为3的倍数的平移方法，则可保证每三行形成的宫内没有重复的数字。

能满足以上三个条件的数独终局，自然也是一个合法的数独终局。但仅利用排列数进行生成，由于第一位要求固定为学 后两位的加和模9加1，故最多只能生成8！=40320种不重复的终局，显然达不到要求的1e6个不重复的终局的要求。但此时我又想到如果把平移列数的要求也作为一种排列来看待，则有：

• 前三行由于第一行第一个数锁死不能变动，故可用“036”，“063”两种平移方式。
• 456三行由于都可以自由变动，故可用“147”，“174”，“417”，“471”，“714”，“741”共六种平移方式。
• 789三行同理也有六种平移方式
• 前三条中列举的平移方式还可以进行组合，所以共可组合出6*6*2=72种不同的方式

故对每个排列，都至少可以生成72个不同的终局，所以使用这种变换方式，即可生成72*40320种不重复的终局，远大于1e6的要求了。

使用这种生成终局的好处在于：不用进行反复的搜索，只要确立了一个排列数，就能直接进行数独生成，可以大大增加生成效率。

这种方法经过博文后续讲到的优化思路优化后，本机上可在1.129秒的时间内生成1e6个数独终局，效率可以说是比较高了

2）解数独问题思路

解数独相较于生成数独终局我并没有想到能大幅度降低时间复杂度的算法，最终使用的是开始提到的回溯法并进行了大量的优化和剪枝，优化部分将在后面提到，经过优化后，本机上可在12秒左右的时间内解1e6的数独问题，效率还是可以接受的，大体思路为：

• 用一个数组记录当前数独盘面内已经填入的数字所在行，列，宫。
• 顺序搜索整个盘面，找到未填入数的格点，并尝试性地放入一个数，并继续向后填数，如果能填完整个棋盘，说明这样的填数方法是一个可行解。如果搜到某一个点时发现1-9都无法填入格中，则说明前面某一个格中填写的数字有误，向前回溯，直到找到可行解为止（因为一个数独至少有一个可行解，所以不用担心找不到解的问题）。

3.设计实现过程

由于没有系统学习过C++和面向对象的知识，所以我选择使用C语言，使用面向过程的思想来完成这个项目。

1）函数设计

为了方便代码管理，我总体上分别对生成数独终局和解数独问题设计了输入，输出，和解决问题的三个函数，里面又包含具体处理数据的函数。下面给出详细介绍：

• 对于生成数独终局，不需要进行输入，所以在主函数中我只有BuildAns()函数进行数独构造和OutputBuildSudoku()函数进行数独终局的输出。
• 对于解数独问题，需要进行输入，故主函数中我创建了InputSudokuQuestion(int row,char *save)这个函数来从文件中读取数独问题，然后SolveSudoku(int r, int c)这个函数对数独问题进行求解，最后用OutputSolveSudoku()这个函数进行输出。在SolveSudoku(int r, int c)这个函数中，由于我反复用到了标记数组，所以我也写了几个函数来表示标记数组的行为，有SetVis(int r, int c,int num)，ResetVis(int r, int c,int num)，CheckVis(int r, int c,int num)这三个函数。函数的复用性较强，函数间没有很复杂的调用关系，整体代码可读性较强。

2）代码结构

为了提高代码可读性和正确性，我在开头对所有函数和全局变量进行了声明，并且用#region和#endregion进行了区域划分并命名，这样在寻找某部分代码的声明和定义时，会比较方便快速，提高整体代码的可读性。同时在代码的复用上，我对使用较多次数的代码都做成了函数，保证较好的复用性。

4.程序性能改进优化

1）生成终局输出优化

以我上文中介绍的思路写出的第一版代码时，生成1e6的终局大概需要14秒左右的时间，可以说是不太能够接受的，我查看了VS2017中自带的性能分析工具，发现有90%以上的时间是输出花费的，然后经过上 查询资料后发现，对文件的输出需要打开文件，反复的打开文件关闭文件，并向文件中输出这个过程会极大的增加时间消耗，故后来我采用了一种可以一次性输出所有结果的方法：

将所有生成的数独终局以一个字符串的形式存在一个极大的字符数组中，最后一次性输出到文件中。

使用这种方法，可将大部分处理文件的时间节省下来，仅多耗费一些向数组中存入数据的时间即可（这个时间相比于向文件中读入的时间几乎可以忽略不计）在存的过程中，需要注意：

• 空格的位置也要考虑到。
• 每行后的空行和每个数独终局后的一行空行都可以预置在数组中，这样输出时不用特别考虑空行的问题，更能提升效率。

经过这种优化后，我在本机上生成1e6的数独终局的时间由原先的14秒缩减到了现在的1.1秒-1.3秒的范围内，可以说是大大增加了效率。下面附上性能分析工具生成的性能分析图：

5.代码说明

1）变换法构造数独终局代码

这部分是通过排列构造数独终局的核心算法，代码每步作用已用注释具体描述。

2）构造1-9的排列代码

这部分代码是生成全排列以及生成变换的组合的核心代码，也是构造终局的核心。

3）解数独核心代码

这是解数独的搜索回溯部分的核心代码，通过vis数组可以大大减少判重所需的时间。

7.PSP表格实际时间

具体实现项目时，本计划写一个GUI，后来发现时间条件上不允许，故学习以及写GUI的时间有所缩减，在总体代码实现的时间上增加。

总结：

通过这个数独项目的学习和制作，我学习了很多一个完整软件制作过程中的一些基本技巧，学会了使用性能分析软件，学会了开发前进行计划，安排和设计，对软件开发的理解又上升了一个层次。