【软件工程基础】个人项目报告|数独终局生成及解决

【github链接】https://github.com/trrrrafarga/Sudoku

PSP表格

2.解题思路描述

(1)生成数独终局

看到这个题目首先想到暴力做,但是看到题目要求在1s内输出1e6个终局,很明显,如果不进行优化,直接的暴力输出是无法达到的。

接下来的思考,先生成一个数独终局,然后在该终局的基础上进行一些替换操作。在这里,我走了一些弯路,我想的是随机进行调换,然后判断其是否能够满足数独终局判断条件。首先这样可能会出现一些重复(即使是概率渺小)而且每一次都要判断增加了程序的运行时间。

我认为数独的第一行是至关重要的,在确定了第一个位置只能是8之后,还有八个数字可以选择。那么第一行就会有8!种可能(也就是40320种)。看数独是一个9*9的矩阵,那么会不会有什么规律能够根据第一行的变换生成一个终局。于是我查阅了一些资料。发现可以把第一行向右平移一定的位数,只要每一行平移的次数和之前的任意一行不一样,那么每一列也不会有重复的数字。接下来,考虑九宫格的不重复问题,我们只需要将每三行看成一组,组内向右移动都移动相差3的倍数个单位时就可以保证每宫内没有重复的数字。

通过这样的方法,我们不仅可以生成不重复的数独终局,而且省去了判断是否为数独终局这样一个很耗时的部分。由于第一行的第一个数字不能动,那么第一行只能平移0行,第二三行都可平移3或6个单位,我们记为036和063,456行的平移就很随意了,我们可以选择1,4,7三个数字自由组合就有了6种,789行选择2,5,8又有了6种,此时,对于每一个第一行排列就会有72种了,那么40320*720可比1e6要大惹。

(2)解决数独

解决数独我们就用了最经典的回溯法解决问题。

填充空缺,然后判断,如果可以就继续,如果不行就往回走。直到解决问题。

3.设计实现过程

本次实现采用C++语言

在主函数里,根据所输入的指令,看所需要实施的是哪类问题。整个问题总共设置了7个函数,除去主函数外,buildMove(int N)(利用全排列生成初始终局)BuildSudoku(char *rule1,char *rule2, char*rule3)(根据不同规则变化终局)print1()(输出终局)这三个解决数独终局问题,然后judge,move,change三个函数解决数独求解问题。

5.性能展示

为了改进性能,首先是更改了生成数独终局的方法,使其变得更加直接。在解决的时候加入了剪枝等操作,那么接下来就是性能分析图

我们可以看出在改变方法之后,输出1e6个终局耗费最多的是输出部分。

 

6.代码说明

生成数独终局中最关键的就是调换和全排列生成。

这里的规则rule就是我们之前说的036,147之类的交换规则。

我们先把除了8之外的数字加入一个数组生成全排列,然后根据思路里的规律来进行变换

解决问题时,就是一个回溯算法,比较关键的是判断时要考虑九宫格的问题,在搜索资料的时候找到了一个比较好的办法。

7.实际表格

 

 

 

 

 

《【软件工程基础】个人项目报告|数独终局生成及解决》有2个想法

发表评论

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