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

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

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

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

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

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

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

于是，我们可以编程，穷举第一行所有可能的组合，逐一验证是否可以过关。我写了一个 Python 小脚本，使用这种方法算出了部分解答，比如下面的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 个之多。关于这个数列，这儿还有更多，看起来解的数目都是 2^x 的形式。

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

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

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

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