智慧金字塔游戏解题算法

介绍

前一段时间看了邰晓梅老师的一段视频, 她用了智慧金字塔这个小游戏来演示如何进行探索性测试. 看了之后很有启发, 探索的过程用了一些技巧, 比如每次一段尝试时会对小方块做一个基本的分类, 还有利用直觉调整尝试的优先级, 还有对所有进行过的尝试有一个记录可以避免重复也方便退回重来.

游戏本身并不复杂, 大体就是一个55格的金字塔形的棋盘,有12个不同形状的小方块,题目会根据难易程度事先先摆好一些方块在棋盘上(越难摆的越少), 我们的任务就是把剩下的方块放进去组成完整的金字塔.

看到这么有意思的东西, 显然我也要买一个来玩玩, 目前已经完成了简单阶段(还有困难和超难…). 虽然还没有进军高难题目, 但是身为一个程序员, 偷懒的本性就上来了, 为什么不写一个程序来解题, 于是就有了下面的故事.

开始

最开始是需求, 我打算做一个能够显示图形的游戏, 暂定是控制台打印, 其次要能根据提前设定好的题目算出答案并展示出来, 最好还要有一些过程演示, 因为我想看看电脑是怎么想的, 和人做有什么区别. 因为工作要用Java, 就用Java写吧, 正好练练手. 当然也要TDD了, 但是因为已经可以想到这个题算法比重大, 估计写起来很纠结.

算法

最开始没什么想法, 准备就按照人解题的思路进行, 就是深度优先搜索, 其中加入一些检查来剪枝(这个就是电脑的探索性测试了). 但是总是隐隐觉得这样做太无脑, 因为题目显然有一些通用的限制, 比如你不可能把两个方块重叠摆放, 如果只是单纯加入一些检查, 感觉效率很低.

于是自然就要借鉴前人的智慧, 在网上搜了一会真的发现了好东西.

Dancing Links

原来这一类拼图的问题可以算作精确覆盖问题(Exact Cover), 类似的比如数独, 八皇后, 而这类问题有一个通用的算法就是X(Algorithm X), 而实现算法X最好的方法就是舞蹈链(Dancing Links, 提出者Donald E.Knuth). 顺带一提精确覆盖问题是一个NP完全的问题哦.

算法大概就是需要先对问题建模, 列出一个0-1矩阵, 列对应了的限制的规则, 行对应了所有可能解的基本元素. 然后问题就转化成了求解这个0-1矩阵的精确覆盖问题, 然后把这个0-1矩阵用十字双向循环链表表示, 算法本身有点小复杂就不详细说了(因为不画图太难解释了). 因为算法过程中利用了双向链表的快速删除/插入元素的特性, 所以效率非常高, 假如过程中的链表能够以图像方式展示出来的话, 你会看到链表的节点飞快的移出当前位置然后又回来, 就像跳舞一样, 这个就是Dancing Links这个名字的由来.

我当时看到这个算法, 真的被它的神奇优雅打动了, 于是就写了现在的这个文章, 就是想要和大家分享一下这个神奇的算法.

数据模型

对于智慧金字塔而言, 在0-1矩阵里我需要一列代表题目初始状态, 12列分别代表不同小方块, 每一个方块只能在特定的那一列上为1, 还需要55列表示整个棋盘的状态.

然后对于每一行, 我需要特别的一行表示棋盘的初始状态, 剩下的每行表示每一个单独的方块在每一种不同的形态下在棋盘上每一个可能的摆放位置, 不精确计算的话大概有12方块乘8种摆放角度乘50个左右的摆放可能. 因为有的方块是对称的, 没有8个摆放角度那么多, 同时有些方块奇形怪状, 也不会有50个那么多的摆放可能, 所以估算的话大概有2000行左右. 于是问题变成了求解一个68 x 2000的0-1矩阵的精确覆盖问题, 如果能找到一系列的行组合后能恰好保证每一列都是1, 那么这个就是解.

原理

上面的东西是不是感觉很神奇, 是不是没看懂? 其实我一开始也看不懂, 但是感觉很厉害的样子. 后来仔细研究了才发现真的很厉害.

算法本身是可以算作深度优先搜索加回溯, 但是其神奇之处在于构造了这个0-1矩阵, 其实是相当于预先存好了所有可能的步骤,再利用Dancing Links高效的在这个解空间中前进, 本质上是空间换时间提高了效率. 因为精确覆盖的特殊性, 每一列只能有一个元素同时占用, 利用链表可以轻松删除其他冲突的节点, 然后在回溯的时候利用双向链表的特殊优势轻松的还原, 以此达到最高效率.

思考

在我手工做题的时候发现了一些小技巧, 比如某些方块摆好后发现它们围起了几个空格, 但是这个空格和其他剩下的方块一个都不匹配, 于是我就可以快速的排除这个摆法.

然后我发现Dancing Links天生就能做出这个优化, 前面讲到, 当你选择尝试一个元素时, 算法会将对应列上的其他元素暂时删除, 对应上面的技巧就是删除的时候就已经排除了所有不可能在剩下的空格中摆放的元素了, 自然也和人一样得出一样的结论了.

还有一个做题小技巧就是优先摆放一些可以放在边边角角的方块, 因为对于这些位置, 你可用的方块里面很有可能只有几个才有可能摆放在那里, 其他一些无论如何都是不可能放在那个位置的. 所以我会先在这些位置尝试一些方块, 显然能够提高效率.

这么有用的技巧, 算法当然也要实现啦. 对于算法来说就是在开始尝试一列的时候尽量选择行数较少的那一列, 这样筛选出来的基本上就是那些边边角角的位置, 或者只有较少方块能够放进去的位置. 这样做能提高多少效率呢, 我一开始没这么优化, 解第355道题的时候用了45秒才出结果, 但是用了这个优化之后, 时间缩短到0.1秒!

其实还有一个解题的小技巧, 就是有一些方块能组合出一些比较规则的形状, 比如三角形, 或者方形, 或是一些其他的形状, 其实组合后的形状之前本身并无差异, 但是人比较容易记住规则的形状, 所以那些能组成三角或方形的组合我记得比较清楚, 当摆放的时候出现类似的空档, 我会优先尝试使用那些组合来尝试.

这个当然也能在算法中实现, 只要事先构造好一些组合放在矩阵里就行, 但是我还没有实现, 我预计这样能够提高一些效率, 但是也很难说啦, 等我实现了之后做一些比较再下结论吧.

其实上面这些优化都算是启发式算法吧, 果然暴力搜索不可取, 还是要加上一些启发式规则的.

虽然算法能够实现各种优化, 但是有一个技巧就不行了, 那就是人类的直觉, 邰晓梅老师说过有时候人要相信自己的直觉. 这么模糊的东西连我自己都说不清楚自然也不可能写到算法里了, 难道这个就是电脑和人的差距所在吗 :)

TDD

整个程序实现分成两个部分, 一个是棋盘和棋子的数据结构和一些基本操作, 这些和算法无关, 就是一些对象的事, 还有一部分就是解题算法的实现.

在做第一部分的时候TDD进行的还算顺利, 虽然有些地方为了要不要返回值和要不要暴露方法纠结了一会, 但大体做到了以测试目标来驱动实现的过程.

但是到了实现算法部分, 真的纠结了, 因为算法本身的整体性加上是个递归算法, 一开始真的没想好要怎么分解测试目标, 最后勉强分成了单个元素, 两个元素, 然后就直接上递归全部实现了, 步子迈的太大了, 所以也造成了一些问题.

中间实现算法的时候有一个关键点是实现那个特殊的数据结构-十字双向循环链表, 因为一开始没有想好的缘故, 我把它和算法实现混在了一起, 导致实现的过程中经常纠结链表本身的一些基本操作比如删除/恢复(其实当我对算法需要的操作本身也理解不够). 如果当时能够单独对这个链表的实现TDD一下, 后面应该就不会那么痛苦了.

值得一提的是基本算法完成后, 我再加入一些优化的时候, 之前写的测试让我对我做出的修改有了很大的保障和信心, 这也是TDD的一个优势所在.

还有一个实践TDD的问题是, 我一般不会把测试覆盖的那么全, 比如在实现所有小方块对象的时候, 因为方块太多了, 有12块, 每块还有8个方向, 我只测试了其中一个方块的实现, 其他的感觉上是没有问题了, 但是事实上还真有问题. 这是到了非常后面, 开始求解实际题目的时候发现怎么都没有解, 调试了半天才发现其中一个方块的实现错了.

对于这种事情不知道大家是怎么看待的?
是觉得 A. 测试还是得覆盖好(纪律性)
还是说 B. 这是不可避免的代价(相信自己, 加快实现)
或者是 C. 要有某种平衡(因为你显然不能100%覆盖, 但是也不能对一些复杂实现不去测试)
还有 D. 随心所欲流(相信直觉, 想测就测, 想放就放)

代码

Github: https://github.com/yesterdaysun/pyramid

代码本身还在完善中, 有什么问题大家尽管提啊.

代码实现了一个算法解题的动画过程, 但是因为是在控制台里面进行的, 所以如果要运行的话要在真实的Terminal下运行, 另外因为要实现动画使用了一些特殊的控制码, 不确定其他平台是否能顺利运行, 我本机Mac+iTerm2是没问题的.

总结

学到了一个新的算法, 很开心, 虽然对一些算法大牛来说这些都是小case, 但是对我这个半吊子来说,能够用新学到的算法解决实际问题还是很有成就感的.

P.S. 某人发朋友圈说有个题两个礼拜还没解开, 希望这个小程序能有帮助 :)