点灯游戏的解法讨论

noski

前两天在最少步版，有人问怎么下载点灯游戏，我就贴出了下面这个：
http://files2.17173.com/flash/4062.swf

这是一个10*10的点灯游戏，以前还在小游戏机上玩过5*5的，目的就是把方阵中的“灯”全部点亮。
规则是：点击一个小方格时，这个方格以及上下左右与之相邻的4个方格，灯的亮灭状态发生变化。
希望大家讨论讨论这类游戏的解法的数学规律：

1. 如果初始状态灯是全灭的：
对于n*n的方阵，有什么固定的解法吗？
对于m*n的方阵，它与m*m或n*n方阵有什么关系？

2. 如果初始状态灯是随机点亮的：
怎样才能以不变应万变？点灯的策略有什么变化？
有所谓的“最少步解法”和“最乱状态”吗？



说说我的两个想法：
当从上而下点灯时，最后一行灯的状态只与第一行灯的状态和点击有关；
随机亮灯时，先从下至上全部灭掉，再从上至下全部打开。

noski

顶，分析得漂亮！
我发现一个有意思的地方：
你11楼这个图，是从灯全亮状态下每个格点击一下，一共点击了100下得到的。
我按照你前面的解法来解这个图，先从下至上把灯全部点亮，除了最顶行，这用了42步；
查得状态633：204，然后从上至下把灯全部点亮，用了58步，加起来恰好是100步！

还有，lulijie贴出的1024表格挺有用的，但是玩起游戏来还要查表，就不那么容易了，谁也记不住啊，呵呵！

另外1楼游戏的小BUG：在一个格子里狂点三四下，这几格的灯就全亮或全灭了-_-

noski

回复sokoban：
回复superacid：
sokoban发的链接中的方法直接可以解出最终结果，对于10*10的游戏，要解一个100维的非齐次线性方程组。
这样看来，“最少步数”“最乱状态”什么的就都可以靠穷举搜索出来。

看看能不能找到一个可玩性好点的策略，让这个游戏除了查表、解方程组之外，不只是碰运气-___-，这样没事还可以玩一玩。。
就像平时玩魔方，我们不是对于每个乱的魔方，都去全空间搜索它的最短路径来还原它，而是有一系列的方法，比如层先、CFOP等。。

noski

lulijie在20楼的解法很不错，用此法可一举解决点灯问题，在步数和时间上有个平衡，可玩性好。。
在理解了这个解法之后就可以更直观一些，不用记任何公式。比如对于距边3个格子以上的地方（N，1），只要看（N-2，10）、（N，10）、（N+2，10）这三个位置亮灯的个数，如果亮的灯是偶数，就需要点击一下。

金眼睛的小程序也很赞，还有击缶功能