需求分析
- 命令行
合法参数有六种： -c 、 -s 、 -n -m 、 -n -r 、 -n -u 、 -n -r -u(支持多参数的顺序任意)
-c 1~1000000 -n 1~10000 -m 1~3 -r 20~55 - GUI程序
难度选择、计时、提示、最佳记录
开发过程
- 看教科书和其它资料中关于Information Hiding, Interface Design, Loose Coupling的章节，说明你们在结对编程中是如何利用这些方法对接口进行设计的。（5’）
在OO课程中，我们学习面向对象程序的需求分析和设计原则时，提到过5个经典的设计原则检查(SOLID)。其中的SRP(Single Responsibility Principle)要求每个模块都只有一个明确的职责。因为模块职责多，就意味着逻辑难以封闭，容易受到外部因素变化而变化，导致该模块不稳定。在本项目中，我们把涉及到计算数据的生成和求解数独功能提出来，形成一个独立的模块。其他的控制输入、数据可视化等功能也形成各自的模块，再通过接口把它们联系起来，这样各模块间就做到了松耦合（即修改一个模块时不需要更改其他的模块），同时也实现了不同模块间的信息隐藏（即每个模块只访问自己感兴趣的数据来实现自己负责的功能）。
例如本项目中的Core模块，功能就是生成和求解数独，因此提供generate和solve两个接口函数供外部调用。当需求发生变化时（生成符合要求的数独），我们遵从OCP原则，不修改已有实现(close)，而是通过扩展来增加新功能(open)。所以我们重载了generate函数，通过接收不同参数，来满足不同的需求。 - 计算模块接口的设计与实现过程。设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？说明你的算法的关键（不必列出源代码），以及独到之处。（7’）
Core模块主要可分为三部分，一是随机生成终盘，二是按要求挖空，三是求解数独题目。因此主要分为三个类，其中FinalMaker类的make函数采用每行随机填数的方法生成一个终盘（为了可玩性牺牲了绝对不重复性，虽然理论上可能生成等效数独但概率极低），PuzzleSovlver类的求解函数采用效率极高的DLX算法，而Core类通过调用这两类的函数来实现随机生成终盘、求解数独、保证唯一解挖空功能。最后一个功能应该是最难实现的，这里我们采取的办法是：先生成终盘，再挖空，然后求解看有没有多解，有则重新挖。流程图如下： - 画出UML图显示计算模块部分各个实体之间的关系(画一个图即可)。（2’）
- 计算模块接口部分的性能改进。记录在改进计算模块性能上所花费的时间，描述你改进的思路，并展示一张性能分析图（由VS 2015/2017的性能分析工具自动生成），并展示你程序中消耗最大的函数。（3’）
主要分析最复杂的生成唯一解数独的功能。生成数量少时还好，个数大于1000就明显慢到无法接受的地步。分析发现findSolutions()函数耗时极长，于是针对它做了修改，在发现有第二个解时就抛出一个int，在最外面通过try catch来接收这个抛出，从而跳出了多重的递归，大大减少了判断是否有唯一解的时间。下面是在-n 10000 -r 40~50 -u参数下的性能分析图： - 消耗最大的函数时Input类的handle函数，负责调用其他函数实现功能。而各功能函数中，耗时较多的是生成随机数独的make()和检查唯一解的checkUnique()。但需要说明的是，当挖空数在50以上时，程序耗时会大大加长，原因在于挖较多空时需要大量地调用checkUnique函数，导致消耗激增，暂时没有更好的解决方法。
- 看Design by Contract, Code Contract的内容：
http://en.wikipedia.org/wiki/Design_by_contract
http://msdn.microsoft.com/en-us/devlabs/dd491992.aspx
描述这些做法的优缺点, 说明你是如何把它们融入结对作业中的。（5’） - 计算模块部分单元测试展示。展示出项目部分单元测试代码，并说明测试的函数，构造测试数据的思路。并将单元测试得到的测试覆盖率截图，发表在博客中。要求总体覆盖率到90%以上，否则单元测试部分视作无效。（6’）
Core单元的功能为生成和求解数独，对于生成的测试主要分三个方面：一是生成的题目是否合法（比如某行是否会出现两个”1”之类的），二是挖空数是否在规定范围之内。可通过下面的函数检测：
bool checkValid(int final[9][9], int row, int col, int& blanks)
{
int value = final[row][col];
if (value == 0)
{
blanks++;
return true;
}
for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) // 检测该块是否已有该数字
for (int j = col / 3 * 3; j < col / 3 * 3 + 3; j++)
if (final[i][j] == value)
if (!(i == row&&j == col))
return false;
for (int i = 0; i < 9; i++) // 检测该行该列是否已有该数字
if ((i != col&&final[row][i] == value) || (final[i][col] == value&&i != row))
return false;
return true;
}三是判断是否有唯一解，这里直接调用PuzzleSolve::checkUnique()进行检查。
测试代码：
[TestMethod]
void TestGenerate1()
{
srand((unsigned)time(NULL));
Core c;
const int number = 100;
for (int mode = 1; mode <= 3; mode++) // 遍历三个难度
{
int result[number][81];
c.generate(number, mode, result);
int game[9][9];
int blanks;
for (int i = 0; i < number; i++) // 遍历生成的题目
{
memcpy(game, result[i], sizeof(game));
blanks = 0;
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(game, j / 9, j % 9, blanks), L"合法性出错");
switch (mode)
{
case 1:
Assert::IsTrue(blanks >= 20 && blanks <= 30, L"难度1挖空范围出错");
break;
case 2:
Assert::IsTrue(blanks >= 31 && blanks <= 45, L"难度2挖空范围出错");
break;
case 3:
Assert::IsTrue(blanks >= 46 && blanks <= 55, L"难度3挖空范围出错");
break;
default:
break;
}
}
}
};
[TestMethod]
void TestGenerate2()
{
Core c;
const int number = 100, lower = 20, upper = 30;
int result[number][81];
c.generate(number, lower, upper, false, result);
int game[9][9];
int blanks;
for (int i = 0; i < number; i++) // 遍历生成的题目
{
memcpy(game, result[i], sizeof(game));
blanks = 0;
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(game, j / 9, j % 9, blanks), L"合法性出错");
Assert::IsTrue(blanks >= lower && blanks <= upper, L"挖空范围出错");
}
};
[TestMethod]
void TestGenerate3()
{
Core c;
PuzzleSovlver ps;
const int number = 100, lower = 40, upper = 55;
int result[number][81];
c.generate(number, lower, upper, true, result);
int game[9][9];
int blanks;
for (int i = 0; i < number; i++) // 遍历生成的题目
{
memcpy(game, result[i], sizeof(game));
blanks = 0;
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(game, j / 9, j % 9, blanks), L"合法性出错");
Assert::IsTrue(blanks >= lower && blanks <= upper, L"挖空范围出错");
Assert::IsTrue(ps.checkUnique(game), L"唯一性出错");
}
};
[TestMethod]
void TestSolve()
{
Core c;
int puzzle[1][81];
int final[9][9];
int blanks = 0;
c.generate(1, 1, puzzle);
Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失败");
memcpy(final, puzzle, sizeof(final));
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出错");
c.generate(1, 2, puzzle);
Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失败");
memcpy(final, puzzle, sizeof(final));
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出错");
c.generate(1, 3, puzzle);
Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失败");
memcpy(final, puzzle, sizeof(final));
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出错");
c.generate(1, 20, 55, false, puzzle);
Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失败");
memcpy(final, puzzle, sizeof(final));
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出错");
c.generate(1, 50, 55, true, puzzle);
Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失败");
memcpy(final, puzzle, sizeof(final));
for (int j = 0; j < 81; j++)
Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出错");
puzzle[0][0] = puzzle[0][1] = 1;
Assert::IsFalse(c.solve(puzzle[0], puzzle[0]), L"解出非法数独");
};单元测试覆盖率：
- 计算模块部分异常处理说明。在博客中详细介绍每种异常的设计目标。每种异常都要选择一个单元测试样例发布在博客中，并指明错误对应的场景。（5’）
针对generate和solve接口的参数，异常可分为以下四类。
- NumberException：-n/-c参数的number范围出错
[TestMethod]
void TestNumberException()
{
Core c;
int result[1][81];
try
{
c.generate(-1, 1, result); // number传入-1
Assert::Fail(L"number范围出错");
}
catch (NumberException& e)
{
cout << e.what() << endl;
}
try
{
c.generate(INT_MAX, 20, 30, true, result); // number传入最大int值
Assert::Fail(L"number范围出错");
}
catch (NumberException& e)
{
cout << e.what() << endl;
}
};- ModeException ：-m参数的mode范围出错
[TestMethod]
void TestModeException()
{
Core c;
int result[1][81];
try
{
c.generate(1, 0, result); // mode传入0
Assert::Fail(L"mode范围出错");
}
catch (ModeException& e)
{
cout << e.what() << endl;
}
try
{
c.generate(1, 4, result); // mode传入4
Assert::Fail(L"mode范围出错");
}
catch (ModeException& e)
{
cout << e.what() << endl;
}
};- RangeException ：-r参数的range范围出错
[TestMethod]
void TestRangeException()
{
Core c;
int result[1][81];
try
{
c.generate(1, -1, 20, false, result); // lower传入-1
Assert::Fail(L"range范围出错");
}
catch (RangeException& e)
{
cout << e.what() << endl;
}
try
{
c.generate(1, 50, 40, false, result); // lower比upper传入-1
Assert::Fail(L"range范围出错");
}
catch (RangeException& e)
{
cout << e.what() << endl;
}
try
{
c.generate(1, 20, 56, false, result); // upper传入56
Assert::Fail(L"range范围出错");
}
catch (RangeException& e)
{
cout << e.what() << endl;
}
};- ValidException ：传入非法数独报错
[TestMethod]
void TestValidException()
{
Core c;
int result[1][81];
c.generate(1, 3, result);
result[0][0] = result[0][1] = 1;
try
{
c.solve(result[0], result[0]); // 传入非法数独
Assert::Fail(L"解出非法数独");
}
catch (ValidException& e)
{
cout << e.what() << endl;
};
};
- 界面模块的详细设计过程。在博客中详细介绍界面模块是如何设计的，并写一些必要的代码说明解释实现过程。(5’)
- 界面模块与计算模块的对接。详细地描述UI模块的设计与两个模块的对接，并在博客中截图实现的功能。(4’)
- 描述结对的过程，提供非摆拍的两人在讨论的结对照片。（1’）
- 看教科书和其它参考书，网站中关于结对编程的章节，例如：
**说明结对编程的优点和缺点。
结对的每一个人的优点和缺点在哪里 (要列出至少三个优点和一个缺点)。(5’)**