Python数独算法

前段时间公司为程序猿们举办了技术周,技术周上有很多像数独,数字华容道等锻炼逻辑思维的小游戏,玩家需要在规定时间完成上面的逻辑挑战,就可获得相应奖品,当时在现场拿了几道数独的题目来做,刚开始还好,后面做着做着就发现走进了死胡同,只能一步步往前回溯,但有时候又忘记前几步在哪儿填的是什么数了,以致于最后还是没能做出来,后来不死心的把题目带回来,想着用Python脚本实现数独的填写,也锻炼一下自己的算法思维,自己琢磨了好几天,也总算是搞出来了,本文主要讲算法思路,具体代码详见文后链接,(代码均已注释)

数独规则:

玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复;

算法思路:

1.对于一个数独,每一个空格填入的候选值应该是确定的,首先计算每个空格可填入的候选值,并按照候选值的个数升序排列,(首先选择确定性较大的空格填入);

2.在填入候选值后,刷新数独矩阵,并重新计算空格位置的可选值;

3.当空格位置的候选值个数为0且数独里仍有空格存在时,说明在前面某一步候选值填的有错,需要回溯,回溯到错误上一步时,如果候选值个数为1,说明错误还在前面,但需要将此处值重新置为0;

4.按照步骤3依次回溯,当回溯到候选值个数大于1时,(说明错误有可能是在此处发生),将指针指向此位置的下一个候选值填入,在重新刷新记录插入位置和值的字典,并重复进行步骤1,2;

5.当记录步骤1的字典(空格位置及所有候选值)为空时,说明所有空格均已填完,则跳出所有循环;

算法详解:

1.将整个数独看成一个9*9的矩阵,而根据游戏规则,对于任一个数独空格,在数独最初时候,每一个空格可填入的值应该是确定,例如下图这个数独,在00号位置,可填写的值[1,7,9]

遍历每一个空格,记录每个空格可填入的数字及位置,并按照可填入数字的个数升序排序,此时记为字典A(我们自己填写时候,肯定也是从确定性最大的空格开始填起,已缩短计算时间),

2.将排序后的第一个候选值填入相应位置,此时需要在生成记录一个填写位置及填入值的字典B,然后重新刷新数独矩阵以及字典A,在重新将字典A中的第一个值填入,并更新字典B,循环上述过程,直至字典A的长度为0(此时矩阵中已无空格),循环结束;

3.真正实现实现时,结果并不会像上述那样好运,当在某一步填写的可能值填写错误时,会导致后面某一步可填写的值为空,例如上面00号位置,从最终结果上看,此处应该填9,但是如果在最开始时候将此位置填1,那么在后面的某一步肯定会出现某一个位置可填写的值为空,这个时候,就需要我们就要利用字典B进行回溯了;

4.假如此时字典B(记录填写位置及填写值)如下,在51号位置上出现可选值为空,则往上一步回溯,上一步是在41号位置填写4,错误是不可能发生在此处的(为什么?)

[('01',[1,3]),('00',[9,7]),('31',[8]),('41',[4]),('51',[])]

需要将这个位置和候选值从字典B中删除,并将此位置的值重新置为0,此时字典B变成

[('01',[1,3]),('00',[9,7]),('31',[8])]

还需要进一步在往前回溯,那回溯到什么时候为止呢?回溯到错误最可能发生的地方为止,上图错误最有可能发生在00号位置,刚刚在00号位置填写的9,此时应该把9换成7填入,然后重新刷新数独矩阵及计算字典A(记录空格位置及所有可能值),当字典A的长度等于0时(表示所有空格都填完),整个循环结束;

数独规则:https://baike.baidu.com/item/%E6%95%B0%E7%8B%AC/74847?fr=aladdin

代码地址:https://github.com/maxiaoguai/sudoku

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181116G1SNZ200?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券