个人项目博客(二)
需求分析
实现一个命令行程序,程序能:
1、生成不重复的数独终局至文件。
2、读取文件内的数独问题,求解并将结果输出到文件。
模块划分
程序从命令行得到命令与参数,并根据命令实现两个功能,因此把程序初步划分为以下模块:
-
命令判断与处理
从命令行获得命令后,判断命令类型是生成命令还是解决命令,并检查参数是否正确(如生成数独的参数必须是1-1e6范围内的数字),参数正确则调用并传参给相应的模块。 -
生成数独
生成指定数量的数独终局,并按格式写入 sudoku.txt 文件。 -
解决数独
从指定的路径读入待解决的数独题目,将可行解按格式写入 sudoku.txt 文件。
功能建模
通过数据流图来进行功能建模。
顶层图:
一层图:
解决思路描述
命令的判断与处理
命令的判断与处理即简单的输入判断。当输入为地址时,进入生成数独模块;当输入为合乎规范的数字时,进入解决数独模块;当输入错误时,返回错误信息。
生成数独
参考了xxrxxr.的算法,通过模版和行列交换生成数独终局。
-
通过第一行数字和模板,产生一个原始的数独矩阵
找到一个终局模版,因为交换其数字固定排列顺序不会破坏数字之间的关系。通过对第一行数字的交换,并依此交换方式生成下面每一行,就可以生成新的终局。第一行的总情况有 8!= 40320种,该方法最终可生成终局数即第一行情况属。 -
通过对这个数独矩阵的行和列进行局部交换,产生符合数独要求的不同数独矩阵。
对第一种方法生成的原始矩阵,可通过行列变换来生成更多的矩阵。把9行分为三个大行,第一个大行包括第2行和第3行,这时可以选择交换第2行和第3行,所以第一个大行有2种情况。第二个大行包括第4,5,6行,此时这三行的每一种全排列交换情况都可以,比如我可以通过交换让第二个大行变成(4,6,5),所以第二个大行有6种,同理第三个大行也有6种。列变换与行变换同理。 -
最终结果
所以我们可以得到,对于每一个原始矩阵,我们可以产生22666*6种数独矩阵,而原始数独矩阵的产生,即之前说的第一个过程和这里的行列交换是互相独立的,所以一共的情况数是8! * 4 * 6 * 6 * 6 * 6
解决数独
这是一个很经典的问题,之前就遇到过,采用枚举+深搜的算法,就可以解决这一问题。