精确覆盖下的数学游戏

前期为了陪娃打发时间，入手了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