软件工程个人项目——数独-1.5

Github项目地址 https://github.com/JackManTvO/sudoku
PSP表格

PSP2.1 Personal Software Process Stages 预估耗时(分钟) 实际耗时(分钟)
Planning 计划 20 12
Estimate 估计这个任务需要多少时间 20 12
Development 开发 520
Analysis 需求分析(包括学习新技术) 120 170
Design Spec 生成设计文档 30 55
Design Review 设计复审(和同时审核设计文档) 20 15
Coding Standard 代码规范(为目前的开发制定合适的规范) 20 10
Design 具体设计 60 80
Coding 具体编码 180 280
Code Review 代码复审 30 40
Test 测试(自我测试,修改代码,提交修改) 60 120
Reporting 报告 100
Test Report 测试报告 60
Size Measurement 计算工作量 10
Postmortem & Process Improvement Plan 事后总结,并提出过程改进计划 30
合计 640
解题思路 生成数独终局 ??数独的要求是在9×9的格子内,每一行和每一列和每一宫内都包含不重复的九个元素,但数独终局的个数共有6,670,903,752,021,072,936,960(6.67×1021)种组合,尽管终局要求左上角第一个数字为固定值,其终局的种数也是巨大的。而程序设计对终局数量的需求仅在1,000,000个以内,因此,没有必要穷举找到前1,000,000种终局,而没有合适的生成策略随机生成则可能造成终局的重复。因此需制定合适的生成终局策略,而我的生成终局策略为对固定的终局模板进行数字交换以及行交换。这种策略共可以生成8!(除首数字外8个数字两两交换)×2(23行交换)×6(4~6行两两交换)×6(7~9行两两交换)=2,903,040种终局,大于要求的终局数。根据要求生成的终局个数对变换方式进行深度优先搜索,第一层为数字交换,第二层为23行交换,第三层为4~6行交换,第四层为7~9行交换,以快速地遍历第四层的叶子,以生成多个不重复的终局。
??具体步骤如下:
  1. 生成一固定的有效终局作为模板。
  2. 对模板进行数字交换。
  3. 对进行数字交换后的终局进行行交换(2~3行交换、4~6行交换、7~9行交换)保证宫内不重复。
  4. 若生成终局数满足程序要求个数即返回,若不满足,重复进行步骤2、步骤3。
求解数独谜题 【软件工程个人项目——数独-1.5】??对于给定的数独谜题,按要求补充数独的空缺,以完成数独。因为填入的数需要满足数独的要求,所以每个固定位置的数值是有限制的,在剩余的可行值中选择一个填入空白,接着填入下一个空白。若发现无可行解,则父节点选择错误,采用回溯法,返回上一节点,填入另一可行解。直到生成树的层数等于空缺数,则生成一可行的数独终局,求解数独谜题成功。
??具体步骤如下:
  1. 扫描题目,将空白值坐标取出存入数组A。
  2. 在数组A中选择下一个坐标。
  3. 查询其所在行、列、宫的数值,填入可行解数组,在可行解数组中选取下一可行解填入。
  4. 若填入成功,则返回步骤2,若无可行解,则在数组A中返回上一坐标,返回步骤3填入另一可行解。若A中无剩余,则返回,求解数独成功。
设计实现过程 类 ??我设计了三个类,分别为向量类、点类和数独类(改进前)
Seed类(改进前)
变量名称 类型 说明
val int[9] 生成向量值
接口名称 参数类型 返回类型 功能
Seed null null 根据宏定义的首数字生成生成向量
swapi int(脚标1),int(脚标2) null 根据脚标交换向量中两数的位置
getVal int(脚标) int(结果) 根据脚标查询向量中数值
Point类(改进前)
变量名称 类型 说明
x int 横坐标
y int 纵坐标
pos int[10] 点的可行解标识
接口名称 参数类型 返回类型 功能
Point null null 初始化类
Point Point*(实例) null 初始化类使其值与实例相同
Sudoku类(改进前)
变量名称 类型 功能
seed Seed 生成向量
val int[9][9] 数独
zero Point[60] 空缺点集合
接口名称 参数类型 返回类型 功能
permuate int(层数) null 根据层数dfs全排列
mod null null 根据生成向量生成模板
generate null null 全排列交换行生成终局
cpy const Sudoku*(模板) null 根据模板复制数独
swapRow int(行数1),int(行数2) null 交换两行数值
write FILE*(文件) null 将数独写入文件
set char*(字符串),int(行数) null 将文件读出,按行给数独赋值
dfs null int(记号) 深度优先搜索,成功返回1,失败返回0
类图(改进后)
软件工程个人项目——数独-1.5
文章图片
Class Diagram.png 关键函数 元素交换函数
软件工程个人项目——数独-1.5
文章图片
permutate.png 行交换函数
软件工程个人项目——数独-1.5
文章图片
generate.png 解数独函数
软件工程个人项目——数独-1.5
文章图片
dfs.png 单元测试设计 ??使用了代码走读,并对三个关键函数使用路径测试法进行了单元测试:
元素交换函数
路径 输入数据 输出数据
path1 level=7 多个模板和终局
path2 level=10 无预期输出
path3 level=6,nsudoku=0 无预期输出
path4 level=6,nsudoku=1 1个终局
行交换函数
路径 输入数据 输出数据
path1 nsudoku=72 72个模板和终局
解数独函数
路径 输入数据 输出数据
path1 空点集 无预期输出
path2 包含3个点的点集 3个点值确定
改进 代码说明 附加题

    推荐阅读