软工结对项目
## 一、 Github项目地址
## 二、 PSP表格
| Psp | personal software progress stages | 预估耗时 | 实际耗时 |
|---|---|---|---|
| planning | 计划 | 15 | 20 |
| estimate | 估计这个任务需要多少时间 | 10 | 10 |
| development | 开发 | 600 | 700 |
| analysis | 需求分析 | 20 | 25 |
| design spec | 生成设计文档 | 15 | 15 |
| design review | 设计复审 | 10 | 15 |
| coding standard | 代码规范 | 10 | 15 |
| design | 具体设计 | 20 | 30 |
| coding | 具体编码 | 300 | 320 |
| code review | 代码复审 | 60 | 60 |
| test | 测试 | 200 | 260 |
| reporting | 报告 | 20 | 30 |
| test report | 测试报告 | 20 | 30 |
| size measuring | 计算工作量 | 5 | 5 |
| postmortem & process improvement plan | 事后总结，提出过程改进计划 | 30 | 40 |
| 合计 | 1335 | 1575 |
## 三、 看教科书和其它资料中关于Information Hiding, Interface Design, Loose Coupling的章节，说明你们在结对编程中是如何利用这些方法对接口进行设计的
- Information Hiding
- 信息隐蔽将可能变化的因素封装起来，遇到变化时对该模块进行操作即可，不会影响到其它模块。对于这一点，我们将一些必要的部件封装成类，将其变量成员设置为私有，访问只通过方法来访问，之后再修改也只要针对需要修改的模块进行修改，不需要改动其它模块。
- Interface Design
- 在考虑接口设计时，要分清楚哪些模块之间是有联系的，设计时应该要遵循下面那个高内聚低耦合的原则。
- Loose Coupling
- 内聚是一个模块内各个元素彼此结合的紧密程度，耦合是一个软件结构内不同模块之间互连程度的度量 。这个原则要求我们设计时明确每一个模块的作用，模块与模块之间尽量无牵扯，就如生成数独与解数独，这两个模块尽可能的没有什么共用的东西，而生成数独与挖空有联系。
## 四、 计算模块接口的设计与实现过程。设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？说明你的算法的关键（不必列出源代码），以及独到之处
**求解数独，对生成的数独挖空得到题目，命令行部分（参数分析等）和异常处理**：
涉及到Core模块中的以下函数：
_declspec(dllexport) bool __stdcall solve(int puzzle[81], int solution[81]);
_declspec(dllexport) bool __stdcall blank(int puzzle[81], int mode);
_declspec(dllexport) bool __stdcall blank(int puzzle[81], int lower, int upper, bool unique);
Node* toMatrix(int puzzle[81]);
void remove(Node* c);
void resume(Node* c);
int dance(Node* head, int solution[81]);
int dance(Node* head, int &tag);
bool DLX(int puzzle[81], int solution[81]);
bool isunique(int puzzle[81]);
void Delete(Node* n);
void init(Node* n);
blank用于对生成好的数独挖空得到题目，挖空时根据传入的参数在范围内随机挖空，会调用isunique判断挖完的题目是否有唯一解，传入参数不合法的话会抛出异常并返回false
由于在实际上玩数独的时候比起解的个数，挖空数对难度的影响要大得多，因此本项目难度的划分不考虑解的个数，具体为:
| 难度 | 挖空数 |
|---|---|
| 1 | 20~35 |
| 2 | 36~45 |
| 3 | 46~55 |
求解使用了DLX算法，使用链表实现：
- DLX用于求解数独，会调用dance(Node* head, int solution[81])和toMatrix，返回值表示是否有解
- isunique用于判断一个数独题目是否有唯一解，会对数独进行回溯求解，直到回溯完成或找到两个解。是对DLX进行少量重写得到的，返回值表示是否有唯一解
- isunique中调用dance(Node* head, int &tag)，用tag标记解的个数，tag=2表示有两个以上的解，=1表示唯一解，=0表示无解
- init用于初始化链表的节点，Delete用于释放链表的空间
- 设计函数时将DLX算法分为2个部分：生成链表和遍历。其中遍历会多次执行删除元素和恢复元素的操作。因此将DLX的整个过程分为4个函数
- toMatrix用于生成链表，返回head节点
- dance(Node* head, int solution[81])用于得出一个解并保存到solution数组里
- resume和remove分别用于恢复和删除链表中元素
生成部分：
涉及到的函数有：
generate(int number, int result[][81])
void produce(int total, int nums[], int block_num, int & count_total, int count_nums, int sudo[9][9], int result[][81]);
bool isinraw(int num, int raw_num, int sudo[9][9]);
bool isincolumn(int num, int c_num, int sudo[9][9]);
int insert(int num, int blocknum, int marked[], int sudo[9][9]);
void out(int sudo[9][9], int result[][81], int count_total);
生成函数采用的是回溯的方法，该方法虽然不能确保生成的所有数独都不是等价的，但是是尽可能少的产生等价的数独。
## 五、 画出UML图显示计算模块部分各个实体之间的关系
## 六、 计算模块接口部分的性能改进。记录在改进计算模块性能上所花费的时间，描述你改进的思路，并展示一张性能分析图（由VS 2015/2017的性能分析工具自动生成），并展示你程序中消耗最大的函数
基本只对求解进行了改进，但是花费了大量时间（7-8h），第一版完成时在x86下进行了简单的测试，当时还没有发现问题，在第一版完成以后我们组进行了第四阶段的交换测试，发现在x64环境下DLX求解变得十分慢而且内存消耗极大，在长时间调试后找到了原因。
一开始通过中断调试找到了死循环，发现多次挖空时没有还原挖过的数独，修正了挖空的逻辑，但是问题没有得到解决，然后通过内存分析发现链表的Node节点占用了大量的内存，可能是释放链表空间出了问题。
经过长时间的分析后发现在求解完成时链表是不完整的，一部分节点被删除，但是变成了孤立节点，没有被释放（仔细想想求解完了的时候链表已经几乎被删空了……）。
主要问题出现在dance函数上：
```
int Core::dance(Node* head, int solution[81])
{
if (head->right == head)
{
return 1; //得到一个解，返回
}
Node *i = head->right->right;
Node *temp = head->right;
while (i != head)
{
if (i->countcount)
temp = i;
i = i->right;
}
if (temp->down == temp)return 0;
remove(temp);
i = temp->down;
while (i != temp)
{
Node *j = i->right;
solution[i->num[0] * 9 + i->num[1]] = i->num[2];
while (j != i)
{
remove(j->col);
j = j->right;
}
if (dance(head, solution))
{
return 1; //依次返回1直到退出递归
}
j = i->left;
while (j != i)
{
resume(j->col);
j = j->left;
}
solution[i->num[0] * 9 + i->num[1]] = 0;
i = i->down;
}
resume(temp); //用于恢复链表，但是退出递归的时候不会执行
return 0;
}
dance函数递归执行，在一开始链表是完整的，在递归过程中会逐渐删除链表中的元素，当执行到:
if (head->right == head)
{
return 1;
}
这段语句的时候，递归的dance函数会逐层返回1并退出。但是这时，链表里面只剩一个head了。以原本的链表索引为基础释放只能释放head，其他元素已经变成了孤立节点。
可以通过在退出递归前还原链表或者建立额外的索引解决， 最后经过测试选择了效率较高的方法，在链表中加入了一个额外的指针，使整个链表形成一个一维链表，以此为索引进行释放就不会漏掉节点，最终解决了问题。
**性能分析**：
两张分别对应生成数独题和求解，生成参数为 -n 100 -u，求解为多次求解一个较难的17个数的数独,由于generate调用了blank，blank调用了isunique，isunique调用了toMatrix和dance，时间主要消耗在转换成矩阵上，求解也花了一定量的时间。求解的时候选用了难度较大的数独，这时dance函数消耗的时间明显上升,在使用-u参数的时候，由于需要多次求解和重新挖空，效率很慢，生成100个就要5s，目前还没有找到什么比较好的解决办法。
<br>
##<font color=gray > 七、 描述这些做法的优缺点, 说明你是如何把它们融入结对作业中的</font>
- 优点
- 有利于设计层面上保证程序的正确性
- 获得更优秀的设计
- 编写契约可以帮助开发者更好地理解代码
- 契约有助于测试（契约可以随时关闭或者启用）
- 简化调试
- 支持复用
- 缺点
- 撰写契约需要时间
- 开发者需要时间学习撰写良好契约的思想和技术
- 需要大量的实践
- 目前的主流语言中，只有Eiffel支持契约，而且仅仅支持顺序式程序（sequential program）的契约
- 事先约定好各接口的参数定义以及能够输入的合法值，约定好各种条件下的返回值。
<br>
##<font color=gray > 八、 计算模块部分单元测试展示。展示出项目部分单元测试代码，并说明测试的函数，构造测试数据的思路。并将单元测试得到的测试覆盖率截图，发表在博客中。要求总体覆盖率到90%以上，否则单元测试部分视作无效</font>
测试生成：
TEST_METHOD(TestGenerate)
{
// TODO: 在此输入测试代码
int sudo[9][9];
Core test;
int result[3][81];
test.generate(3, result);
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 81; j++)
{
sudo[j / 9][j % 9] = result[i][j];
}
for (int j = 0; j < 9; j++)
{
for (int k = 0; k < 9; k++)
{
for (int n = 0; n < 9; n++)
{
if (n != j)
{
Assert::AreEqual(false, sudo[i][j] == sudo[i][n]);
}
if (n != i)
{
Assert::AreEqual(false, sudo[i][j] == sudo[n][j]);
}
}
}
}
}
int blankNum = 0;
int puzzle[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
,2,1,7,5,6,7,5,4,9,1,2,8,3,1,5,4,2,3,7,8,9
,6,3,6,9,8,4,5,7,2,1,2,8,7,1,6,9,5,3,4,5,2
,1,9,7,4,3,6,8,4,3,8,5,2,6,9,1,7,7,9,6,3,1
,8,4,5,2 };
int backup[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
,2,1,7,5,6,7,5,4,9,1,2,8,3,1,5,4,2,3,7,8,9
,6,3,6,9,8,4,5,7,2,1,2,8,7,1,6,9,5,3,4,5,2
,1,9,7,4,3,6,8,4,3,8,5,2,6,9,1,7,7,9,6,3,1
,8,4,5,2 };
test.generate(1, 1, result);
for (int i = 0; i < 81; i++)
{
if (result[0][i] == 0)
{
blankNum++;
result[0][i] = backup[i];
}
}
Assert::AreEqual((20 <= blankNum&&blankNum <= 35), true);
blankNum = 0;
test.generate(1, 2, result);
for (int i = 0; i < 81; i++)
{
if (result[0][i] == 0)
{
blankNum++;
result[0][i] = backup[i];
}
}
Assert::AreEqual((36 <= blankNum&&blankNum <= 45), true);
blankNum = 0;
test.generate(1, 3, result);
for (int i = 0; i < 81; i++)
{
if (result[0][i] == 0)
{
blankNum++;
result[0][i] = backup[i];
}
}
Assert::AreEqual((46 <= blankNum&&blankNum <= 55), true);
blankNum = 0;
test.generate(1, 20, 55, true, result);
for (int i = 0; i < 81; i++)
{
if (result[0][i] == 0)
{
blankNum++;
result[0][i] = backup[i];
}
}
Assert::AreEqual((20 <= blankNum&&blankNum <= 55), true);
blankNum = 0;
test.generate(1, 40, 40, true, result);
for (int i = 0; i < 81; i++)
{
if (result[0][i] == 0)
{
blankNum++;
result[0][i] = backup[i];
}
}
Assert::AreEqual((40 == blankNum), true);
}
分别针对生成的三种接口进行测试，检测生成的数独终局是否合法/题目是否符合要求
测试求解：
TEST_METHOD(TestSolve)
{
// TODO: 在此输入测试代码
int puzzle[81] = {
8,0,0,0,0,0,0,0,0
,0,0,3,6,0,0,0,0,0
,0,7,0,0,9,0,2,0,0
,0,5,0,0,0,7,0,0,0
,0,0,0,0,4,5,7,0,0
,0,0,0,1,0,0,0,3,0
,0,0,1,0,0,0,0,6,8
,0,0,8,5,0,0,0,1,0
,0,9,0,0,0,0,4,0,0,};
int result[81] = { 0 };
int answer[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
,2,1,7,5,6,7,5,4,9,1,2,8,3,1,5,4,2,3,7,8,9
,6,3,6,9,8,4,5,7,2,1,2,8,7,1,6,9,5,3,4,5,2
,1,9,7,4,3,6,8,4,3,8,5,2,6,9,1,7,7,9,6,3,1
,8,4,5,2 };
int wrong[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
,2,1,7,5,6,7,5,4,9,1,8,2,3,1,5,4,2,3,7,8,9
,6,3,6,9,8,4,5,7,2,1,2,8,7,1,6,9,5,3,4,5,2
,1,9,7,4,3,6,8,4,3,8,5,2,6,9,1,7,7,9,6,3,1
,8,4,5,2 };
Core test;
bool isvalid = true;
test.solve(puzzle, result);
for (int i = 0; i < 81; i++)
{
puzzle[i] = answer[i];
Assert::AreEqual(result[i], answer[i]);
}
test.blank(puzzle, 20, 55, true);
test.solve(puzzle, result);
for (int i = 0; i < 81; i++)
{
Assert::AreEqual(result[i], answer[i]);
}
isvalid = test.solve(wrong, result);
Assert::AreEqual(isvalid, false);
isvalid = test.solve(answer, result);
Assert::AreEqual(isvalid, true);
}
依次求解一个较难的数独，随机挖空的唯一解数独，不合法的数独和完整的合法数独，检测求解的结果和返回值正不正确。
同时检测了判断唯一解算法的正确性，若返回的数独不是唯一解的话求解出的result和answer可能不相同，不能通过测试。
单元测试覆盖率：
<br>
##<font color=gray > 九、 计算模块部分异常处理说明。在博客中详细介绍每种异常的设计目标。每种异常都要选择一个单元测试样例发布在博客中，并指明错误对应的场景</font>
项目的异常分为三种：
|异常|描述|
|:--|:--|
|numberException|输入的数独生成数量异常|
|boundException|输入的挖空边界异常|
|modeException|输入的难度异常|
TEST_METHOD(TestException)
{
Core test;
int result[3][81];
try {
test.generate(2000000, result);
}
catch (numberException &e)
{
Assert::AreEqual(0, 0);
}
try {
test.generate(20000, 2, result);
}
catch (numberException &e)
{
Assert::AreEqual(0, 0);
}
try {
test.generate(20000, 20, 40, false, result);
}
catch (numberException &e)
{
Assert::AreEqual(0, 0);
}
try {
test.generate(3, 5, result);
}
catch (modeException &e)
{
Assert::AreEqual(0, 0);
}
try {
test.generate(3, 41, 40, false, result);
}
catch (boundException &e)
{
Assert::AreEqual(0, 0);
}
try {
test.generate(3, 12, 40, false, result);
}
catch (boundException &e)
{
Assert::AreEqual(0, 0);
}
try {
test.generate(3, 32, 70, false, result);
}
catch (boundException &e)
{
Assert::AreEqual(0, 0);
}
}
单元测试分别针对使用-c和-n时的参数，难度不为1-3，边界超出范围和lower>upper等情况进行了测试:
|测试函数|具体描述|
|:--|:--|
|test.generate(2000000, result);|使用参数-c，超出了最大范围1000000|
|test.generate(20000, 2, result)|使用参数-n，超出了最大范围10000|
|test.generate(20000, 20, 40, false, result)|使用参数-n，超出了最大范围10000|
|test.generate(3, 5, result)|使用参数-m，输入的参数不在1~3范围内|
|test.generate(3, 41, 40, false, result)|使用参数-r，lower>upper|
|test.generate(3, 12, 40, false, result)|使用参数-r，lower超出范围|
|test.generate(3, 32, 70, false, result)|使用参数-r，upper超出范围|
<br>
##<font color=gray > 十、界面模块的详细设计过程。在博客中详细介绍界面模块是如何设计的，并写一些必要的代码说明解释实现过程</font>
界面主要分为两部分：菜单栏和主界面。菜单栏实现的功能有难度的选择，help文档，主界面实现的功能有重新开始、清空、提示、提交、计时以及最佳记录。
**数独盘**：通过81个单行文本框实现，继承了QLineEdit类实现MyLineEdit类，重写了contextMenuEvent方法，新增了hint信号以及槽函数为了实现提示功能，新增setRead方法，使得题目中的数字背景变色以及hint失效。
**模式选择**：在菜单中实现，通过点击执行相对应的槽函数，实现难度的改变。
**提示**：通过点击相应空格的右键进行提示，该动作的槽函数在自己写的MyLineEdit类里，该函数是发送信号，在主界面接受到信号后调用相应的函数求解并提示。
**计时计最佳记录**：通过实现定时器和QTimer实现，让定时器每隔一秒触发一次，更新时间并输入到文本框当中。最佳纪录是在提交成功解正确后比对当前时间与最佳纪录，若当前时间短则更新，通过一个字符串保存在类里。
具体布局代码如下：
//布局
QGridLayout layout = new QGridLayout;
layout->addWidget(restartButton, 0, 0, 2, 1, 0); // 重新开始按钮
layout->addWidget(clearButton, 0, 1, 2, 1, 0); // 清空按钮
layout->addWidget(bestRecord, 0, 8, 1, 1, Qt::AlignRight); //最佳纪录时间
layout->addWidget(nowRecord, 1, 8, 1, 1, Qt::AlignRight); //已经用时
layout->addLayout(layoutSudo, 2, 0, 1, 9, Qt::AlignCenter); // 99的方正
layout->addWidget(submitButton, 3, 0, 1, 9, Qt::AlignCenter); // 提交按钮
计时部分代码如下：
设置1秒触发一次，调用updateTime函数，加一秒并更新文本框。
QLineEdit *bestRecord; // 显示最好记录的时间
QLineEdit *nowRecord; // 显示现在的时间
QString record;
connect(timer, SIGNAL(timeout()), this, SLOT(updateTime()));
timer->start(1000);
void QtGuiApplication2::updateTime()
{
*TimeRecord = TimeRecord->addSecs(1);
nowRecord->setText(TimeRecord->toString("hh:mm:ss"));
}
提示部分代码如下：
点击hint后，发出信号，在主界面接收到信号调用hintClicked()函数。
class MyLineEdit :public QLineEdit
{
protected:
QMenu * hintMenu = new QMenu();
QAction * action = hintMenu->addAction("hint");
void contextMenuEvent(QContextMenuEvent *event);
signals:
void hint();
public slots :
void hintCliked();
}
connect(blocks[nowNum], SIGNAL(hint()), this, SLOT(hintCliked())); // 提示绑定事件
<br>
##<font color=gray > 十一、界面模块与计算模块的对接。详细地描述UI模块的设计与两个模块的对接，并在博客中截图实现的功能</font>
- 要使用计算模块的功能首先要配置相应的dll，我参考了这篇[博客](http://www.cnblogs.com/houkai/archive/2013/06/05/3119513.html)。
- 接下来是具体的调用部分
- 首先创建了一个core对象，供调用函数。
- 初始化的时候调用generate(1, mode, sudo)，生成一个简单的数独局。
- 重新开始按钮点击后，需要生成新的数独局，同样调用generate函数。
- 在提交按钮点击后，需要先判断填写是否正确，错误的话应该显示正确答案，此时先调用solve函数判断解的正确性，若错误，再次调用solve函数。
- 模式选择中，每次选择一个模式，都需要生成相应模式的数独，调用generate函数并传入相应的模式难度参数。
- 提示被点击之后，要在该空显示出数字，调用solve并取出对应位置的数填写即可。
- 实现的功能有：模式选择，帮助菜单，重新开始，清空当前所有，计时功能，最佳纪录，提示功能
<br>
##<font color=gray > 十二、 描述结对的过程，提供非摆拍的两人在讨论的结对照片</font>
主要的讨论都在网上进行，在确定结对后线上讨论得出分工，之后制订计划并开始编码
讨论的结果是我负责除GUI和生成完整数独算法以外的任务
在下课的时候会当面讨论一些线上无法解决的问题
<br>
##<font color=gray > 十三、 结对编程的优点和缺点</font>
- 优点
- 在开发层次，结对编程能提供更好的设计质量和代码质量，两人合作能有更强的解决问题的能力
- 对开发人员自身来说，结对工作能带来更多的信心，高质量的产出能带来更高的满足感
- 在心理上, 当有另一个人在你身边和你紧密配合, 做同样一件事情的时候, 你不好意思开小差, 也不好意思糊弄
- 在企业管理层次上，结对能更有效地交流，相互学习和传递经验，能更好地处理人员流动。因为一个人的知识已经被其他人共享
- 降低学习成本。一边编程，一边共享知识和经验，有效地在实践中进行学习
- 可以让编程环境有效地贯彻Design
- 缺点
- 有时候，程序员们会对一个问题各执己见（代码风格可能会是引发技术人员口水战的地方），争吵不休，反而产生重大内耗
- 面对新手，有经验的老手可能会觉得非常的烦躁。不合适的沟通会导到团队的不和谐
- 有经验的人更喜欢单兵作战，找个人来站在他背后看着他可能会让他感到非常的不爽，最终导致编程时受到情绪影响，反而出现反作用
- 两个人在一起工作可能会出现工作精力不能集中的情况，程序员可能会交谈一些与工作无关的事情
- 对于有不同习惯的编程人员，可以在起工作会产生麻烦，甚至矛盾
<br>
##<font color=gray>十四、 结对的每一个人的优点和缺点在哪里 (要列出至少三个优点和一个缺点)</font>
- 个人
- 优点
- 代码模块分的比较清楚
- 比较细致
- 遇到问题愿意去沟通
- 缺点
- 不太主动去汇报进度
- 同伴
- 优点
- 积极沟通
- 有规划，知道应该做什么
- 愿意尝试
- 缺点
- 代码不怎么写注释，理解起来较困难
<br>
##<font color=gray>附加题： 界面模块，测试模块和核心模块的松耦合</font>
合作小组：15061122 15061144
问题主要出现在两方的测试模块和Core对接，由于我们在测试的时候都用了非标准接口的函数，在测试时出现了问题。
我们对测试进行了针对性修改后可以使用他们的Core。
他们在测试时发现generate(100,40,55,true,result)会导致程序异常，这是导致发现第六部分提到的问题的原因（在此感谢他们）
由于我们测试的时候是在x86上，他们是在x64上，因此出现了完全不一样的结果，对问题的处理和优化在第六部分有详细说明。
gui与核心模块对接没什么问题，只是在设计上有所不同，他们把无解的数独认为是异常，而我们能够判断，而我们的gui需要能判断该数独是否有解，也就是说，接上他们的核心模块有可能填错数独而发生异常。