解不出数独?有python这不存在的

接下来,我们就用python来解决这个数独,强大的语言配上强大的算法——深度优先搜索。基本思路是从第一个空格开始试着填数,从 1 开始填,如果 1 不满足横排竖排九宫格无重复的话,就再填入 2 ,以此类推,直到填入一个暂时满足规则的数,中断此格,移动到下一个空格重复这个过程。如果到达某个空格发现已经无数可选了,说明前面某一格填错了,那就返回上一格,从上一格的中断处继续往 9 尝试,直到这样回朔到填错的那一格。

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

原理就不多说了,拿出代码我们看效果。在程序中用time计时的起始时间是从第一行import time模块之后就开始了。

代码如下

求解结果

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180714G07VSL00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券