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控制符是正常的。
加快速度
其实代码中有很多东西是可以省略的,比如说找空格,只需要找一个就行了。
在寻找可填项(列、行)时,可以不找自身所在区块。