熄灯游戏

熄灯游戏(Lights Out)是一个规则很简单的游戏,在一个 n * n 个格子的面板上,每个格子中有一个灯,灯有亮着和熄灭两种状态,初始状态下,所有的灯都是亮着的,点击某一个格子,会影响到那个格子以及它上、下、左、右四个相邻格子中的灯的状态,影响的规则为如果灯原来亮着则将其熄灭,如果原来熄灭则将其打开。游戏的目标是要将面板上所有的灯全部熄灭。如下图所示。

Lights out
(图片来自:http://en.wikipedia.org/wiki/File:LightsOutIllustration.svg)

你也可以尝试一下我写的网页版熄灯游戏

这个游戏的规则很简单,但如果不思考一下可能也不容易很快找到解,尤其当 n 比较大时。

简单来说,这个游戏有两个比较明显的诀窍:

  1. 点击的先后顺序对最终结果没有影响。比如 5*5 的面板中,如果把格子以 #1 ~ #25 依次编号,那么按 #3、#8、#14 的顺序点击和按 #14、#8、#3 的顺序点击结果是一样的。
  2. 每个格子至多只需被点击一次。因为点击两次的效果和一次也不点击的效果是一样的,并且有第一条做保证,即使两次点击之间隔了很多次其它的点击,效果和这两次点击连在一起是一样的。

有了这两条规则,就能有一个解题策略:对一个 n * n 的面板,我们从第一行开始逐行点击,每一个格子至多只点一次。除第一行外,每一行的任务是把上一行没有关闭的灯关闭(在上一行亮着的灯下方的格子点一次,这样就可以把上一行对应格子的灯熄灭,并且不会在上一行打开新的灯),直到点完最后一行。如果最后一行的灯全部熄灭了,说明过关了,否则过关失败。

也就是说,我们只需要确定第一行的点法,接下来 n - 1 行的点法就都确定了,是否能过关也就确定了。

于是,我们可以编程,穷举第一行所有可能的组合,逐一验证是否可以过关。我写了一个 Python 小脚本,使用这种方法算出了部分解答,比如下面的20 * 20 面板的解答。

20 * 20

比较有趣的是随着面板不断增大,解的数目的变化。根据上面脚本的计算结果,n 从 1 增加到 20 时,解的数目依次为:

1, 1, 1, 16, 4, 1, 1, 1, 256, 1, 64, 1, 1, 16, 1, 256, 4, 1, 65536, 1

这个数列的变化似乎没有特别的规律,比如 18 * 18 的面板只 1 个解,但 19 * 19 的面板的解却突然有 65536 个之多。关于这个数列,这儿还有更多,看起来解的数目都是 2x 的形式。

另外,这篇文章也提到,对于任意初始状态灯全部亮着的方形(n * n)面板,总是有解的。

但这个穷举的算法复杂度非常高,对于一个 n * n 的面板来说,第一行有 2n 种组合,这是一个可怕的指数函数,比如对于 n = 50 的面板,需要验证 250 = 1125899906842624 种可能的组合,如果电脑每秒能验证一千万种组合(这已经很难达到了),也需要三年半才能完成。何况这还仅仅是 n = 50 ...

所以,要求更大的面板的解,就需要其它更加高效的方法。网上看到有一位老外用线性代数的方法求出了 400 * 400 的面板的解,他还将 n <= 200 的解做成了一段很酷的小动画,也在这个页面上。后来这位老外又用一种更快的算法,找出了惊人的 5000 * 5000 面板的解,画成图像后是这样的,一个像素代表一个格子,白色代表点击,黑色代表不要点击。

熄灯游戏看似简单,但一旦规模变大之后求解方法也会急剧复杂。另外,面板不一定必须是正方形的,可以是方形、三角形等,还有人制作了六边形版本,甚至3D版本(不知道还有没有 4D版)。

分类:编程标签:数学趣题

相关文章:

评论:

freerabit

能不能证明所有的解都有轴对称且中心对称,这样的话,它的第一行与第一列就具有了一定的绑定关系,说不定可以大大缩小计算范围

oldj

似乎不是所有的解都轴对称,比如 http://oldj.net/static/lights-out/solutions.html 这儿的 9x9 的解 #1 就是旋转对称,9x9 的解 #16 则没有明显的对称模式...

freerabit

这样算会不会有啥好的思路:先计算如果第一行没有元素被按下,那么通过你的迭代计算到最后一行有哪些元素无法被关闭。这个不妨叫做第0个数列。它的长度为N。再计算第一行第一个元素被按下,其他都不按,那么迭代后最后一行有哪些元素无法被关闭。这个数列长度为N,它和第0个数列的异或,就是第一个元素的影响。再计算第一行第二个元素被按下,其他都不按,那么迭代后最后一行有哪些元素无法被关闭。这个数列长度为N,它和第0个数列的异或,就是第二个元素的影响。以此类推。直到第N个元素试验完毕。现在所有N个元素分别产生了一个影响,是长度为N的数列。总共N个元素因此,可构成一个N阶方阵。现在的问题就转化为了以2为模的整数环上的N阶矩阵方程的问题。要求一个长度为N的行矩阵,使它乘上刚才那个N阶方阵以后,等于之前的第0个数列。

freerabit

看来解的数目决定于那个N阶方阵的秩缺少多少。

BlackGlory

请问彩色熄灯可能有解吗?例如这个http://weblab.sinaapp.com

oldj

不知道呢,你看看 http://sokoban.ws/blog/?p=487 这篇文章有没有帮助呢?

BlackGlory

我看看,先谢谢了:)

发表评论: