图上的熄灯游戏

作者:杨超

本文地址:http://sokoban.ws/blog/?p=487

一、熄灯游戏

熄灯通常在n*n的格子上玩,每个格子是一盏灯,点击每个格子可以改变格子本身及其上下左右相邻格子的灯的状态。游戏要求把灯从全亮变到全部熄灭。关于熄灯游戏,老杰有一篇博文《熄灯游戏》对此作了非常好的介绍,他的网站还有网页版的熄灯游戏可以在线玩。对熄灯游戏不太熟悉的朋友可以在看老杰的博文之后再继续往下看。

二、推广

老杰的博文提到,对任意的n,初始状态为全亮的熄灯游戏都有解,即可以被全部熄灭。老杰的博文最后还提到熄灯游戏有六边形,3D等形式的推广。

更一般地,熄灯游戏可以推广到任意的图上面。这里所讲的图是若干个顶点和某些顶点对之间的连边构成。如下就是所谓的 Petersen 图,它由10个顶点和15条边构成。熄灯游戏的规则可以不作任何改变应用到一般图上,点击一个顶点,改变该顶点以及和该顶点直接相邻的顶点的状态。

图片来自 Wikipedia, CC-BY-SA协议

并且有趣的是,任意的一个图上以全亮为初始状态的熄灯游戏都有解。这个结论可以用线性代数和线性方程组的求解理论作出证明。但是这个证明需要系统地学习过线性代数才能比较好地理解,一般大学理工科的学生才会学习线性代数课程。下一节,我准备介绍一个纯粹的图论证明,这个证明由 Henrik Eriksson 等人2001年发表在《Advances of Applied Mathematics》杂志上,全文可以在 arXiv 下载。这个证明只用到了数学归纳法,有一定数学修养的高中生都完全有可能自己独立证明出来。这个证明简洁漂亮,很有可能被许多人独立地发现过。

三、证明

本节用数学归纳法证明:任意一个图上以全亮为初始状态的熄灯游戏有解。

对图的顶点个数 n 归纳。n=1 的时候显然有解。

下面进行归纳,假设对n-1个的点的图结论都成立,我们证明n个顶点的图G结论也成立。设这n个顶点的标号为1,2,…,n。为了用归纳假设,我们可以作这样的考虑,把标号为i的顶点删掉(当然这时和顶点i关联的那些边也同时删掉了),那么剩下的还是一个图,但只有n-1个顶点了。根据归纳假设,剩下的这个图是有解的,取定一个解称之为关于i的解,因为图是删掉顶点i得到的。

如果对某个i,关于i的解也是原来n个顶点的图G的解,那么结论对原图G也成立了。所以下面我们只需要考虑这样一种情况:对所有的顶点i,关于i的解都不是原图G的解。具体地说,每个关于i的解作用在原图G上的效果就是顶点i还亮着,其余的顶点都灭了。在这样一种情况下,我们下面分甲乙两种小情况考虑。

甲、n是偶数。此时我们可以把关于1的解,关于2的解,…直到关于n的解依次都在原图G上执行一次。我们分析一下执行的最终效果。对顶点i来说,关于i的解使得顶点i的状态保持不变,而其余n-1个解使顶点i改变状态。因为n是偶数,n-1是奇数,合成的效果就是顶点i的状态改变了奇数次,由亮变为灭了。每个顶点都是这样,所以这n个迭加在一起就是原图G的解了。

乙、n是奇数。这时刚才的方法不管用了,要另辟蹊径。我们取图G中一个度数为偶数的顶点,不妨设为顶点1。本段余下解释为何存在这样一个顶点,熟悉图论的朋友可以跳过直接看下一段。所谓顶点的度数,就是和这个顶点相邻的其它顶点的个数,也就是和这个顶点关联的边的条数,如前面的 Petersen 图每个顶点的度数都是3。一个图的所有顶点的度数加起来一定是偶数,这时因为在计算度数的时候,图的每一条边都会被两个不同的顶点计算了一次,共被计算了两次,于是所有顶点的度数和是边数的两倍,为偶数。还是以刚才的 Petersen 图为例,度数和为30,是边数15的两倍。因为我们的图G的顶点个数n是奇数,若所有顶点度数都是奇数,那么所有顶点的度数和是奇数个奇数相加,还是奇数,这不可能。

把上面取定的顶点1和它的全部邻点构成的集合称为A,那么A一共有奇数个顶点。其余的顶点全体是集合B,且B有偶数个顶点。对原图G,我们执行以下操作,点击一下顶点1,那么A中的点全灭了,B中的点任然保持亮着。之后再对B里面的每个顶点j,执行关于j的解。这里一共有偶数个解,所以A中的点改变状态偶数次,还是灭的状态;B中的点改变奇数次,也由亮变成灭了。于是我们得到原图G的解了。

四、小结

上述证明没有用什么高深的数学,非常简单。但是若是要找出一个具体的解法,还是用线性代数的方法或者结合其它技巧要快一些。老杰的博文提到有人给出 5000*5000 的熄灯问题的解。这相当于一个 2500 万个顶点的图。这是因为线性方程组求解是一个P问题(有多项式时间算法),从而熄灯问题也是一个P问题。P问题在计算复杂度理论里面可以认为是最简单的问题。我上一篇博文提到过推箱子求解是 PSPACE 完全问题,这在计算复杂度上至少比熄灯游戏的P问题高两个级别(中间还夹了一个NP问题)。计算复杂度增加了游戏的耐玩性。可能看到有些朋友十年如一日地玩推箱子游戏,参加本站举办的在线推箱子比赛的很多朋友就是如此。但是估计很难找到持续多年地玩(纯粹游戏意义上的玩)熄灯游戏的人。

此条目发表在 数学, 游戏 分类目录。将固定链接加入收藏夹。