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

项目简介

[github]链接: https://github.com/kindoms214/Sudoku.

1、项目要求

• 能够生成1-1e6个不一样的数独终局并输出到文件（命令：sudoku.exe -c abc)
• 读取文件中的数独问题，求解并将结果输出到文件（命令：sudoku.exe -s path）
• 附加题要求：为数独游戏生成一个GUI界面，能够生成任意数量的数独题目并依次显示，9*9棋盘上挖空数目30<=n<=60。用户可以在界面上方点击或输入完成数独题目。用户完成数独题目后可以得到反馈，知道自己的题目是否做对。

2、PSP表格

3、解题思路及过程

  拿到题目后感觉难度并不会特别大所以并没有去考虑结队项目。而且之前也比较喜欢玩数独，基础形式的数独也玩了不少，所以感觉题目难度并不会太大，最主要的是明确相应的数独生成及求解算法。至于附加题，因为有认识的同学会使用QT，所以到时候遇到具体问题也不是没有办法解决。

3.1数独终局生成解决过程

• 题目思路
    首先，我们应该明确一点的是，9*9数独中的每一行、每一列及每一宫都必须无重复的出现0-9的每一个数字。生成数独终局，很容易想到的是全排列，因为数独中的每一行都是数字0-9的一个排列，因此每一行的数字的排列方式一定是9！中的一种。当然由于题目条件的限制，数独第一行的数字是8！中的一种。但需要注意的是，数独游戏的限制要求每一列及每一宫也不能出现0-9中的重复数字。所以我想到了通过第一行数字平移特定位数来生成其他行数的方法。
    最开始映入脑海中的想法是，第二行通过第一行移动一位来产生，第三行通过第一行移动两位来产生……这个想法显然不行，因为它只满足了行和列的要求，并没有满足每一宫中的要求。那么既然每次移动一位不行，那我每三行划分成一组，然后通过三列三列的移动，是否有效？在进行验证之前我先简单的阐述一下具体的过程。方便起见，我们先用数组a[1]-a[9]表示第一行的数。第二行通过第一行移动三位得到，第三行通过第二行移动三位得到，那么第四行呢？因为第四行中没有和第一行的数处于同一宫的可能，只需满足行与列上的关系，所以只需要按照最开始的想法通过第一行移动一位即可！然后4~6行按照1~3行的变换获取。第7行再利用第4行右移一位获得然后同样按照1~3行的变换生成7~9行的变换即可完成整个数独的生成。
  
    可以看到，这样生成的数独矩阵是满足每一行、每一列及每一宫无重复出现a[1]~a[9]中每个数的条件。因此，按照这种生成数独的话，一共能生成8！个（第一行第一位固定为4）有效的数独。但8！=40320<1e6，不及题目要求的数量。但仔细思考后我发现，对于每个数独终局来说，交换2、3行，交换4、5、6行，或者交换7、8、9行的数据便可以生成新的数据终局（不用管具体的数，只需要观察上面的“代号”数组a[1]-a[9]即可）。这样终局生成总数就来到了8！*2*3!*3!=2903040种结果，这也就意味着1e6的条件能够满足。