首先点灯游戏是什么？

点灯游戏是一个十分有趣的智力游戏,他的规则是这样的:有一行N行N列的灯,开始时全部是灭的,当你点击其中一盏灯是他的上下左右(若存在的话)状态全部改变,现在要求你在限定的时间内以最少地步数,将全部的灯点亮.
以某一盏灯为研究对象,显然,当此灯状态被改变奇数次后,灯被点亮.反之,被点击偶数次,灯则维持原来的熄灭状态不变.而促使灯状态改变的事件不外乎其上下左右(若存在的话)被点击.推而广之,只要所有的灯状态被改变奇数次,则可保证所有的灯全部被点亮.同时,应该,说明的是,对每一盏灯来说,自身被点次奇数数与一次效果相同,这是因为,对每盏灯来说,被点一次后,再点偶数次,自身他的上下左右(若存在的话)状态恢复原态.同样道理,自身被点偶数次,相当于没被点.故在最少步数的限制下,每盏灯要么没被点,要么仅被点一次。

关于点灯游戏和“二维码”知乎上的用户曾加是这样解答的：

在8年前，还是个初三的孩子时，我曾经探索过这个问题。当时用文曲星的 GVBASIC 计算到n=14，也得到一些漂亮的结果，但因为文曲星性能所限，没有继续算下去。

8年之后，偶然的机会让我重新发现了这个被遗弃的问题，突然感到很怀旧。

于是用Java编程，重温了这个问题。

8年前，曾做过游戏技巧的总结：

（1） 显然，点灯游戏的解，和点下方格的次序无关，仅和点下方格的位置有关。

（2） 在一个方格下累计点下两次，和没有点下过的效果是一样的。所以xx解必然只是在某些格子下点下过一次。

（3） 当第1行被点下的格子确定时，若存在方案，则方案xx。

这是因为一个格子（坐标[a,b]）的灯是否点亮只和其初始状态以及以下五个点：

[a-1,b][a,b-1][a,b][a,b+1][a+1,b]是否被点下有关，其中只有[a+1,b]是位于第a+1行，其它均在第a行之前。

举例说明：如下图所示

5×5的方格，假设紫色格一开始是暗的，我的目标是把它点亮，而前两行点下的位置已经确定（如图中的1），那么由于紫色格的状态只与自身以及周围4个点被按下次数有关（总和应是奇数），而绿格和紫格累计被按下2次，所以在第3行，红色格必须被按下。所以，当固定了第一行的点灯位置，那么，剩下的步骤是确定的，点完第n行可以让第n-1行的灯全亮，所以，我可以确保除xx一行外，所有位置的灯都能点亮，而xx一行是否恰好都被点亮，则要看天意。但是在n较小的情况下，暴力求解并不麻烦。

（4） 如果初始亮灯位置是随机的话，就没有确定的解，甚至不一定有解，只能按照上面（3）的方法逐个尝试。但是如果初始状态是全部灯暗，是可以通过穷举找到确定方案的。

比如，5×5共有4个解，如果考虑对称性和旋转性，此解是xx的。

下面是5×5的方案，可以看到，它在斜对角线有一条对称轴：

游戏的技巧大致就这些，但游戏的内涵却远不止于此。

这个问题其实并不容易。即使用计算机算，考虑到之前所说的技巧，只需要确定第一行点下的灯，在目前的算法下，复杂度达到了
，随着n的增大，复杂度指数增长，所以能算得的n也并不是太大，当n达到30的时候，一次全遍历的计算就要花上大约3个小时。

于是得到了n=1-30的解：

这张表格里有很多耐人寻味的规律：

1、 是否对于每个n，都存在解？

2、 若都存在解，是否解的个数（蓝色数字）必是4的整数次幂？

3、 对于每个n，它的每个解的步数是否总是和n同奇同偶？

这些规律或许已经有证明，或许还没有，或者存在反例，但是发现规律本身就足够令人兴奋了。

如果仅仅是那些数据，也许还看不到它的美妙，那就上图吧，看看玩n×n的“点灯游戏”，到底需要点击哪些位置的点。

————沧海桑田的8年————

（8年后，那时看不到的美丽，在Java中展现无遗）

多么美妙的图形！！！

点灯游戏和“二维码”你看懂了么？
你有更优的算法吗？
敢不敢来挑战，看看你能算出怎样美丽的“二维码”。

更多关于点灯游戏，请点击【阅读原文】