目录
Github项目地址
- 难度级别-m说明：
- 1：生成35个空的单解数独；
- 2：生成40-50个空的单解数独
- 3：生成50-60个空的单解数独 理由：在国际数独比赛中要求数独题目均为单解的标准数独，在个人体验中，也能感觉到多解数独会造成很大的困扰，因此统一生成单解数独。数独的难度很大程度上依赖空的个数有关，因此把空的个数作为数独难度的判别标准。
接口设计
方法：Information Hiding, Interface Design, Loose Coupling
生成数独终局
void generate(int number, int[][] result)
生成设置难度级别的数独游戏
void generate(int number, int mode, int[][] result)
生成设置挖空数量的数独游戏
void generate(int number, int lower, int upper, bool unique, int[][] result)
解数独题
bool solve(int[] puzzle, int[] solution)
数据成员和方法分别有public类型和private类型，仅将外部需要调用的数据和方法公开，规范好传入的参数的格式，返回符合要求的结果。函数的实现过程，内部调用的函数不对用户公开
计算模块接口的设计与实现过程
代码的组织： 类、函数及其关系
代码一共有两个类：数独类和命令行参数处理类
数独类主要有如下函数:
class Core { public void set_play(bool a);//设置为游戏模式 void create_sudoku_puzzle(int n, int mode); void create_sudoku_puzzles(int block_num, int mode, int n); void create_random_sudoku(); void solve_all_soduku(FILE *fp); void generate(int number, int result); void generate(int number, int mode, int result); void generate(int number, int lower, int upper, bool unique, int result); bool solve(int* puzzle, int* solution); private: void init_sudoku();//初始化数独 int init_check_puzzle();//挖空后是否单解 int can_delete(int addr);//能否挖空 }; 命令行处理类有如下函数:
class arg_info { public: int read_arg_info(int argc, char argv); //读取命令函参数 void run_cmd(int argc, char **argv); private: int str2num(char *str); int str2range_num(char *str); void error_out(int error);//错误输出 void set_arg_bit_on(int mode);//模式设置 }; 关键函数流程图
主要说一下生成数独游戏的函数之间的关系
生成数独游戏首先要调用create_sudoku_puzzles这个函数，然后根据生成题目的数量调用n次create_sudoku_puzzle函数。
这个函数首先调用创建数独的函数，如果是命令行中调用，那么就调用create_test_sudoku，这个函数不会生成重复等价数独；如果是GUI调用（给玩家玩的），那么就调用create_random_sudoku，这个函数保证了随机性。
生成完数独就开始挖空，这些是挖空用的函数：
int can_delete(int addr); int can_delete_senior(int addr);
调用can_delete用来判断通过低级方法可以挖掉的格子；调用can_delete_senior用来判断通过高级方法可以挖掉的格子；这三个函数是来回递归判断数独是否是唯一解的函数，由can_delete_senior调用：
int to_next(int i, int j, int n); int init_check_puzzle(); int check_puzzle(int i, int j, int n);
这个函数是把原来尝试挖掉的空加上的函数，也由can_delete_senior调用
void add_addr(int addr, int num);
找到可以挖的空之后调用一次clear_addr把空挖掉，都挖完调用一次print_sudoku输出
算法的关键及独到之处
分阶段产生数独游戏
采用两种方法对生成的数独终局挖空：低级方法——四种排除法直接把一个数推出来；高级方法——猜数并验证。如果某一个数挖完之后能被简单方法再推出来，那么就把这个格子放在缓存区内；找完当前所有的数，那么就随机挖掉一个缓存区里面的空。但是这样不容易挖够55个空，那么只能通过猜数来挖空。如果一个数挖完之后还是单解数独，那么就挖掉。通过暴力回溯法判断数独解是否唯一；从数独格子中的最后一个空，往前寻找。如果挖完这个格子还是单解数独，那么就挖掉，然后继续往前找，直到挖够55个空就停止挖空。这个挖空方法的独到之处就是会先找到所有低级挖空方法可以挖的空，这样就减少了暴力回溯的次数UML:计算模块部分各个实体之间的关系
计算模块接口部分的性能改进
花费的时间：2小时左右
改进的思路
程序中主要费时间的地方是判断挖完空之后的数独还是单解数独。我们解数独有以下几种方法：1.四种排除法直接把一个数推出来（简单方法）；2.猜数（复杂方法）
挖空过程中，如果某一个数挖完之后能被简单方法再推出来，那么就把这个格子放在缓存区内。找完当前所有的数，那么就随机挖掉一个缓存区里面的空。但是这样不容易挖够55个空，那么只能通过猜数来挖空，猜数是这样。如果一个数挖完之后还是单解数独，那么就挖掉。通过暴力回溯法判断数独解是否唯一，就造成了运行的缓慢最开始是把所有挖过之后解唯一的数找到再随机一个，但是后来发现这样做，判断解唯一性的次数就多，要追求效率，就要减少这方面花的时间，也就是减少判断的次数。所以从前往后找，找到第一个可以挖的格子就挖掉，然后再继续找，直到挖的空够55个。但是这样改了之后更慢了，这种回溯法对前面空多后面空少的数独很棘手，会判断的非常慢。所以就改成从后往前找，从后往前挖，速度提高。这就是执行世界最难指令：n 10000 -r 55~55 -u所用的时间，虽然挖空的函数还是用了很多时间，但是整体已经有很大改进了性能分析图
-c 1000000
-n 10000 -r 55~55 -u
消耗最大的函数
生成数独时，消耗最大的函数是create_sudoku；生成数独游戏时，消耗最大的函数是create_sudoku_puzzle
Design by Contract, Code Contract
- 基本思想：函数的调用者保证传入参数的函数符合函数的要求，如果不复合函数的要求，函数将拒绝执行，写函数时应该对传入函数的参数进行检查
- 优点
- 传统的server/client模式下，对被调用者要求严格，导致了调用者的质量低劣，契约式编程中，调用者和被调用者地位平等，保证了双方的代码质量，提高软件工程的效率和质量
- 在多人合作编程中，使用契约式编程，有利于团队编程接口的统一性，更容易划分模块，便于模块之间的对接
- 缺点
- 契约式编程需要一定的机制验证契约成立与否，对程序语言有一定的要求
- 契约式编程没有被标准化，项目之间的定义和修改的不同，可能会给代码带来混乱
- 融入作业
- 按照要求设计和实现generate和solve等接口，传入符合要求的参数执行函数可以获得正确的结果。事先对传入的result，number等参数进行参数检查，如果不符合要求将会进行异常处理，不会进行下一步的操作，保证运行结果的正确性。
计算模块部分单元测试展示
| 单元测试代码 | 测试的函数 | 测试数据构造思路 |
|---|---|---|
TEST_METHOD(SingleSolution) { Core core; core.create_sudoku_puzzle(1, 3); int result = 0; result = core.check_puzzle(0, 0, 0); Assert::AreEqual(result, 1); } | create_sudoku_puzzle(int n) |
|
TEST_METHOD(generate) { Core core; Tool tool; int **result = tool.CreateArray(1000, 81); core.generate(1000, result); core.generate(1000, 1, result); core.generate(1000, 25, 50, true, result); } TEST_METHOD(LegalSudoku) { int result = 0; Core core; core.create_random_sudoku(); core.solve_sudoku(); Assert::AreEqual(result, 0);} | generate() |
|
TEST_METHOD(solve) { int puzzle[81] = { 0, 0, 0, 8, 0, 9, 0, 2, 0, 7, 0, 0, 0, 0, 0, 8, 4, 5, 0, 0, 5, 0, 7, 6, 0, 9, 0, 0, 0, 8, 7, 0, 0, 3, 0, 0, 0, 9, 6, 0, 1, 8, 0, 0, 0, 4, 0, 0, 3, 0, 0, 0, 1, 0, 8, 0, 0, 0, 0, 2, 0, 0, 6, 0, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; int *solution = new int[81]; Core core; bool result = false; result = core.solve(puzzle, solution); Assert::AreEqual(result, true); puzzle[0] = 8; result = core.solve(puzzle, solution); Assert::AreEqual(result, false); } | solve() |
|
通过的单元测试
单元测试覆盖率
有些用来更方便看到结果的输出到控制台的函数没有被调用，所以不能达到100%
计算模块部分异常处理说明
| 类别 | 设计目标 | 单元测试样例 | 应用场景 |
|---|---|---|---|
| 命令行参数（该部分使用命令行测试） | 处理非法的参数 | sudoku.exe -a | 输入未定义的参数 |
| 处理超出范围或格式不正确的数字 | sudoku.exe -c 100c sudoku.exe -c 100009999 | n，c，r，m后面的参数不正确 | |
| 处理个数错误的参数 | sudoku.exe -c -c 100 sudoku.exe -n -m 1 | 参数重复出现，参数后面没有数字 | |
| 处理错误的参数组合 | sudoku.exe -c 100 -u sudoku.exe -n 100 -m 3 -u | 参数组合错误,即不属于定义的6种组合 | |
| 读入的数独题 | 处理不存在的文件路径 | sudoku.exe -s "non.txt" | 文件不存在 |
| 处理格式不正确的文件 | sudoku.exe -s "non.exe" | 处理文件格式不正确的情况 | |
| 处理非法的数独题 | int puzzle[81] = { 0, 0, 0, 8, c, 9, 0, 2, 0, 7, 0, 0, 0, 0, 0, 8, 4, 5, 0, 0, 5, 0, 7, 6, 0, 9, 0, 0, 0, 8, 7, 0, 0, 3, 0, 0, 0, 9, 6, 0, 1, 8, 0, 0, 0, 4, 0, 0, 3, 0, 0, 0, 1, 0, 8, 0, 0, 0, 0, 2, 0, 0, 6, 0, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; int *solution = new int[81]; solve(puzzle, solution) | 处理数独题内容不正确的情况 | |
| 处理无解的数独题 | int puzzle[81] = { 0, 0, 0, 8, 8, 9, 0, 2, 0, 7, 0, 0, 0, 0, 0, 8, 4, 5, 0, 0, 5, 0, 7, 6, 0, 9, 0, 0, 0, 8, 7, 0, 0, 3, 0, 0, 0, 9, 6, 0, 1, 8, 0, 0, 0, 4, 0, 0, 3, 0, 0, 0, 1, 0, 8, 0, 0, 0, 0, 2, 0, 0, 6, 0, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };int *solution = new int[81];solve(puzzle, solution) | 处理输入的数独题无解的情况 |
界面模块的详细设计过程
界面模块的设计
按照需求将页面划分为四个部分：起始状态的难度选择模块，数独题模块，功能按钮模块，时间、记录展示模块，界面中的各种控件使用.ui文件生成，控件的切换由transGUI控制，信号由coreConnect控制。
功能比较简单，主要有提示、暂停，可以在开始时进行难度选择，也可以在游戏过程中点击返回按钮重新选择难度，或者询问后退出。游戏界面显示当前用时和本难度最高纪录。点击提交反馈是否正确，并询问是有继续游戏。代码说明&实现过程
编辑UI文件，自动生成空间的代码
class Ui_sudokuGUIClass { public: QWidget centralWidget; QWidget verticalLayoutWidget_2; QVBoxLayout panelLayout; //...数据成员 void setupUi(QMainWindow sudokuGUIClass); // setupUi void retranslateUi(QMainWindow *sudokuGUIClass); // retranslateUi }; 在transGUI中对各控件的状态进行设置，实现页面的转换，与计算模块的对接也设置在这一部分
class transGUI : public QObject{ Q_OBJECT public: QTimer *timer; QLineEdit *sudokuLineEdit[9][9]; transGUI(Ui_sudokuGUIClass UI); void writeRecord(); signals: public slots: void play(); void updateTime(); void stop(); void goOn(); void option(); void quit(); void quitCancel(); void inform(); void submit(); private: Ui_sudokuGUIClass ui; Core core; //计算模块 QTime recTime; QLabel *sudokuLabel[9][9]; int **answer, **puzzle; int mode = 0; //难度级别 FILE *fp; //记录文件 QTime recTimes[3]; //最高记录 void readRecord(); }; 在coreConnect中实现信号函数和槽函数的链接。
class coreConnect :public QObject{ Q_OBJECT public: coreConnect(Ui_sudokuGUIClass UI, transGUI *Trans); private: Ui_sudokuGUIClass ui; transGUI *trans; QTimer *timer; void startConnect(); void timeConnect(); void resetTimeConnect(); void backConnect(); void quitConnect(); void quitCancelConnect(); void informConnect(); void submitConnect(); void setTimer(); void againConnect(); signals: private slots: void reSetTimer(); }; 界面模块与计算模块的对接
设计
需要用到计算模块的部分有获取数独题、提示、结果验证的部分。为了更好的用户体验，产生的数独都是标准数独，因此在生成数独时已经有了唯一解，在获取数独题将数独题存入puzzle数组的同时也将数独的答案存储进answer数组，方便提示和提交时使用。
对接
游戏中难度的选择对应-m参数，因此点击游戏开始时，选择的难度级别作为参数m，调用generate(int number, int mode, int** result)函数，因为一次只产生一个数独游戏，所以number设为1，在计算模块中设置play参数，分别将数独终局和数独游戏存入result。
实现的功能
提示：用户点击空格后点击提示按钮，在右侧提示信息处会出现此处应填的数字
暂停：点击暂停按钮，停止计时
返回：退回难度选择页面，重新选择难度级别
退出：点击退出按钮，弹出对话框询问是否确认退出
提交：进行结果验证，告知用户答案是否正确，询问继续游戏还是退出
结对的过程
在周二课上决定结对。
最开始在放假前完成了代码复审的部分，发现两个人思路思维方式非常不一样，对方对性能有很高的追求，思维方式比较独特，有很多神奇的脑洞；我思路比较窄，也比较循规蹈矩。两个人最大的共同点是个人项目都没有写注释，也都没有写GUI。。。
国庆节期间两人大部分时间都不在学校，基本没有任何结对开展工作，双方独立进行，对方进行了算法设计，我学习了GUI和生成dll的方法。非常不好的一点是没有一起对项目进行规划和设计，基本顺其自然。
假期快结束时危机感上升，开始进入一有时间就一起写代码的状态，以对方的代码为基础，按照对方设计的算法两人共同完成了核心部分。接下来对方主要进行性能优化、异常处理，我完成了参数处理，对代码进行了测试和单元测试，完成了GUI。
结对照片
结对编程
| 项目 | 优点 | 缺点 |
|---|---|---|
| 结对编程 |
|
|
| 对方 |
|
|
| 自己 |
|
|
预计花费时间&实际花费的时间
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 60 | 30 |
| Estimate | 估计这个任务需要多少时间 | 60 | 30 |
| Development | 开发 | 1380 | 1590 |
| Analysis | 需求分析 (包括学习新技术) | 300 | 120 |
| Design Spec | 生成设计文档 | 180 | 60 |
| Design Review | 设计复审(和同事审核设计文档) | 60 | 60 |
| Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 60 | 30 |
| Design | 具体设计 | 120 | 240 |
| Coding | 具体编码 | 1800 | 2400 |
| Code Reviewg | 代码复审 | 120 | 120 |
| Test | 测试（自我测试，修改代码，提交修改） | 240 | 240 |
| Reporting | 报告 | 240 | 180 |
| Test Report | 测试报告 | 180 | 120 |
| Size Measurement | 计算工作量 | 60 | 60 |
| Postmortem & Process Improvement Plan | 事后总结, 并提出过程改进计划 | 60 | 60 |
| Sum | 合计 | 3240 | 3480 |
附加题：界面模块，测试模块和核心模块的松耦合
合作小组
刘畅 15061183
王辰昱 15231177出现的问题
如果不改动GUI代码：合作小组使用我们的Core.dll每次生成的puzzle都是相同的；我们使用合作小组的Core.dll无法获得puzzle。
用我们的测试模块测试合作小组的solve(int[] puzzle, int[] solution)时，如果输入的puzzle不合法（如同一行中有两个同样的数字），没有返回false原因
合作小组对非法数组进行了异常处理，会抛出一个InvalidPuzzleException，但是没有把Exception包含在Core.dll中，双方异常处理的位置和方式不同
我们小组的GUI和Core之间存在标准接口以外的交互，在Core中自定义了很多东西，导致合作小组无法正常使用。根本原因是我们小组在做GUI的部分时对Core的使用不规范，没有完全按照定义的接口使用而是设置了其他变量，因此原有的GUI的代码也无法使用其他小组的Core.dll。改进
对GUI界面部分的代码进行修改，调用Core的标准接口。
另外我们的异常处理都在计算模块外部进行，即默认传入Core的接口的参数合法，应该对参数进行检查，使它有一定的异常处理能力。另外应该向合作小组学习，他们的Core模块非常简洁，包装非常好除了必要的接口没有多余的东西，可以模块划分应该也做得非常好，我们不应该把计算模块、输入输出都混杂在Core里面。总结
- 没有对项目进行充分的设计和时间规划，在需求分析和设计上花费的时间明显不足，导致对进度的把握很不好。
- 从对方身上可以看到一些独特的思维方式以及非常执著的精神品质，非常的值得学习。
- 结对双方没有争论但是对课程的理解、关注的重点不一致。