基于Python实现数独游戏【100011897】

# 数独游戏 # 需求分析 - 生成 不重复 的数独终局至文件，并满足以下三个条件： - 保证每一个数独终局左上角的第一个数字必须为 `(1 + 3) % 9 + 1 = 5` - 所有数独终局不重复 - 生成1000个数独终局的时间限制在60s内 - 读取文件内的数独问题，求解并将结果输出到文件，需要满足以下条件： - 求解1000个数独题的时间限制在60s内 # 解题思路 ## 生成数独 我们知道，一个9×9的合法数独终局需要同时满足以下3个要求： 1. 每行单元格包含整数1到9，且每个数恰好出现一次。 2. 每列单元格包含整数1到9，且每个数恰好出现一次。 3. 每个3×3的宫包含整数1到9，且每个数恰好出现一次。 经过查阅资料，我找到了生成数独终局的以下三种方法： 1. 暴力搜索+回溯 2. 矩阵变换法 3. 全排列平移+行变换 对于上述三种方法，我们依次来分析。首先，方法1是通过不断的填数、检查和回溯去生成一个终局，而一般我们尽量避免使用暴力搜索的方法，因为虽然它们可以生成质量不错的数独终局，但是非常耗时。 对于方法2和方法3，我参考了这篇博客 - [数独终盘生成的几种方法](https://my.oschina.net/wangmengjun/blog/781984) ，为了说明这两种方法，我先来介绍数独终局在交换方面拥有的3个性质： 1. 交换9×9的合法数独终局的两列，如果被交换的两列同时在左三列或中间三列或右三列，那么交换后得到的数独终局是合法的。 2. 交换9×9的合法数独终局的两行，如果被交换的两行同时在上三行或中间三列或下三行，那么交换后得到的数独终局是合法的。 3. 将9×9的合法数独终局中的两个数字的全部位置兑换，得到的数独终局是合法的。例如交换数字1和数字2，即把所有填数字1的位置改为数字2，所有填数字2的位置改为数字1。 根据上述的三条性质，矩阵变换法的基本思想就形成了：选择一个初始的种子数独终局，根据上述三条性质，随机地对该数独终局进行交换，交换的次数不限，同时随机地对数独终局进行 0或90或180或2700或90或180或270 的旋转，则可以得到一个合法的数独终局。这种方法不仅效率高，实现方便，且生成的数独终局两两重复的概率很低。但是我认为该方法存在一个问题：对于这种随机的方法，虽然解空间很大，生成重复的终局概率很低，但是我们也无法从理论上证明生成的1000000个终局中不存在重复数独。因此我选择了第三个方法。 方法3的基本思想是：对数字1到9进行全排列，对于每一个排列情况，将其作为数独终局的第一行，然后从第2行开始，每一行的数字分别是第一行数字向右偏移3、6、1、4、7、2、5、8位，这样就可以生成一个合法的数独终局，然后利用交换性质，在第2和3行之间、第4、5、6行之间、第7、8、9行之间两两交换，要把所有的交换都遍历到且不重复。根据上述描述，在第一位数字确定的情况下，我们可以生成的终局有 8!×2!×3!×3!=29030408!×2!×3!×3!=2903040 个，这数量远超过1000000。因为在生成的过程中，无论是第一行的生成还是交换行的方法，我们都严格的把所有情况按照全排列的顺序遍历，所以生成的终局一定两两不重复。 ## 求解数独 目前我找到的方法有以下三种： - [暴力枚举+深度优先搜索](https://zhuanlan.zhihu.com/p/31865810?utm_source=qq&utm_medium=social) - [舞蹈链算法](https://www.cnblogs.com/grenet/p/3163550.html) - 基于约束程序方法的数独问题求解研究[4] 在[舞蹈链算法](https://www.cnblogs.com/grenet/p/3163550.html)这篇文章中作者用自己实现和多次改进的舞蹈链算法与暴力求解算法进行了多次对比，根据他的讲解，我决定选择较为常用的暴力枚举+深度优先搜索算法来求解数独。 # 项目环境 | | | | ---------------- | ---------------- | | 编程语言 | Python3.7.9 | | 系统环境 | Windows10 20H2 | | 开发工具 | PyCharm 2020.2 | | 代码质量分析工具 | Pylint | | 性能分析工具 | PyCharm的Profile | | 单元测试工具 | Pytest | # 项目文件结构 项目用`Git`进行版本控制，托管在`Gitee`平台。 目前项目代码的组织如下： ``` sudoku-cli ├── main.py ├── performance │ ├── generate_endgames1.0.png │ ├── generate_endgames1.pstat │ ├── generate_endgames2.0.png │ ├── generate_endgames2.pstat │ ├── solve1.0.png │ ├── solve1.pstat │ ├── solve2.0.png │ └── solve2.pstat ├── sudoku │ ├── __init__.py │ ├── generate_endgames.py │ ├── generate_games.py │ └── sudoku_class.py └── test ├── __init__.py ├── test_generate_endgames.py ├── test_generate_games.py ├── test_sudoku_class.py └── test_system_main.py ``` `sudoku-cli` 为命令行版的数独项目，`main.py`为整个项目的入口函数，`sudoku`包主要包含了：`generate_endgames.py` (数独终局生成模块)、`generate_games.py`(数独开局生成模块)、`sudoku_class.py`(数独模块)；`test` 包中包含了各个模块的单元测试；`performance` 文件夹中包含了性能分析的报告。 # 代码设计 ## 命令行版的数独项目 项目主要的模块有以下四个： - `main.py`：项目的入口。负责与用户的交互，包括处理用户的输入和返回对应的信息。 - `generate_endgames.py`：其中包含`GenerateEndgames`类。负责生成数独终局。 - `generate_games.py`：其中包含`GenerateGames`类。负责生成数独开局。 - `sudoku_class.py`：其中包含了`Sudoku`类。主要负责求解数独。 类图如下：  - ``` GenerateEndgames ``` - `__init__`：初始化成员变量。 - `get`：获得当前的一个数独终局，即成员变量 `matrix_swap` 的值。 - `offset_first_row`：偏移第一行以生成数独终局。 - `swap_rows`：根据参数对数独进行行交换以生成数独终局。 - `generate`：生成数独终局的入口函数。负责调用各种成员函数以生成指定数目的数独终局并写入文件。 - `generate_one`：无条件地随机生成一个数独终局，该方法留给图形界面的数独游戏使用 - ``` GenerateGames ``` - `__init__`：初始化成员变量。 - `load`：加载一个外部数独，本质就是set方法，即将成员变量`matrix`设置为一个指定的数独。 - `get`：获得当前的一个数独终局，即成员变量 `matrix_swap` 的值。 - `write_to_file`：将数独写入文件 - `dig`：对数独进行挖空 - `generate`：生成数独开局的入口函数。负责调用各种成员函数把输入文件中的数独终局生成数独开局并写入文件。 - ``` Sudoku ``` - `__init__`：初始化成员变量。 - `load`：将输入的矩阵加载为类成员变量保存的数独。 - `load_from_file`：从外部文件加载数独。 - `get`：获得当前的一个数独终局，即成员变量 `matrix_swap` 的值。 - `is_vaild`：判断数独是否合法。 - `write_to_file`：将数独写入文件 - `solve`：求解当前类成员变量保存的数独。 - `solve_from_file`：求解输入文件中的数独。 ## 关键函数流程图 以下的流程图均为第一版命令行数独游戏的代码流程图 `GenerateEndgames`类的成员函数`generate`的流程图如下： ![](https://www.writebug.com/myres/stati