最近一头山羊火遍全网，关于第二关有多难，如何过关的文章层出不穷。但是，从计算复杂度的角度讨论游戏难度的文章还是应该发表的。这不，所以这次我也要写一篇计算复杂度来碰瓷的文章。游戏机制相对简单。简单来说，地图上有一些不同类型的方块。玩家可以选择方块放入自己的槽位（槽位有上限，是一个常数）。如果插槽中出现三个相同类型的方块，方块就会被消除，游戏的目标是消除所有方块。游戏的难点在于地图上的方块是堆叠在一起的，堆叠在下面的方块是无法选中的，只能在最上面的方块放入槽中后才能选中（也就是解锁），有时堆叠的最下面block的类型都因为被遮挡而未知。事实上，羊弹羊的机制和一些小游戏非常相似，其中很多已经被证明是NP-complete的，所以我们更有信心也可以证明推广的羊弹羊是NP-complete的。这里我们给出一个更弱和更简单的归约结构来说明广义的羊羊博弈是NP完全的。我们这里说的推广是指块类型的数量不限于一个常量，要阻塞的块类型是确定和已知的，槽数固定为3（槽数为其他常量，也可以使用类似的方法，只要在游戏开始时，强制玩家拿走一种特殊类型的方块，这种方块只能在游戏结束时被淘汰。在整个过程中，这个方块占用一个slot，相当于少了一个slot）。当然，这里我们不考虑游戏道具的影响。本文的归约主要是抄袭ComputationalComplexityofGamesandPuzzles网页来证明麻将游戏（一种类似于连连看的游戏，有的地方也叫麻将）是NP完全归约。我们仍然使用3-SAT的经典NP-complete问题作为归约问题。我们在3-SAT公式中为每个变量设置3个方堆，一个方堆用来模拟变量的赋值（TRUE或FALSE），一个方堆对应FALSE的赋值，一个方堆对应赋值真实的。模拟变量赋值块栈有两层，第一层包含4个与变量对应的相同块，第二层包含变量赋值为TRUE和FALSE的块和填充块各一个。FALSE赋值对应的块堆通常是多层的（也可能退化为一层），最上层包含两个块对应赋值为FALSE的变量（与之前的赋值块栈一起使用），下层层包含对应于子句框（对应于变量显示为NOT的子句）和填充框的块。对应于评估为TRUE的一堆块的结构是相似的。最后，有一堆块用于验证解决方案。这个堆是多层的，最上面是子句对应的块，中间是变量对应的块，最下面是子句对应的块。我们用一个具体的例子来描述这种减少，假设3-SAT的实例是。那么羊羊游戏的例子如下（为了表达每个方块的类型和堆叠情况，我们用侧视图来表示）其中C1代表，C2代表，a是填充方块，方格a不压住任何方格，所以可以保存到最后全部消除，不影响其他方格。注意我们这里设置的槽数是3，也就是说选择了某个方块放入槽后，必须消除该类型的方块，否则游戏无法继续。如果公式可满足，则满足时可根据各变量的赋值消去方块。比如假设xyz全赋值为FALSE，那么我们就应该对应的去掉最左边的三个xy和z。这样，第二层的方格x=Fy=F和z=F就会被解锁，我们可以消除所有x=Fy=Fz=F的方格，然后就是一个C1方格和两个C2方格解锁，然后可以将最下面的两层验证方块组合起来，消除上面的两层验证方块，然后中间的可变xyz方块也被解锁。马上就可以消除，最后没有限制，可以消除所有的方块。反之，如果可以消除所有的方块（即可以清除关卡），则可以满足公式。注意，如果要淘汰验证堆中变量xyz的块，必须先淘汰上面的C1和C2子句块，子句块受赋值块限制，赋值块受变量限制块，而变量块的摆动放置方式决定了在给变量赋值时，每个变量只能赋值FALSE或TRUE其中之一（具体来说，在开始的4个x块中随机剔除3个后游戏中，块x=F和x=T必须有一个未解锁）。这意味着消除块的顺序暗示??了满足公式的分配。也就是说，满足3-SAT公式的充要条件是对应的羊羊游戏实例可以通关。而绵羊和绵羊显然属于NP，因为可以在多项式时间内确定一个操作序列是否可以消除所有的方块，所以我们证明了以下命题：命题：条件所有被遮挡的方块类型是确定的且已知接下来，提升的羊羊博弈是NP-complete的。用非人类的话来说，你是没有办法设计一个多项式时间复杂度的算法来判断有没有办法提升羊羊等级的，除非P=NP（这个只有4个字符的等式就值个地奖了和100万美元，所以不要坐在那里试图证明或反驳它）。用人类的话来说，即使被遮挡的方块类型被确定并已知，计算机仍然（几乎）无法快速判断一只羊是否可以通过关卡。
