Python 穷举破解数独

前情提要

数独是一种数学游戏,最早发源于18世纪的瑞士。在校时同学从《中学生天地》上抄了一个数独给我。我对此保持不屑,“区区一个数独?可以秒杀我???”

然后我花了一节英语课的时间去尝试完成数独。

结果尝试了数百次,终于在填到最后一个块的时候,出现了“死循环”,无论怎么填都是错误的。这意味着我必须重新在某一个格子改掉数字,重写!!!

FA♂Q!我决定用编程穷举数独!

思路

数独最最最基本的写法就是——试错,不断的试错直到没有错误。什么是“没有错误”?数独时我们会遇到这个尴尬的桥段:

请问 “?” 处应该填写什么?从已经给出与已填写数字的双重压力下,“?”处已经没有任何一个可填数字。

我们只有一个方法——尝试更改上一个已填数字。所以只要知道每个格子在每个填写后之后的可填数字进行逐次尝试,在把每个尝试的结果带到数独中在次尝试,如果没有就换一个数字尝试......不断递归......就一定可以完全穷举出数独!

设计

打个简单的草稿:

 

要想研究数独,我们必须先给它编号,一步一步来研究,如上,

把每一个区块(粗线宫,我们标记为box)编号:从0开始,第一个叫0号,第二个叫1号。至于为什么从0开始,是因为在Python中数组调用下标是从0开始的,这样有便于我们写代码。

行就叫行(x),列就叫列(y)

上面这个数独是给人看的,但是机器看不到啊。赶紧转化成编程语言!这里我用数组来表示:

# 定义数独
sudoku = [[[0, 9, 0], [0, 0, 0], [5, 0, 0]], [[0, 0, 0], [0, 0, 0], [9, 0, 0]], [[0, 4, 0], [9, 0, 0], [0, 0, 1]],
          [[0, 0, 0], [0, 1, 0], [0, 0, 7]], [[6, 0, 0], [0, 0, 0], [0, 0, 9]], [[8, 0, 0], [0, 5, 0], [0, 0, 0]],
          [[0, 0, 0], [6, 0, 0], [0, 0, 0]], [[2, 0, 0], [0, 0, 0], [0, 7, 0]], [[0, 6, 0], [0, 0, 4], [0, 0, 0]]]

Wait!Wait!我来解释一下:

“0” 就是要填的数字,数独中是不可能出现 “0” 的,所以我们用“0”来标记再好不过了!(即对称又美观)

为了可以表示一个点的坐标,我们必须来定义一个坐标格式,我的想法是(框,列,行),这样是符合设计思路的,就是 pos = (0,0,0)

打印数独

虽说是机器看的数独,但是我们还是需要监督程序执行过程与最终结果输出,所以打印数独也是一个十分重要的一环。一个机器语言的数组由box、y、x定义,打印成9宫格,我选择一行一行的打印。然后把已经填写的数字打印成绿色(Windows与linux打印颜色有一点不同,这里使用的ESC控制符,linux系统下是完全支持的,Windows下对于部分的命令行支持,所以你在测试的时候可能会出现错误,需要自行的修改,这个下面会细讲)

这是打印0、1、2的区块,再把其它区块也以此打印。

我们封装成函数叫做 show() 看一下效果:

说明:

打印数独并不作为重点讲解,其中\033是ESC控制符开头,大家可以参考这篇资料:https://blog.csdn.net/lzuacm/article/details/8993785

取出格子的可填数字

接下来可是重点的一步,取出某个格子里可以填写的数字,我这里打算用函数封装,返回一个列表,列表是包含所有可填数字的列表,

sudoku是数独的意思,pos是当前要获取格子的坐标。

我定义了一个 mayb 的列表,里面放了所有的可能数字,后面会进行排查删除。

从简单的开始,从一个区块内开始排除:一个区块内的数字肯定不可以再填了,所以我们要循环遍历删除:

接下来是在同一列中进行删除:

我们知道坐标所在区块,区块有九个,三个一行,所以有三种情况:

体现在代码中就是这样:

最后就是行了,其思路与上面一样:

 

最后记得要 return mayb

现在输入一个坐标可以查看效果了。

开始递归

递归就是函数调用自己,我们先找到所有未填的格子,同样使用遍历的方法:

当没有空项的时候,有两种情况:①数独填完  ②此区块填完

为了判断这两种情况,还有一点就是区块编号是否为 8 ,是8,就是最后一个区块,填完意味着就是数独填完了。所以我们加一个判断:

之后就简单了,取出可填数字一个一个试:

真的这么简单?

出现了一个问题,递归并没有用,并没有一个一个试,而是当发现没有数字可以填的时候,只改变了一个数字,出现数字重叠等等问题。

为什么?

在对比了 nsudoku 与 sudoku 之后,我发现并没有得到不同的数据,举个栗子:

试问:上面的代码输出什么?

大部分人一定认为会输出 [1,2,3]   [2,2,3]

因为只更改了b列表,而没有更改a的列表,其实输出结果为:

什么?都改了?

是的,b=a的传递过程中,传递的是a列表的指针,而不是数据。修改b值时,就是在修改a。

如何解决这个问题呢?

list.copy()  是一个解决方法,可以复制列表的数据,但是如果列表中还有列表,就没有用了。

查阅资料后,得知 copy 库中有一个 deepcopy ,可以完全复制数据。

所以我们这么改:

开始测试

成功!

颜色符说明

Windows下常用Windows平台提供的DLL中的API设置颜色,大家可以看一下这篇文章:http://www.phpxs.com/code/1005030/

Linux系统使用ESC控制符是正常的。

加快速度

其实代码中有很多东西是可以省略的,比如说找空格,只需要找一个就行了。

在寻找可填项(列、行)时,可以不找自身所在区块。

发表评论 (1)

后再参与讨论
公告
公告