【算法】从少女前线重装部队，到NP问题、精确覆盖和DLX算法

* 注：本文主要内容为 算法，属 计算机/软件/数学 领域，游戏内容仅为背景，请读者悉知

重装部队芯片拼接

《少女前线》游戏中，你拥有数支重装部队，每一个部队都有特殊的装备槽（重装回路），给她们配备装备（芯片）可以增加战斗属性。

不过给重装部队“穿装备”是件很麻烦的事情。重装部队的“装备”是形状各异的 俄罗斯方块 芯片，她们的“装备槽”是不同形状的插槽，插入插槽不允许重叠。芯片由1x1正方形小格组成，可以旋转90°、180°、270°，芯片每一格都带有属性加成，插槽塞的越满“套装效果”（同色谐振）越好，所以首先要做的就是把芯片插槽尽可能拼满！

于是乎玩家饶有兴致的拼起来了……一番折腾后发现终于拼满了，可是属性不好啊！换芯片又得重新拼别的形状……辣么多芯片，还得考虑多种属性组合最优……何时是个头啊！

量大的情况人力无法解决，我们就用计算机，就写代码！

问题抽象

为了让计算机帮我们解决运算问题，我们首先要把芯片和回路进行数学抽象。二维的回路我们可以从左往右、从上往下拉伸成一维数组。被芯片占据的地方记1，空的地方记0。我们以简单的九宫格示例：

什么都没放的回路必然是全为0数组，那么怎么将芯片放进去呢？不难发现，全满的回路其实就是将不同芯片单独放置在对应位置，再将数组按位置求和：

一个芯片，一种旋转角度，放在空回路的一个可行位置，我们将这个放置的回路数组称为放置行。所有芯片和回路的形状都是固定的，那么对于给定的一组芯片，我们先将所有芯片所有放置单元先求出来，以上图为例，只需要选出7个属于不同芯片的放置行，使其能够求和为全1矩阵就行了！

上述问题数学中称为“精确覆盖”

精确覆盖

在一个全集X中若干子集的集合为S，精确覆盖是指，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。

——百度百科《精确覆盖问题》

我们需要解决的问题是精确覆盖的特殊问题：零一精确覆盖，即全集X为全1矩阵，子集元素仅为0或1。通俗来讲，就是选出几个01行，对应位置相加刚好加出全为1的行。

零一精确覆盖问题是NP问题。

NP问题

即非确定性多项式（Nondeterministic Polynomially）问题，指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。

也就是说，芯片拼接问题处理时间会随着芯片数量增加而非多项式时间增加，这种增加趋势近乎于阶乘。

解决芯片拼接问题最简单的办法就是穷举法：把所有芯片所有放置方法都试一遍就行了！然而实际上，以6x6回路为例，对于形状限定在九宫格内的芯片，一共有36种放置方法（4x旋转3x横移3x竖移）。那么假设玩家有100个芯片，每7个芯片有可能组成回路，粗略估算有8,000,000,000,000,000,000种需要验证的组合！（电脑：我也遭不住啊！）

一般解决NP问题都会根据问题的特性，基于穷举进行优化，很多组合大类可以在很早就被否定掉，这种思路叫剪枝。以芯片拼接为例，假设前两个芯片已经出现重叠，那么后面的就不用试了。解决零一精确覆盖的高效算法之一，就是“舞蹈链算法”（Dancing Link X），简称DLX。

DLX

该算法剪枝思路是提前消除冲突行的试探回溯法，具体步骤：

1. 将所有01行合并为矩阵，创建一个栈S（栈Stack：数据结构，类似堆放椅子，从栈中取元素称为出栈，只能取最后放入的元素，即先入后出）

2. 选择一行为当前行，默认从当前矩阵第1行开始选

3. 检查当前行所有元素为1的对应列，我们称这些列为冲突列。除当前行外，其他行在该列元素如果为1，则必将与当前行冲突，称为冲突行。标记所有冲突行，并将当前行的行号入栈S

4. 删除当前行、冲突列和冲突行。如果：（a）当前矩阵0、1元素都包含，则返回第2步继续（b）当前矩阵为全1矩阵，算法结束，将所有剩余行的行号入栈（c）当前矩阵为全0矩阵，或者为空矩阵，则先前选择无法满足条件。回滚至约简前的矩阵，S出栈，并选择S出栈行号的下一行。如果已经是最后一行，那么继续回滚，直到能选择下一个当前行，或者退回初始矩阵

5. 如果：（a）退回到初始矩阵，且不能选择下一行，那么所给集合没有零一精确覆盖解（b）矩阵为全1，则S中的行号为满足零一精确覆盖的对应行号

我们看如下例子：我们从3个备选行 [1,0,1,1]、[0,1,0,1]、[1,0,1,0] 中求精确覆盖解。首先选取#1为当前行，1、3、4列被标记为冲突列，检查所有冲突列随后将2、3行标记为冲突行。将当前行行号#1入栈S，并删除当前行、冲突列和冲突行，发现矩阵为空，该次试探失败。于是回滚至上一次矩阵，将S出栈。出栈得到上次选取行号=1，则本次选取#2为当前行，2、4列被标记为冲突列，检查所有冲突列随后将1行标记为冲突行。将当前行行号#2入栈S，并删除当前行、冲突列和冲突行，发现矩阵为全1矩阵，剩余行号#3入栈，算法成功结束。故得到零一精确覆盖解为2、3行。

利用DLX求得全部图解

实际操作需要增加额外判断，行需要存储所属芯片序号，因为同一个芯片有很多放置行，但是一个芯片只能用一次。并且因为芯片和回路形状各异，部分重装可以空出一些格数依旧可以达到最高属性（M2迫击炮）。所以具体求图解的步骤为：

1. 将所有芯片形状的所有旋转角度，先以二维坐标表示，称为基本形状矩阵

2. 回路设为8x8的零行，针对不同形状，边界外部分初始化为1即可

3. 根据回路形状，输出所有形状芯片所有旋转的所有可能放置位置，用01行表示，这些01行的集合称为位置矩阵

4. 穷举可能的芯片格数组合（例如：36格回路，可能由6个六格，或者1个六格+6个五格拼成），并进行DLX，且每一步迭代不选取已经入栈的芯片编号。DLX结束条件更改为：必须执行固定次数迭代，且最后一步不为空矩阵即可（保证M2这种特殊情况能被正确计算）

5. 记录每一个DLX的解，这种解包含两条数据（a）放置行矩阵，即该图解中，每一块芯片的种类、旋转、放置位置（b）芯片数索引，表示每类芯片用了多少个。因为图解是固定的，所有图解保存为本地文件，运行芯片计算时直接通过查表得到图解，不需要再跑一遍DLX。放置行矩阵和芯片数索引详见下图：

DLX后续优化

1. DLX对冲突行的判断，可以将64位01串分成两个32位01串 *，并将32位01串直接按二进制存储为32位整形。判断“有没有同位为1”，本质等价于“两个32位整形按位求与≥0”（按位与：运算符&，两个二进制数按位求与，同为1的位数保留1，否则保留0）按位运算速度比逻辑判断快数百倍，在DLX成千亿级的比较中可极大幅度优化速度。 * 注：只所以8x8方阵的64位01穿要拆分成两半，因javascript默认支持32位整形

2. 计算最佳方案时，将芯片可能的组合列举出来，根据总属性（或增加筛选条件）进行排序，利用堆排序能加快速度

芯片计算器：https://hycdes.com/pages/GFT_ChipCal.html

代码（不包含DLX）：https://github.com/hycdes/GFTool

别搞这些花里胡哨的，啥时候能删除回路和芯片形状

这些设计不能带来任何新的游戏体验，只有麻烦和浪费时间