精确覆盖下的数学游戏

[metaquant]

前期为了陪娃打发时间，入手了smartgames家的一款益智桌游，中文名叫做智慧大作战。游戏的规则和拼图比较类似，就是把总共十二个不同的形状放入到一个五乘十一的长方形当中，这十二个形状每个分别由三到五个小球拼接而成，十二个形状总共由五十五个小球组成，而长方形的凹槽数量也刚好为五十五个，所以如果拼对的话，十二个形状刚好可以完美的放到这个长方形中。玩具中附带一个题卡册，其中的题目已经给出了一些形状的位置，玩家的任务就是把剩余的那些形状放到正确的位置，题卡保证每个题目只有一种解法。题卡中靠前的题目已经放好的形状比较多，所以比较容易完成，而越往后已经放入的形状就越少，需要玩家自己完成的部分就越多，困难程度也会大大提升。

虽然家中神兽目前也玩过不少拼图，拼图技能颇为娴熟，但面对这个游戏仍然感觉难度很大，玩了几局就兴趣索然了，看来为父只能在“压箱底玩具榜“中又增加一个了。经过几次失败的尝试，我发现这个游戏的难度比自己预想的要大得多，虽然只有十二个简单形状，但是要成功拼完，常常需要经过多次尝试，而且往往一开始拼得越顺利，最后就越难拼成功，这使得我越发好奇这个游戏背后的原理。

经过一番搜索，我发现在 2009 年有一位作者在美国数学协会网站上发表了一篇题为Puzzling Over Exact Cover Problems的文章，其中描述了一种和”智慧大作战”非常相似的游戏的原理与解法。简单来说，我们可以把这个游戏转化成一种名为exact cover problem的数学问题(中文通常翻译为“精确覆盖问题”)，然后再使用Donald Knuth提出的一种名为“舞蹈链”的算法加以解决。事实上，另外一些有趣的益智游戏如数独、索马立方体(soma cube)都可以转化成为精确覆盖问题，并且用相同的算法加以解决。所以虽然智慧大作战与数独两个游戏表面上看起来毫无关系，但站在数学的角度上，他们实际上是同一个游戏。

上面提到的美国数学协会网站上的文章只描述了游戏背后的原理和解决的大致思路，但是没有给出任何具体的实现，所以我们没法直接用他的方法来解决我们的问题，好在已经知道了背后的原理，自己从头实现求解器应该不会太难，需要解决的问题主要有三个：一是如何将智慧大作战这类游戏转化为一个精确覆盖问题，应该使用何种数据结构来表示？二是如何实现舞蹈链算法，以及如何用它来求解精确覆盖问题？三是如何创造一个简单易用的用户界面，以使得为父和神兽在玩游戏遇到困难时，能够参考这个求解器找到答案？

经过几天爆肝，在阅读了众多文章、编写了无数 BUG 、耗费了电脑数十小时算力后，终于实现了一个颇为堪用的求解器。求解器使用 python 实现了舞蹈链算法，可以用来解决一般化的精确覆盖问题；求解器也实现了多个类，可以用来表示不同形状、大小的游戏盒以及不同的拼图形状；求解器使用 excel 作为前端，通过 xlwings 实现 python 与 excel 的互动，从而为求解器提供了一个简单易用的用户界面，如下所示：

几天的爆肝经历让我觉得有必要记录一下探索的过程，下面的文章首先会简单介绍了一下精确覆盖问题和舞蹈链算法的相关知识，这是我们求解器的理论基础，这一部分数学味可能比较浓，不感兴趣的读者可以跳过；第二部分则会介绍如何将智慧大作战这类的游戏转化为一个精确覆盖问题，通过分析不同组件的旋转与翻转对称情况来构建精确覆盖矩阵。第三部分则把分析进行了扩展，不仅限于智慧大作战这一个游戏，而是会考虑不同大小、形状、摆放方式的游戏盒，以及不同形状的组件，尤其会重点研究五格骨牌(也称五连方)，也给出了一些探索的结果。第四部分简单介绍了如何安装和使用这个求解器。第五部分是结语。

突然发现 V 站无法显示数学公式，有兴趣的可以点击下面链接查看原文和代码：

电脑端： https://metaquant.org/exact-cover-problem-math-game.html

手机端： https://mp.weixin.qq.com/s/34PnJaT90jde9ilsjMaLGA

github 仓库： https://github.com/sorrowise/polyomino-solver

[Pipecraft]

厉害！这款游戏很好玩。家里有两个，一个正方形，一个三角形的。三角形的还可以拼成立体金字塔形。

[wjploop]

佩服楼主有耐心配娃做这样的事，很费时间精力啊。

我猜，你家娃知道老爸有”破解“方法后，可能对玩该游戏本身就失去兴趣了，会好奇如何破解的。不过，这得看娃年纪大点才会这么想，年纪太小就只会想到老爸有答案。

另外，谈下我对益智游戏得看法哈。

我觉得玩游戏的唯一目的是为了与人交流，无论哪种游戏的其吸引人的原因都是这样。小时候，一个人玩数独、扫雷等单机游戏时，其目的是在练习技术，为了下一次与小伙伴以较高低，间接交流；而玩象棋、算 24 这类多人游戏，属于直接交流。

可能我这类人太浅薄了，才会有这种看法，若有冒犯，请见谅。

[7gugu]

cooool ，解决方法慢慢看

[terence4444]

这个玩具长得有点……

[Mutoo]

我家有个星型的，说明书提供了所有的解法。不过我一般就暴力破解，杀时间。

[sillydaddy]

感谢分享，很有兴趣。

[metaquant]

@Pipecraft 感谢支持，这个游戏也还有第三种立体的玩法，本质上可以用相同的算法来解决，不过涉及到立体会稍微复杂一些。

[metaquant]

@sillydaddy 感谢支持！

[metaquant]

@Mutoo 感觉对人脑来说暴力破解更适用，毕竟不能指望人脑能有计算机的计算能力。

[metaquant]

@terence4444 放飞你想象的翅膀:smile:

[metaquant]

@wjploop 是的，我同意你的看法，游戏另外一个重要的侧面就是提供人与人之间交流的机会，对于孩子来说尤其如此。

[pheyer]

光看文字就觉得不简单了，就是这游戏好像不太适合年龄更小的孩子，LZ 能推荐一下给 2 岁小孩玩的耐玩玩具吗

[2i2Re2PLMaDnghL]

@pheyer （我记得这游戏本身就推荐 6+，主要是因为它有小部件吞咽窒息的风险）