BUAA个人项目

![数独](http://images2017.cnblogs.com/blog/990007/201709/990007-20170903112734765-
212116598.png)

题目修改自https://edu.cnblogs.com/campus/fzu/SoftwareEngineering2015/homework/859

零、任务：

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

一、要求：

1. 阅读《构建之法》第一章至第三章的内容，并在下方作业里体现出阅读后的成果。特别是第2章中的效能分析及个人软件开发流程（PSP）。
2. 使用Visual Studio Community 2017进行开发，采用C++或者C#语言实现，可以使用.Net Framework，运行环境为64-bit Windows 10。
   附：下载链接：Visual Studio 2015/2017，下载也推荐使用国内一些镜像站点（不是盗版）MSDN,I tell you
3. 提交的代码要求经过Code Quality Analysis工具的分析并消除所有的警告。
4. 完成项目的首个版本之后，请使用性能分析工具Studio Profiling Tools来找出代码中的性能瓶颈并进行改进。
5. 使用单元测试对项目进行测试，并使用插件查看测试分支覆盖率等指标；并写出至少10个测试用例确保你的程序能够正确处理各种情况。
6. 使用Github来管理源代码和测试用例，代码有进展即签入Github。签入记录不合理的项目会被助教抽查询问项目细节。
7. 按照要求发布博客，利用在构建之法中学习到的相关内容，结合个人项目的实践经历，撰写解决项目的心路历程与收获。博客与Github项目明显不符的作业将取消作业成绩。

二、作业提交：

• 撰写一个博客，要求参见博客作业要求。
• 在个人博客上发布项目源代码的Github链接，以便助教下载，助教将会在测试环境中检查程序的正确性。
• 正确的程序会再进行性能测试，根据性能的好坏进行评分；不正确的程序没有性能的分数。

三、需求：

实现一个命令行程序（不妨叫sudoku.exe），程序能：
1. 生成不重复的数独终局至文件
2. 读取文件内的数独问题，求解并将结果输出到文件

生成终局

1. 在命令行中使用-c参数加数字N（1<=N<=1000000）控制生成数独终局的数量例如：

   sudoku.exe -c 20
   将生成20个数独终局至文件中

2. 将生成的数独终局用一个文本文件（假设名字叫 sudoku.txt）的形式保存起来，文件内的格式如下，数与数之间由空格分开，终局与终局之间空一行，行末无空格：

2 6 8 4 7 3 9 5 1
3 4 1 9 6 5 2 7 8
7 9 5 8 1 2 3 6 4
5 7 4 6 2 1 8 3 9
1 3 9 5 4 8 6 2 7
8 2 6 3 9 7 4 1 5
9 1 7 2 8 6 5 4 3
6 8 3 1 5 4 7 9 2
4 5 2 7 3 9 1 8 6
4 5 1 7 8 2 3 6 9
7 8 6 4 9 3 5 2 1
3 9 2 1 5 6 4 8 7
5 2 7 6 4 9 8 1 3
9 6 8 5 3 1 2 7 4
1 3 4 2 7 8 6 9 5
8 1 5 3 6 7 9 4 2
6 7 3 9 2 4 1 5 8
2 4 9 8 1 5 7 3 6
9 5 8 3 6 7 1 2 4
2 3 7 4 5 1 9 6 8
1 4 6 9 2 8 3 5 7
6 1 2 8 7 4 5 9 3
5 7 3 6 1 9 4 8 2
4 8 9 2 3 5 6 7 1
7 2 4 5 9 3 8 1 6
8 9 1 7 4 6 2 3 5
3 6 5 1 8 2 7 4 9
……

1. 程序在处理命令行参数时，不仅能处理格式正确的参数，还能够处理各种异常的情况，如：

   sudoku.exe -c abc

2. 在生成数独矩阵时，左上角的第一个数为：（学号后两位相加）% 9 + 1。例如学生A学号后2位是80，则该数字为（8+0）% 9 + 1 = 9，那么生成的数独棋盘应如下（x表示满足数独规则的任意数字）：

9 x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x

求解数独

1. 在命令行中使用-s参数加文件名的形式求解数独，并将结果输出至文件，如：

   sudoku.exe -s absolute_path_of_puzzlefile

   程序将从路径中读取数独题目，并将数独题目的解输出至与sudoku.exe同目录的sudoku.txt中，要求与生成终局相同。

2. < puzzlefile >的格式如下,其中0代表空格，题目与题目之间空一行，行末无空格：

9 0 8 0 6 0 1 2 4
2 3 7 4 5 1 9 6 8
1 4 6 0 2 0 3 5 7
0 1 2 0 7 0 5 9 3
0 7 3 0 1 0 4 8 2
4 8 0 0 0 5 6 0 1
7 0 4 5 9 0 8 1 6
8 9 0 7 4 6 2 0 0
3 0 5 0 8 0 7 0 9
9 0 0 8 0 0 4 0 0
……

1. sudoku.txt的格式如下（与生成终局的要求相同）：

9 5 8 3 6 7 1 2 4
2 3 7 4 5 1 9 6 8
1 4 6 9 2 8 3 5 7
6 1 2 8 7 4 5 9 3
5 7 3 6 1 9 4 8 2
4 8 9 2 3 5 6 7 1
7 2 4 5 9 3 8 1 6
8 9 1 7 4 6 2 3 5
3 6 5 1 8 2 7 4 9

1. < puzzlefile >中数独题目个数N（1<=N<=1000000），保证文件中数独格式正确。

附加题：

编写一个GUI，可以来实现随机生成数独题目，并在界面上显示为网格，空白处可以输入数字，填写过程中，或者填写完成后可以判定解法是否正确。

四、测试须知

所有提交到Github上的项目均需要建立一个名字为BIN的文件夹，里面必须含有可执行文件与相关的依赖库，请注意以下两点：
- 确保可执行文件的名字统一为 sudoku.exe。
- 确保生成的棋盘文件 sudoku.txt 与可执行文件在同一目录下，生成文件时请使用相对路径！

一个示例组织目录如下所示：

/ SudokuProject(工程名字自行指定即可)
/ main.cpp
/ generator.cpp
/ BIN
    / Lib.dll(exe运行需要的动态链接库文件)
    / sudoku.exe
    / sudoku.txt (运行exe后生成)

助教在测试时，将以命令行运行可执行文件的方式进行批量测试，参数及其约定如下

五、博客撰写要求：

发表在你的个人博客上，也可以同时转发到你的团队博客上来增加你们团队博客的人气。博客共15分，具体要求如下：
1）在文章开头给出Github项目地址。（1‘）
2）在开始实现程序之前，在下述PSP表格记录下你估计将在程序的各个模块的开发上耗费的时间。（0.5‘）
3）解题思路描述。即刚开始拿到题目后，如何思考，如何找资料的过程。（3‘）
4）设计实现过程。设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？（4‘）
5）记录在改进程序性能上所花费的时间，描述你改进的思路，并展示一张性能分析图（由VS 2017的性能分析工具自动生成），并展示你程序中消耗最大的函数。（3‘）
6）代码说明。展示出项目关键代码，并解释思路与注释说明。（3‘）
7）在你实现完程序之后，在下述PSP表格记录下你在程序的各个模块上实际花费的时间。（0.5‘）

附：PSP 2.1表格

六、评分规则

本次个人项目分数由三部分组成，分别是
（1）博客 — 15分，分数组成在博文规范中。
（2）程序 — 35分

5分为源代码管理评分，该评分主要通过源代码管理中的commit注释信息，增量修改的内容，是否有运行说明等给分。
20分为正确性评分，正确性测试中输入范围限制在 1-1000，要求程序在 60 s 内给出结果，超时则认定运行结果无效。
10分为性能评分，性能测试中输入范围限制在 10000-1000000，没有时间的最小要求限制。
当程序的正确性评分等于20分时才可以参与性能评分环节，所以请各位同学务必保证自己程序的正确性。
性能评分将采取档级评分制度，助教将根据同学们的程序跑同一数据耗费的时间长度将程序分为若干档，每一档的同学得到的分数为 10/档级数。

（3）附加题 — 5分，附加题不参与总分映射。
（4）注意事项：

按时间完成并提交——正常评分
晚交一周以内——0分
晚交一周以上或不交——倒扣本次作业分数
抄袭——倒扣2倍本次作业分数【严禁代码与博客等一切形式的抄袭！博客园支持了对博客的查重功能，我们也有专用的代码查重系统进行代码查重。请各位同学千万不要触碰底线，勿谓言之不预也！】

（5）补考的同学，在截止时间，必须先提交部分博客和部分代码，允许在最后一门补考结束后的48小时内，补充完整。