精确覆盖下的数学游戏

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

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

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

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

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

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

一、精确覆盖问题

精确覆盖问题的严格数学定义是：假设一个全集\(X\)中若干子集的集合为\(S\)，如果\(S\)的子集\(S^*\)满足\(X\)中的每一个元素在\(S^*\)中恰好出现一次，那么集合\(S^*\)就是\(X\)的精确覆盖。简单来说，就是要找集合\(X\)的一系列子集，使得这些子集两两之间不相交，并且这些子集的并集恰好等于集合\(X\)。上面的定义可能有些难以理解，可以看一个具体的例子：假如有一个集合\(X=\{1, 2, 3, 4, 5, 6, 7\}\)，它有一系列的子集如下：

• \(A=\{1,4,7\}\)
• \(B=\{1,4\}\)
• \(C=\{4,5,7\}\)
• \(D=\{3,5,6\}\)
• \(E=\{2,3,6,7\}\)
• \(F=\{2,7\}\)

求解精确覆盖问题就是要在这些子集中找到一系列集合，使得它们之间两两不相交同时它们的并集要等于原集合\(X\)。经过简单的尝试，我们可以发现集合\(S^*=\{B,D,F\}\)满足条件，所以集合\(S^*\)就是集合\(X\)一个精确覆盖。这里的例子因为很简单，所以我们只需要简单尝试一下就能够找到答案，但是如果问题更为复杂一些，我们就很难简单尝试出答案。事实上，我们可以尝试的方案数是随着子集数的增加而指数增长的，假设子集总数为\(n\)，则我们需要尝试的次数则为\(2^n\)，则对于上面例子中的问题，我们需要暴力尝试的次数为\(2^6=64\)次。然而，对于智慧大作战游戏，总的可选择数达到了\(2140\)种，如果我们每次尝试时任意选出十二种组合方式，则总的选择数为：

这个天文数字共有32位，假设我们每一毫秒尝试一种方案，那么我们总共需要约\(5.92\times10^{20}\)年才能尝试完所有方案，这显然不是一个我们可以接受的时间，我们需要一种更为高效的算法。

对于精确覆盖问题，除开上面集合形式的表示方法以外，我们还可以用矩阵的形式来表示，比如上面的例子我们可以表示成如下矩阵的形式：

这里矩阵中的行标题为所有的待选子集，可以理解为我们可做的选择；列标题为所有的元素，可理解为我们做选择时的限制条件。以行为单位看，可以看到每个子集包含的元素，也就是单元格为一的元素，比如集合\(A\)就包含元素1,4,7；以列为单位看，可以看到每个元素包含在那些集合中，比如数字一就包含在集合\(A\)与集合\(B\)中。通过这种转化，我们求解精确覆盖问题就变成在这个矩阵中找到一系列的行，使得这些行对应的每一列都只有一个数字一，也就是表格中标红的\(B,D,F\)三行。

把需要求解的精确覆盖问题用矩阵形式表示出来后，我们还需要一个高效的算法对这个矩阵进行处理，只保留那些满足条件的行，最终得到一个较小的矩阵。拜高德纳大神所赐，我们有了这样一个算法，高德纳把它称为Algorithm X，有时候也叫做dancing links algorithm，这主要是因为这个算法用到一个专门的数据结构dancing links，中文有时称做舞蹈链或者跳舞链。从上面举的那个简单例子我们可以看出，求解精确覆盖问题实际上就是对这个矩阵的行与列进行处理，因为精确覆盖问题对应的表示矩阵一般是一个规模较大的稀疏矩阵，值为零的元素远远多于值为一的元素，所以直接对矩阵的行与列进行删除与重新插入操作就非常的低效，而使用dancing links这种数据结构则可以显著提高这些操作的效率。算法的原理与数据结构的细节我就不详细介绍了，大家可以参考前面提到的美国数学协会网站上的文章，里面有非常详细直观的解释，学有余力者也可以直接去看高大神的论文原文。

虽然我们已经有了一个高效的算法，但仍需要一个高效的实现。经过一番搜索，我发现又一位大神使用python实现了舞蹈链算法，整个实现的代码行数只有约三十行，而且没有使用任何外部库，只使用了python原生的字典这种数据结构。经过测试，这个实现的效率也非常高，求解每个游戏问题的时间通常只需几百毫秒。所以我们现在的问题只剩下如何把智慧大作战游戏转化成一个精确覆盖问题，然后使用舞蹈链算法来求解，下一节我们来解决这个问题。

二、问题的转化

为了将智慧大作战游戏转化成一个精确覆盖问题，我们需要找到所有的待选子集及对应的限制条件，也就是矩阵中的行标题与列标题。首先来看比较容易处理的部分，也就是列标题。我们知道智慧大作战中总共有十二个组件，而游戏盒总共有五十五个位置可以用来放置这些形状。因为每个组件只有一个，这对应十二个限制条件；而每个空位也只能放置一个组件，所以有55个限制条件，因此总共有\(12+55=67\)个限制条件。对于组件的限制条件，我们可以使用不同字母来代表不同的组件，不妨直接使用游戏手册中给出的命名：

十二个组件分别对应\(A-L\)十二个字母，而对于游戏盒上的空位，则可以使用二维坐标来表示，如游戏盒上第一行第一列的空位，对应的坐标就是\((1,1)\)，其它位置依次类推。

对于行标题也就是待选子集的情况，一个显然的事实是，不同组件因为形状不同，可以在游戏盒中放置的位置也会不同，我们可以看一个简单的情况，比如对于一个四乘四的游戏盒，总共有十六个位置，如果我们用最简单的组件也就是组件I去放置，它可以放在哪些位置？

显然对于一个四乘四的游戏盒，组件I的可以放置的位置有九种，而在五乘十一的游戏盒中，可能的放置方式共有四十种。然而，上面列出的并不是所有可能的放置方式，我们还需要考虑组件的旋转与翻转，比如对于组件A来说，它可以每次逆时针旋转九十度，产生四种不同的变种，同时每一个变种又可以翻转一次，各产生一个变种，所以组件A经过旋转与翻转共可以产生八个不同的形状，如下：

这些形状里我们可以定义一个基础形状，而把其它形状都看作是基础形状的旋转与翻转变形。每个形状用一个长度为三的字符串表示，第一个字符表示这个形状属于那个组件，比如上面的形状都属于组件A，因此第一个字符都为A；第二个字符表示这个形状在基础形状上经过了几次旋转，如A30就表示这个形状是在基础形状上顺时针旋转三个\(90^\circ\)也就是\(270^\circ\)得到的；第三个字符表示这个形状是否经过了翻转，比如A31就表示这个形状是在A30形状上翻转得到的。

因此，对于每个组件，我们除了要考察它基础形状的放置位置外，还要考虑它的变种的放置位置，如对于组件A，在一个五乘十一的游戏盒中，可能的放置位置共有208种。因此为了列出每个组件可能的放置位置，我们需要考察它所有可能的变种，即通过旋转和翻转总共可以产生多少个不同的形状。这是一个复习几何图形对称知识的好时机，也许还可以和家中神兽一起来完成。下面我直接列出结果：

有了行标题与列标题，我们就可以开始构建精确覆盖矩阵了，这个矩阵有2140行及67列，截取部分如下：

有了精确覆盖矩阵，我们就可以调用之前介绍过的求解器来进行求解了，我们可以调用python中相关的可视化库来对结果进行可视化，如下：

对着上面的可视化结果，我们就可以成功拼出一个答案了。需要注意的是，当游戏盒上没有放置任何组件时，可行解的数量很多，虽然我的电脑运行了三个多小时，也没有能够找到全部可行解。但好在我们更加关心的问题是，如果已经在游戏盒上放置了一些组件，那么对应的答案是什么？我们可以使用游戏随附的手册中的例子，不妨就以其中最难的第六十四题为例：

第六十四题中共放置了两块组件，即组件A与组件J。因为已经放置的组件只有两个，所以这道题的难度是非常高的，如果手工尝试通常会花费很多的时间，但使用我们的求解器则可以很快找到答案(效果见文章开头的动图)。有了这个求解器，我们还可以不受游戏手册的限制，自己尝试摆出一些组件，然后用求解器查看某种摆法是否有解。

至此，我们已介绍完求解器的基本原理，但是这个求解器只适用于这个游戏特定形状、大小的组件与游戏盒，下面我们将对这个求解器进行扩展，使得它可以适用于不同大小、不同形状的组件与游戏盒。

三、扩展的求解器

首先我们来考虑不同形状的游戏盒，然后我们再来考虑不同形状的组件。实际上我上面提到的smartgames的这款游戏还提供了一种玩法如下图：

表面上看这里的游戏盒不再是一个正规的矩形，但是实际我们只需要把游戏盒顺时针旋转四十五度，就会发现它仍然是一个矩形，只是这个矩阵是残缺的，有些位置无法再放置组件了。如上面第120题中迷题就可以通过旋转变成下面的形状：

显然这是一个九乘九的矩形，总共有八十一个位置，同时矩形右上和左下各有十二个位置空缺，左上和右下各有一个位置空缺，因此总共有二十六个位置空缺，使得这个形状总共可以放置组件的位置数为\(81-26=55\)个，正是十二个组件可以占据的位置。求解器得到的结果如下图，我们只需要把这个形状再逆时针旋转四十五度，就可以对照图形拼出我们的答案了。

根据上面的原理，在求解不同形状的游戏盒时，我们可以把它们转化为某种矩形，然后去除一些不需要的位置即可。具体求解时，我们会先构建出一个完整的矩形，然后用特定的字符表示那些需要去除的位置，再调用一般的求解器求解。

除开不同形状的游戏盒以外，还可能有不同形状的组件。实际上smartgames这个游戏中的组件是从一种称做五格骨牌的游戏变化而来的，五格骨牌的谜题，最早是英国人亨利·杜德耐于1907年所发明，比smartgames的这个游戏要早得多。传统的五格骨牌共有十二个，它们的形状以及相应的命名如下：

这里面有些形状和智慧大作战游戏是重合的，如果形状F就是智慧大作战中的组件B，形状L对应组件C；有些组件则是修改过的，如智慧大作战中的组件I是五格骨牌中的组件V去掉两个正方形，组件K则是五格骨牌中的组件T去掉一个正方形。容易发现，五格骨牌中十二个形状每个均由五个正方形组成，总共由六十个正方形组成，因此可以填满一个由六十个正方形组成的矩形，这个矩形可以是\(6\times10,5\times12,4\times15,3\times20\)这四种形状。当然，我们也可从矩形中去除一些位置，比如我们可以从一个八乘八的大正方形中去除四个位置，留下六十个位置。

使用五格骨牌来拼成一个特定的形状的研究很早就有人做了，实际上早在1958年，图灵奖得主达纳·斯科特就求出了八乘八正方形中去除最中心四个位置的游戏盒有多少种解法了，他得到的结果是共有520个解，但是因为这个游戏盒是中心对称以及轴对称的，所有可以共有八个变形，因此如果不考虑游戏盒本身的旋转或翻转的话，则唯一解共有\(520/8=65\)种，其中一些可行解可参见下图：

斯科特的求解方式实际上是回溯法计算机程序的早期应用之一，之后其它人用类似的程序求解了上面提到的四种不同形状的矩形对应的精确覆盖矩阵的维度以及解的个数，具体结果如下：

四、安装与使用

因为我使用用户界面的目的只是为了方便自己测试，并不想在前端界面上花费太多时间，所以我直接使用了excel这个现成的用户界面来作为我的求解器的前端(这主要是因为在excel画格子比较方便)，然后使用xlwings库来实现excel与python之间的互动，我编写了一些必要VBA代码来实现一些控件的功能，最后形成的用户界面虽然简陋但也够用。

名称为board.xlsm的文件里有两个工作表，第一个工作表是五格骨牌对应的求解界面，最上方展示了十二种五格骨牌的形状和对应的名称，然后下面列出了五种常见的五格骨牌游戏盒形状，使用时我们只需要在左侧的游戏盒中填入组件对应的字母代号与占据的位置，然后点击solve就可以在右侧显示对应的解答。需要注意的是，某些迷题可能会有多个答案(特别是已放置的组件比较少时)，碍于excel界面的限制，这里只会显示出一个答案。如果想得到全部答案，则需要调用我实现的求解器中的相应代码。第二个工作表则是智慧大作战游戏对应的求解界面，左上角是组件的形状及名称，右侧是普通的矩形游戏盒的求解界面，下方是旋转四十五度的矩形的求解器。其它的部分和五格骨牌的求解界面相似，不再赘述。

在使用前，需要用户安装了一些常用的第三方库，如numpy, matplotlib, seaborn等等，最简单的方法是直接安装anaconda发行包，其中也直接附带了xlwings库，无需再重复安装。相关代码与excel文件已上传github仓库，感兴趣可点击链接查看。

五、结语

当我在网上搜索与我们今天解决的问题相关的文章，偶然遇到了一篇文章让我感触颇深，文章的作者在文中讲述了它为什么会对五格骨牌的问题感兴趣：

我现已退休的父亲曾是一名全职牧师，同时也是一名黑客。他对编写 Forth 编译器和低级图形库等“极客”事物的热情让我在 十四岁左右就爱上了编程……多年来，父亲编写了各种版本的程序，以找到五格骨牌难题的所有答案……基于我父亲多年来编写和不断改进的 Forth 语言的五格骨牌求解器，我用python实现了一个新的版本……

我想这篇文章之所以让我有所感触的原因，并不仅仅在于父子两人多年来共同追求一个更高效率的五格骨牌的求解器，更是因为它展现了一位“极客”父亲对孩子的潜移默化的影响，展现了一位对世界抱有单纯好奇心与求知热情的父亲，如何把这种好奇心和热情传递给自己的孩子。这种热情与好奇心的传递，可能比知识本身的传递更为重要。我想很多时候，我们需要小心呵护孩子对这个世界的纯真好奇，努力成为他求知路途上的同行者，陪伴他跨越“无效内卷”与“功利化知识”的沼泽，在成长过程中不丢失那颗求知的初心。

是为记。

六、参考

1. Algorithm X in 30 lines!
2. Efficient Algorithm for Enumerating All Solutions to an Exact Cover Problem
3. Fast pentomino puzzle solver ported from Forth to Python
4. Knuth, Donald E. "Dancing links." arXiv preprint cs/0011047 (2000).
5. Puzzling Over Exact Cover Problems
6. Wikipedia contributors. "Exact cover." Wikipedia, The Free Encyclopedia.
7. Wikipedia contributors. "Pentomino." Wikipedia, The Free Encyclopedia.