数独项目2.0版本

目录:

Github地址

https://github.com/ZhaoYi1031/Sudoku_Pair


最终效果图

《数独项目2.0版本》

《数独项目2.0版本》

第一阶段

难度(初级/中等/复杂)界定

关于难度的界定,我们小组没有只采取空格数界定难度的方式,因为数独的难度空格多不一定难的. 比如 欧泊颗数独这里列的全是17数的数独,但玩入门级与骨灰级,根本不是一个概念。

因此我阅读了一些相关资料,从这篇博文,又引入了自由度的概念。

数独的空格自由度,指除掉空格本身,空格所在行、列、九宫内的空格数总和。

因此,当只剩一个空格时,此时的自由度为0;当数独全为时,空格数为81,空间自由度为81*24=1944达到最大。

自由度越大代表数独越难,但自由度和空格数不完全程正比。因此那篇博主进行了自由度的阶段区分,并在后文中验证了模型的合理性。

《数独项目2.0版本》

我们关于自由度的定义和他略有不同,主要在于他在算同一行同一列的自由度时,算入了自己。而我们没有。他最终分了10个等级,我们要求的是3个。因此我们最终的难度设定如下:

简单 中等 复杂
空格数范围 [40,49] [50,56] [56,65]
自由度范围 [0,650] [651,999] [1000,1944]

计算模块接口的设计与实现过程

首先主要的生成&求解仍然采用之前的回溯的方法,求解方面加了一点优化,关于这方面的具体思路见博客数独_个人项目。然后针对这次的新要求,在生成具有限制个数的数独时,我采用的方法就是先生成足够多的满数独,然后进行挖空。其中挖空的策略仍然采用回溯:如果要挖空number个格子,那么每个格子被挖空的几率就是number/81,我们每次
都按照这个几率去决定格子的去留,执行一遍dfs. 一点小优化就是如果发现后面的格子都填上才能刚好够number,就直接挖空;如果空的格子已经达到了number, 那么之后的就直接保留。

流程图如下:

《数独项目2.0版本》

具体的Core类的所有函数即功能如下:

UI方面,当新开始一个不同难度的游戏时,generate(1, mode, res)即生成一个模式为mode的数独到数组中即可。然后在提示或者提交的时候,对当前的数独进行solve(puzzle, solution)判断有没有接以及求出解即可。

UML类图显示各个实体间关系

《数独项目2.0版本》

单元测试

例如我测试求解一个数独是不是有唯一解这个函数,我就通过来填入一个有多个解的数独来进行求解其解数,来进行判断。之后我也对有唯一解的数独进行了测试。

测试的原函数代码如下:

再例如测试-n -r,并且r1 > r2的例子,我是通过在generate里捕获异常把一个布尔变量hasException置为true来判断的:

而我的generate函数的代码如下:

单元测试覆盖率截图

一共测试了20个例子,最终总的覆盖率为94%,主要的函数实现的cpp文件达到了98%,如下图:

《数独项目2.0版本》

第二阶段

界面模块的详细设计过程。在博客中详细介绍界面模块是如何设计的,并写一些必要的代码说明解释实现过程。

游戏一共有两个界面,一个是coverWindow(封面),另一个是gameWindow(游戏界面)。在coverWindow中放置了一个QLabel呈现”SUDOKU”标题和三个QPushButton来对应”Start”、”Record”、和”Setting”。玩家单击”Start”按钮可以切换到游戏界面gameWindow,单击”Record”按钮查看三个难度的最佳记录,单击”Setting”来设置游戏难度。
在gameWindow中用81个QPushButton来呈现数独,9个QPushButton来填数,”clear”和”hint”两个QPushButton提供清除一个格子内容和显示一个格子的提示。”submit”QPushButton用于检查答案,”home”按钮用于返回coverWindow。一个计时器用于记录花费的时间。玩家也可以通过上面的菜单栏来进行新的游戏或查看游戏规则等。

《数独项目2.0版本》
单击”Record”按钮查看三个难度的最佳记录。
《数独项目2.0版本》
单击”Setting”来设置游戏难度。
《数独项目2.0版本》
在gameWindow中用81个QPushButton来呈现数独,9个QPushButton来填数,”clear”和”hint”两个QPushButton分别对应清除一个格子内容和显示一个格子的提示。
《数独项目2.0版本》
使用”clear”和”hint”时先通过鼠标单击选中一个需要填数字的格子。
《数独项目2.0版本》
选中后该格子会变成绿色。
《数独项目2.0版本》
然后再点击”clear”按钮即可清空上面的数字。
《数独项目2.0版本》
或者点击”hint”按钮获得这个格子应该填的数字。
《数独项目2.0版本》
“submit”QPushButton用于检查答案。
《数独项目2.0版本》
“home”按钮用于返回coverWindow。
《数独项目2.0版本》
一个计时器用于记录花费的时间。点击时钟图标可以暂停和开始计时。
《数独项目2.0版本》
玩家也可以通过上面的菜单栏来进行新的游戏或查看游戏规则等。
《数独项目2.0版本》

核心代码如下:

数独矩阵上按钮对点击事件的相应:

检查用户提交答案的正确性:

为按钮添加缩放动画:

界面模块与计算模块的对接

将计算模块封装在Core类里,生成dll文件供UI模块调用,并将计算模块的头文件放入UI模块中。
《数独项目2.0版本》
《数独项目2.0版本》

实现对接的代码, 调用generate生成数独初局:

调用solve求解数独:

第三阶段

互测

我们是三个小组进行互相测试的,我测试的是15061186安万贺,测试我们的是由15061187窦鑫泽来完成的。

首先我们测试安万贺小组的情况如下,我们先把他们的Core.dll和Core.lib拷贝到了我们的sudokuGUI工程下进行测试,发现他们的生成有这样的问题,就是不管怎么开始,终盘的第一行总是1..9,即如下效果:

《数独项目2.0版本》

《数独项目2.0版本》

然后我就给他们提出了issue,后来通过交流发现他们的随机化放在了GUI里而不是generate里进行随机,因此导致我们用的时候总是1..9。

另外是关于命令行的调用。我发现不管是调用generate(1, 1, 53, false, a); 还是c.generate(1, 54, 53, false, a); 或者c.generate(1, 20, 500000, false, a);

反馈的错误都是:

The number after -r is not in the range.

然后我希望能够他们区分这些错误,就提了issue.

一个可能的测试代码如下:

还有一个问题是关于solve的异常捕捉的。

如果solve函数的puzzle函数是一个本身就非法的数独,例如一行有两个数是一样的情况,没有捕捉到异常或者返回false,而是也求了一个解。

一个可能的测试代码如下. 这个矩阵的第一行有两个9,显然是无解的

而最终却给出了一个解如下:

然后是别人给我们的测试进行的修正。最初始的改正就是把generate的数组的参数从83改成了81,即宏定义的M值。(之前写成83是害怕溢出)因为发现如果参数不同是无法调用别人的函数的。

根据窦哥给我们组的issue如下,是几个比较中肯与实际的测试问题:

《数独项目2.0版本》

软件只能通过右上角的红叉来结束,在开始界面中没有退出软件的按钮。
《数独项目2.0版本》
于是我们增加了可以在开始界面中退出游戏的按钮。
《数独项目2.0版本》

软件在点击”home”按钮返回开始界面时没有”Setting”按钮,影响用户体验。
《数独项目2.0版本》
于是我们修复了这个bug,时用户可以在游戏途中返回主界面对游戏难度进行设置,从而优化了用户体验
《数独项目2.0版本》

然后第三点,关于sudoku.exe -c abc, 其中abc是个不存在的文件,此时我们的是不能识别这个异常的。相当于直接闷声过去了。然后增加的修改如下:

用fopen判断是不是NULL就可以增加捕捉了这个异常。

第五阶段

通过增量修改的方式,改进程序,发布一个真正的软件


用户的反馈:
用户1:按钮有动态效果,界面很好看。
用户2:支持键盘输入数字,很方便。
用户3:No Solution的意义不是很明确。
用户4:成功求解数独弹出right之后点击ok能返回主界面就好了。
用户5:没有音效。
用户6:没有暂停功能。
用户7:点击黑色按钮最好不要有动画,因为不能填数字。
用户8:不太明白record保存的是什么,如果可以让玩家自己输入文件名就好了。
用户9:可以提示哪些数字是填错的就好了。
用户10:游戏介绍是中文的就好了。

改进:
用户3. No Solution就是代表当前数独无解,意思应该还是比较明确吧。
用户4. 成功求解数独弹出right之后点击ok停留在当前界面也挺好的吧,如果想重新玩的话通过左上角的New菜单进行难度选择即可。
用户5. 添加音效的话确实能够优化用户体验,不过时间不够了就不加了。
用户6. 增加了该功能,现在点击时钟图标可以暂停计时和开始计时了。

7.有动画也挺好看的啊,而且改起来没想象中的简单,就不改了。
9. 填一个数字按一下hint就可以直到当前填的这个数字是不是错的了
10.中文有的字会变为乱码,还是英文比较保险。

性能分析及改进


分别对-n 10000 -r 55~55-n 10000 -r 55~55 -u进行了测试,然后性能分析图如下,可以看到当没有考虑-u时,init_gen这个生成50000的函数的时间占据了主导,但是一旦当测试进了-u,这个占据的时间就是非常小的一部分,此时solve_unique函数就占据了主导,因为我们得一直从一个确定的数独终盘里面去挖空来找到有唯一接的数独。

《数独项目2.0版本》

《数独项目2.0版本》

《数独项目2.0版本》

考虑的优化如下:我们可以不是对一个确定的数独终盘进行一直来挖空,而是当一个数独终盘一直挖空不出唯一解时,跳到下一个进行执行。优化的代码如下:

阅读作业

看Design by Contract, Code Contract的内容,描述这些做法的优缺点, 说明你是如何把它们融入结对作业中的。


首先引用一段契约的概念:

契约作用于两方,每一方都会完成一些任务,从而促成契约的达成,但同时,每一方也会接受一些义务,作为制定契约的前提,有任意一方无视了必尽义的义务,则契约失败

契约式编程,我们在面向对象时曾经常用这个概念。我们当时在在设计程序的时候,需要明确地规定一个类的实例,在调用某个操作前后应当属于何种状态。我们当时需要在所有的类和方法前协商了前置条件,后置条件,不变式等等。

优点:代码规范,有利于实现者、设计者、使用者进行协作。
缺点:实现起来有困难,而是契约双方都需要履行责任。在一个大的项目里,一旦有人违反契约,后果不堪设想。

我在第二阶段处理异常时,就遇到了『遇到异常,是由我的Core程序catch住保证不crash还是throw给外面catch』的问题。当时弄的很头疼。最后我和我的partner约定了调用Core的要求,保证他调用时的参数是正确的,而另一方面,作为Core核心的编写者,对于预料范围内的参数错误,进行输出错误信息到控制台反馈给了调用者。

另外关于契约式编程,安利一下伯乐在线的这篇文章,契约式编程与防御式编程. 讲到了关于平衡的艺术,值得一读。

结对照片

《数独项目2.0版本》

结对编程优缺点

说明结对编程的优点和缺点。
结对的每一个人的优点和缺点在哪里 (要列出至少三个优点和一个缺点)。(5′)

  • 优点:提升团队协作的能力;有利于互相测试发现小错误;互相学习知识;学习氛围比较好,比一个人单干快。
  • 缺点:分工不好的时候,效率低下。另外需要互相了解,需要磨合。

partner优缺点

  • 优点:代码能力强;思路清晰;编码效率高;算法好;学习新知识快
  • 缺点:对于有些新事物有点排外;有些小问题有点缺乏主见。

我的优缺点:

  • 优点:具备一定的编程能力;接触较多;自认为有一点美工意识
  • 缺点:面向对象思维有待提升;写前端的速度捉鸡

看教科书和其它资料中关于Information Hiding, Interface Design, Loose Coupling的章节,说明你们在结对编程中是如何利用这些方法对接口进行设计的。

Information Hiding
就类似面向对象的封装的概念,把一些不能共享或者需要考虑安全的信息封装到内部,不让其他的使用者来修改这部分的内容。最明显的例子就是类里的private成员变量和函数。

Interface Design
接口是在一定粒度视图上同类事物的抽象表示。设计一套共用的interface来供多个对象来使用。对象的交互只需要通过接口来完成。

Loose Coupling
上计组时高小鹏老师曾经多次强调的代码设计应该保持的风格就是高内聚低耦合,而低耦合的概念就是模块和模块间的联系要少。这样有利于代码移植和互相测试。

具体地在我们的程序中最明显的一点就是,我们用Core模块来包装核心的实现generate等功能,然后生成动态链接库给其它的地方直接调用就好,这样既保证了别人无法修改你的generate函数实现信息隐藏,又非常便于调用和移植。然后互测也只要交换dll就好了,很是方便。

结对编程总结

人生第一次这种体验,我们采用的分工的方式,总体上我负责后端Core接口的编写、测试,他负责前端。界面的设计我也参与了其中,提供了一些美工和游戏的玩法设置上的建议,主要是颜色还有Button的颜色啊图片啊等等。形成了现在这种以黑色和红色为主色调的界面(和我最近穿的一件格子衬衫颜色几乎一样.-.)如果你们觉得设计的很土我背锅

然后感觉最大的收获就在于Git操作吧。虽然我们是双线并发作战,但仍然存在着两人一起改的冲突这样的局面,因此也算积累了一些协作编程写仓库的经验吧。下图是我们的Git信息的部分截图。

《数独项目2.0版本》

花费时间

PSP2.1 Personal Software Process Stages 预估耗时(分钟) 实际耗时(分钟)
Planning 计划
·Estimate ·估计这个任务需要多少时间 5 5
Development 开发
·Analysis ·需求分析(包括学习新技术) 60 80
·Design spec ·生成设计文档 0 0
·Design Review ·设计复审 0 0
·Coding Standard ·代码规范 60 90
·Design ·具体设计 120 30
·Coding ·具体编码 600 1800
·Code Review ·代码复审 100 140
·Test ·测试(自我测试,修改代码,提交修改) 120 240
Reporting 报告 150 150
·Test Report ·测试报告 15 25
·Size Measurement ·计算工作量 10 5
·Postmortem & Process Improvement Plan ·事后总结,并提出过程改进计划 15 10
合计 1265 2575
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注