游戏背后的数学 Vol. 1 WayOut

本文力图以最通俗易懂的语言，讲清游戏背后的数学。如果你没有看懂，说明我讲得不够好，欢迎一起探讨问题。

我上高一时，听过一个段子：有人问法国四年级小学生：3+4等于几？答：不知道。问：那4+3等于几呢？答：不知道。问：那你小学都学了什么呀？答：我知道3+4=4+3。问：为什么呀？答：因为整数关于加法构成一个交换群。

这使我意识到了三件事：

1.数学是Universal Language。无论是 3+4=7， III+IV=VII，还是{{-{}}:{{{，说的都是同一件事，真理是存在的。就3+4=7而言，请参考Peano公理系统。

2.我要学数学。

3.交换性／对称性是好东西。为什么古人觉得地球是平的呢？因为他们理所当然地认为自己所处的空间具有对称性——先往北走100米再往东走100米，等同于先往东走100米再往北走100米。实则不然，以后讲到HyperRogue时会详细探讨这一点。

正文

WayOut 是一个按灯的游戏，每按一盏灯会改变它及周围所有灯的状态，目标是把所有灯关掉。 它的原型是Lights Out，一款由Tiger Electronics发行的“掌上游戏机”。5*5的灯阵，总共有8388608个不同谜题，保证每次玩的都不一样！8388608=2²³，好像暴露了什么。交换性体现在哪呢？按灯的先后顺序不会影响最后的结果，所以问题归结于“按哪些灯”而不是“如何操作”。做视频／GIF攻略的朋友辛苦了，但吃力不一定讨好，我觉得图片攻略更简明易懂。

如果有n盏灯，则总共有2ⁿ种按法，它们构成F₂上的n维线性空间。和我们熟知的线性空间类似，只不过其系数取自有限域F₂={0, 1}，其中0+0=0，0+1=1，1+1=0，etc。（可以理解为偶+偶=偶、奇+奇=偶，但一个域除了有加法结构还有乘法结构）

举个栗子，如图有A, B, C, D四盏灯。

2A = 0，即：连按两次A等于什么也没做。

(A+B) + (A+C) = B+C，即：按A和B，再按A和C等同于按B和C，因为A按了两次。

注意到：按A改变了A, B, C的状态，按B改变了A, B, D的状态，etc。因此左边的问题转化为解线性方程组。当然，是在F₂上。解得x = (1, 1, 0, 0)——A与B各按一次即可。（注意：1+1=0)

接下来我们以Lights Out的5*5灯阵为例，探讨如何找到所有解。

如何找到一组解？

线性方程组怎么解？高斯消元法！这种活儿还是交给计算机吧。

我们用高斯消元法的思想，从另一个角度解决这个问题。

Chase The Lights，顾名思义，是通过一系列操作把所有灯聚集到底边上，其实就是把复杂的局面进行等价简化。（某盏灯亮着，则按其下方的灯，如此反复）Chase The Lights的按法是唯一的，而且没有用到最上方的五盏灯。

现在我们需要知道，最上方的五盏灯通过Chase The Lights会得到什么结果。

至此，问题已被简化为如下问题（在C.T.L等价意义下）：

注意：D=B+C，E=A+C。

因此，A, B, C, D, E总共能表示出2³种不同情形——0, A, B, C, A+B, A+C, B+C, A+B+C。不难看出，右边的情形正是A+B+C。

回到原题，我们只需按下A, B和C，再利用C.T.L即可得到一组解。（因为它经C.T.L得到的图案与A+B+C经C.T.L得到的图案相同，二者抵消。）

由C.T.L方法的唯一性，5*5灯阵总共有2²³种图案有解——因为C.T.L有2²⁰种方法，C.T.L之后有2³种可能。等下从另一个角度印证这一点。 （总数必然是2的幂，因为F₂上n维线性空间有2ⁿ个元素）

如何找到所有解？

两组解之间差了什么？“Nothing！！”

Literally nothing——按了这些灯之后，并不会改变任何灯的状态，我们称之为“Quiet Move”。任两组解之间之差一组“Quiet Move”；反之，任一组解可由某一组解加一组“Quiet Move”得到。鉴于之前已经得到了一组解，因此我们只需找到所有Q.M即可。

一个想法是，先随意给定最上面一行的情况，再根据每盏灯的状态被改变了偶数次逐行往下推，直至导出矛盾或得到一组Q.M。缺点很明显，总共要检验2⁵种情形，费时费力。

但仔细一想，逐行往下推导，相当于在进行C.T.L。因此上面这种做法的实质是：对灯进行C.T.L，只有当最后得到空白行时才对应一组Q.M。

并非空白行

这就好办了，利用我们之前得到的结果，可以得到：0=0，A+C+E=0，B+C+D=0，A+B+D+E=0，每一组解与一组Q.M一一对应。实际上，(A+C+E)+(B+C+D)=A+B+D+E，它们构成一个线性子空间。

0当然对应的是“什么也不做的”Q.M

A+B+D+E对应的是Q.M如下，注意第一行就是A, B, D, E哦～

A+B+D+E

A+C+E

B+C+D

因此，一个图案只要有解，就恰好有4组解。按灯的方法有2²⁵种，每一种按法都是某一个图案的解，因此恰有2²³种图案有解。

看攻略确实能知道最优解，但你能知道所有解吗？

回到WayOut本身

现在，任给Lights Out的8388608个谜题中的任何一个，我们都能快速求解。WayOut保留其核心内容，在此基础上加入了很多新机制。同时，交换性限制了游戏的深度，再多的新机制和“复杂”的关卡都没法从本质改变这一点。

首先是不拘泥于5*5的灯阵。

存在（非平凡）Q.M是一件很稀奇的事！如果没有Q.M的话，任意图案均有解，而且解还唯一！（如果有n盏灯，则共有2ⁿ种图案和2ⁿ种按法。没有Q.M意味着任两种按法得到的图案不同，因此任意图案存在唯一解。）

因此，首要目标是找到一组解——如果没有Q.M的话，它就是唯一的解，即最优解。C.T.L是我们的利器，与其说它是一种方法技巧，倒不如说是一种思维习惯。

检验一下自己，上面四关能不能口算出答案？这方面的能力对解决复杂问题至关重要，与其乱点一通，倒不如静下来想一想，对局部模拟各种按法得到的结果。

以这一关为例，左上角怎么处理？

左下角呢？

抑或是这样？（与左上角第二种解法结合看）

再对右上角、右下角作同样讨论，统筹一下就能解出来了。

再看一个例子，这个非常具有代表性，因为经过C.T.L之后，有时会剩下零星几盏灯没灭掉。有个小技巧——按一盏灯及其周围所有灯，在地图边缘效果更显著。

特别地，在这一关：将以下三者相加即可得到一组解。当然，这一关也有别的思路，比如说观察到它是轴对称的。

第一个新机制是带箭头的灯，按它只改变其自身和两侧灯的状态。有了这些，关卡反而变简单了，因为避免了C.T.L过程中牵一发而动全身的尴尬，不知道你能不能理解。看下面这三关是不是很简单？

再次强调一下口算的重要性。毕竟是人设计出来的关卡，总能捕捉到一些蛛丝马迹。

第二个新机制是带圆圈的灯，按周围的灯不会改变它的状态。也就是说，只有按它自身才能改变其状态，seriously？这太弱智了，一上来把这种灯全关了，之后当它们不存在即可。

第三个新机制是黄色的灯，一开始按不了，需要靠周围的灯激活。把亮的黄灯当成暗的普通灯，暗的黄灯当成亮的普通灯即可，甚至可以在一开始就把它们全部激活。如果要找最优解的话，先把它们当成普通灯找到最优解，然后注意按灯的顺序——在按一盏黄灯之前要激活它。如果最优解没有激活黄灯，比如说如下第一幅图，可以额外花两步激活它（旁边一盏灯连续点两次），这时得到的很有可能就是有黄灯情形下的最优解。

第四个新机制是带十字的灯，只要改变了它的状态就会附带改变其周围所有灯的状态，给人一种一发不可收拾的的错觉。玩到这里时，有些人绝望了，求助攻略也不知其所以然。其实原理非常简单，关键在于注意到：通过旁边一盏灯激活十字灯，只比直接按十字灯多改变至多三盏灯（这句话不严谨，理解意思就行了）二者求和能抵消很大一部分，而剩下的就是我们想要的。

按左下角的灯就变成这样了

感到脑在颤抖？且慢！

最后一个新机制是带圆点的灯，只要改变其中任意一个的状态，其他所有灯都会变成与之相同的状态。注意，这与“所有圆点灯一起改变状态”有些许差别，因为一开始时所有圆点灯的状态不一定全相同。只要改变了一盏圆点灯的状态，所有圆点灯就会变成相同的状态，从这时起所有圆点灯一起改变状态。交换性看似被打破了，但实际上只有“第一步”会影响大局——把所有圆点灯都打开／关闭将得到不同的结果，后面的操作都具有交换性。这里，“第一步”指的是首次改变圆点灯状态那一步。

怎么解呢？不要管圆点灯，目标是把其他所有灯都关掉。当然，不要忘了可以用圆点灯改变周围灯的状态。到最后，所有圆点灯状态相同——开／关。如果是后者，则问题已经解决；如果是前者，说明我们“第一步”按得不对，与后面某一步交换即可得到正解。（如果“第一步”将所有圆点灯打开，则换成将所有圆点灯关闭的一步，反之亦然）

结束语

之前有人问我解谜游戏为什么能那么快全成就，我一时竟答不上来。现在想，是因为我长期以来受到数学的熏陶，思维方式和一般人不一样吧。我突然动了一个念想，把自己玩解谜游戏时的想法写出来，同时解释其背后的数学原理。

但这谈何容易！数学已经融入到了我的思维习惯里，所谓“想法”有时只是潜意识里的捕风捉影，想给没有数学基础的人解释清楚其数学原理就更难了；同时，素材的选取也有一定困难，既要接地气还要有内容。

最近两个月实在是太忙了，进度只停留在构思的阶段，目前可写的内容积累了大概五六期吧。这几天一有时间，我就玩命把第一期写出来了，整体感觉比我预想的要好，希望你们能喜欢。如果有可能的话，我希望能一直写下去。

本来想把WayOut 2一并写进来，但考虑到篇幅以及没有本质上的新内容，最后还是没写。值得一提的是，WayOut 2有一关的设计让我拍案称奇。如果你能领略到其奥妙，说明你对本文内容已经完全理解了。当然，看不出来也很正常。

WayOut 2把tile换成了正六边形。现在回想起Hexcells、SquareCells、文明4、文明5、Endless Legend和XCOM，正方形与正六边形的tile平分了江山。牛关也有人就此问了一个问题，引发热议：https://cowlevel.net/question/1845202

那么问题就来了，这背后的有什么数学原理呢？存在别的的tile吗？将来我准备花两到三期的时间把这个问题彻底讲清楚，现在丢一张图就跑。

跑到一半突然发现有个问题还没问，有人知道牛关的字数统计是怎么算的吗？我这一篇统计出来有4000+，这明显不对啊。