数独Python程序.详解 | Shanyang’s Notion

type

status

date

slug

summary

Sudoku-Python作品

1 前言微叙

本附属文档及Python作品，演示视频作者：张宁

就读学校：泌阳县第一高级中学

本作品灵感来源：Leetcode

关于此程序：本程序杂糅了作者在见到本题目开始至本程序截稿期间，个人想法，本校科技社成员间的交流，以及部分博文所体现出来的试错递归思想，数独矩阵技巧，下标数学问题。在经过多次测试后实现了本程序基础算法的完整性，可行性，快捷性，由于本程序主要集中于集合，算法，递归，函数学习。所以对于可视化，观赏性，本作品没有足够的精力来优化，但本程序体现了数学思想和Python的不可分割，以及数学思维，编程思维之间的相辅相成，希望评委能够给予支持，感谢。

2 程序简介

2.1 数独简介

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

注：本段来源于百度百科

3 实现思路

3.1 转换矩阵

3.1.1 代码实现

本段代码无任何技术难题，不再赘述。

3.2 探寻首格

3.2.1 码前思路

借助于本文档【1.1】中对数独的解释，可以得出解数独的第一步是寻找第一个空白格。对于人类而言，在短时间内的大量试错是极其浪费时间的，但对于具有极强计算能力的计算机来说，试错是比人类技巧更简单的一种方法

3.2.2 代码实现

在本程序的前部分，已经将数独转化为Python矩阵，并且将未填入的数字用0来代替。在本段代码中，通过使用两个for循环来确定0格的位置。倘若无0点，则证明本数独已然完成。

3.3 探寻下格

3.3.1 码前思路

如果将当前格填入之后，下一步的工作便是填入下一个空白格，但是在码前应当思考，下一格的坐标如何确定，如果单纯的以x+1便会致使程序只在第一行进行(若第一个空格在第一行的条件下)，所以这里要考虑空格的换行问题。

3.3.2 代码实现

本段代码在探寻下一行时使用了两个for 循环，第一个循环计算了在本行的条件下，通过用累加y值进行判断是否为0。第二个计算了下一列中的空格。其余不再赘述。

3.4 剔除筛选[重要]

3.4.1 码前思路

将 1~9 这个数字集合中，与行的数字集合、列的数字集合以及九宫格的数字集合重叠的部分去除。剩余的就是符合条件的集合。

3.4.2 代码实现

line2中的整除是为了得出在哪一宫，line3中的[i*3+r][j*3+c]是根据I,j(m[i*3][j*3]是本宫的起始位点)。并将横纵坐标用for循环累加。

Line4利用set，zip来确定具体的集合。

3.5 递归试错

3.5.1 码前思路

以首空格为基本，尝试下一个空格，若下一个空格的集合为空，则解数独失败，将此格填为0，再次试错。

3.5.2 代码实现

在本段代码中，通过对上一步获得的集合进行填数，从value中填入数字，倘若无空格，则返回True,如果在seenext中未探寻到空格，那么便会得到next_y=-1,故无下一个空白格。如果有下一个空白格，则进行下一个空白格的试错，直至end=True。本数独完成。

3.6 代码整合

3.6.1 代码实现

由于本段代码无任何技术性难题，不进行【码前思路】部分。

📏数独Python程序.详解