软件工程基础个人大作业 数独终局生成和求解

github项目地址https://github.com/lukal-new/new-potato/tree/sudoku

一、预计开发

Personal Software Process Stages	预估耗时（分钟）
计划	60
估计任务所需时间	20
开发	1500
需求分析	30
生成设计文档	40
设计复审	40
代码规范	300
具体设计	300
具体代码	600
具体编码	600
代码复审	60
测试	300
报告	120
测试报告	120
计算工作量	30
事后总结并提出过程改进计划	120
合计	4240

---

二、解题思路描述

首先了解数独的规则， 以下是摘自百度百科的内容。

数独（shù dú）是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复 。数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

根据题目意思，主要分为两部分。一是生成最多一百万个数独终局，并存入文件中，生成新文件要覆盖原文件。二是从某路径文件中读取最多一百万个数独，并求解存入文件中。以下内容主要描述算法和实现思路。

1.生成数独终局

数独的生成方法有很多种，比如随机法和行列变换法。但为了兼顾性能和输出时间，在此选择比较简单的一种算法。主要思路是随机生成第一行，然后从第二行开始，每一行是第一行右移3,6,1,4,7,2,5,8列的结果，这样就可以产生一个数独终局。由于题目要求第一行第一个数字必须是固定的，我的固定数字为9，所以只用生成第一行的后八位数字。这样可以产生的数独终局个数为8！=40320种。为了达到要求的一百万种，可以将已生成的数独做行列交换，因为第一行已经固定，所以第二行和第三行可以交换，四五六行可以互换，七八九行可以互换。所以最终可以产生2！*3！*3！8！=2903040种，远超要求的一百万种。为了简化代码，只对四五六行、七八九行进行互换即可，二三行可以不用动。这样就有3！*3！*8！=1451520种，也达到了要求。总结来说，使用的算法主要思路是，第一行的第一个数字固定为9，随机生成后8位数字，第一行右移3,6,1,4,7,2,5,8位依次得到剩下8行，可以互相交换四五六行、七八九行。最终输出每一行，可以得到题目要求的结果。

2.求解数独

求解数独的方法也有很多，比较典型的是回溯法，简单但效率比较低。回溯算法的主要思路是从根节点开始向下搜索，如该正在被搜索的节点有解，则向下继续搜索，如无解，则返回到该节点的父节点。对于数独求解问题，对所有空格，即为0的位置，可以依据全局找到可能填入的数字。从数字最少的空格开始，填入某一个数字，然后在数字第二少的空格填入数字，直到某一个空格无法填入位置，向上一个填入的空格返回，更换该空格填入的数字。题目要求是找到一个可行解即可，所以不用搜索完所有解空间，直到找到一个可以将所有空格填入的方法，则不用继续搜索。并且可以设计合适的剪枝条件，来提高搜索效率。

---

三、设计实现过程

1.数独的表示形式

四、描述改进过程

记录在改进程序性能上所花的时间，描述改进思路，展示性能分析图，展示程序中消耗最大的函数

---

五、代码说明

展示出项目关键代码，并解释思路与注释说明

---

六、实际花费时间

Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟
计划	60
估计任务所需时间	20
开发	1500
需求分析	30
生成设计文档	40
设计复审	40
代码规范	300
具体设计	300
具体代码	600
具体编码	600
代码复审	60
测试	300
报告	120
测试报告	120
计算工作量	30
事后总结并提出过程改进计划	120
合计	4240