python挑战骨灰级难度数独-数独 python 解题过程

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

数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。标准数独由9行，9列共81的小格子构成。分别在格子中填入1到9的数字，并满足下面的条件。

现在我们访问在线数独网站（http://www.cn.sudokupuzzle.org/），选择其中骨灰级难度的数独，如下图所示

接下来，我们就用python来解决这个数独，其中使用的算法是深度优先搜索。

深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

在程序中用time计时的起始时间是从第一行import time模块之后就开始了，运行结果如下：

python挑战骨灰级数独

网站提供答案如下

python挑战骨灰级数独

查看答案发现求解正确，至此有没有感觉到python的强大，骨灰级的数独都不在话下，那么入门级的更是小菜一碟啦，代码获取请看公众号《python练手项目实战》回复“数独”，从此告别数独难题，开启数独称霸之路。

参考：

https://blog.csdn.net/littlethunder/article/details/9749509

https://www.cnblogs.com/LukeStepByStep/p/5694454.html