Lights Out(关灯游戏) 是一款经典的老游戏，维基百科上说Lights Out 是在1995年由 Tiger Toys 第一次发行。接触它却在去年的时候Gnome3的小游戏里。Lights Out 的规则很简单，游戏由一个 5 * 5 格的棋盘构成，每格子都是一颗灯，灯肯定是有两种状态，亮或者暗。游戏一开始棋盘上会亮起一些灯，你的目标就是把所有亮起灯都关掉，亮起的灯点一下就会关掉，但游戏当然不会这么简单，点一下灯的时候还会有一些附加影响，准确的说就是点一下灯的时候会切换它和四周也就是是上下左右的灯的状态。找到了一个在线的Lights Out，http://www.addictinggames.com/puzzle-games/lightsout.jsp。一般能过第五关就差不多了吧。
不过即便是第一关，如果一开始摸不到基本的门道，乱点的话基本上想点回来是很难的，为什么？\(2^{25}\)等于多少 ，作为一个合格的码农应该脱口而出，33554432 ！好吧我承认我也是用计算器的。要玩这游戏首先要明白一个道理：你关的不是灯，是寂寞…噢不，是开关！先不管棋盘上的灯光状态如何，也不管一个开关可以控制多少颗灯，只要知道你点一下方块，就等于切换一次开关，开关就从状态1转换到状态0，再点一下方块，开关又从状态0切换回状态1。这里的0和1也就是开关开和关两种状态，明白这一点很重要，把所有开着的开关都关闭就是完成游戏，所有开着的开关都关闭，肯定没有灯是亮的是吧，但是反过来并不一定成立哦，后面会说到这个。它还可以继续往下推，第一点，每一个方块只有点第一下才是有意义的，点第二下也就切换会原始状态，点N下也就是来来回回切换而已。第二点，开关关闭的顺序无关紧要。从上往下点，从下往上点都没关系。
如果你有迈克那么牛逼的话，相信现在已经能够透过亮着灯光看到后面隐藏的开关了吧，看不到也没关系先想象一下。我们知道一个开关控制着上下左右和本身的灯光，相对的，一颗灯亮与否，取决于它本身和四周开关的状态，当有奇数个开关开着的时候，灯就亮，偶数个的时候灯就是暗着的。再看看第一行，第一行上的一颗灯，能影响到它的开关有本身、左右，这三个都是第一 行上的开关，另外还有下方位于第二行的开关，而上方的开关因为是第一行所以是不存在的。现在假设一下，第一行所有开关都被关闭了，那么此时第一行如果还有亮着的灯，能控制这些灯的开关就只剩下第二行的开关，一颗亮着的灯，显然第二行其对着的开关肯定是打开的，相反的，第一行的灯是暗的，那么第二行对应的开关肯定是关闭的，这样第二行打开的开关就是其上面的灯还亮着的那些。照着第一行亮着的灯把第二行的开关全部关掉，现在一行的灯应该是全暗的，第二行的开关也全部关闭了，第二行还亮着的灯也就只有第三开关能影响到了。同样的，此时第二、三行的情况就跟前面第一、二行的情形一样了。以此类推，第三、四、五行的开关都可以这样关掉，此时游戏也就解决了。终于有一条有用的结论了，当第一行的开关全部关闭后，其他行的开关通过一个唯一且固定的模式来把开关全部关闭，也就是说对应着上一行亮着的灯把下一行对应的开关关闭就行。有了这个结论，现在已经把游戏的难度降低不少了，我们只要猜对第一行打开的开关就可以把游戏K.O.了。这个结论，我们把问题猜测的规模从\(2^{25}=33554432\)降到\(2^5=32\)。当然这样有点无趣，也不会变得完全没有难度。 但对于计算机来说，那确实是易过吃碗水，遍历第一行的所有可能性，再校验是不是一个解。
但是这种方法不能脱离暴力搜索，始终有点丑陋。我在看Gnome Lights Out 的源码的时候，发现了一篇论文讨论了如何用线性代数的方法来解决这个问题。非常简单的一个方法。
首先我们随便找一个开局状态，1表示灯是亮的，0表示灯是暗的。如下所示，
把这些数字放到一列里并标上号，就成了向量\(\vec b=(b_{1,1},b_{1,2},\cdots,b_{1,5},b_{2,1},\cdots,b_{5,5})^T\)
当我们按一下开关，\(\vec b\)又会发生什么变化呢？比如按下位于坐标(1,1)的开关，记为\(s_{1,1}\)。当\(s_{1,1}\)按下时，他会改变\(b_{1,1} ,b_{1,2},b_{2,1}\)的状态，如果灯光原来的状态为0，那么就变成1，原来为1就变成0。这个刚好是GF(2)上的加法，GF(2)怎么说呢，其实和一般的数域没什么区别，因为只有两个元素 0， 1 。那么在这个域上 1 + 1 就等于 0 。我们把\(s_{1,1}\)也用向量表示，它就是这个样子的
\[\vec s_{1,1}=(1,1,0,0,0,1,0,\cdots,0)\]当我们在游戏中点一下开关\(s_{1,1}\)，数学上就等于\(\vec b + \vec s_{1,1}\) 。我们还可以继续表示其他开关的向量，比如，
\[\vec s_{1,2}=(1,1,1,0,0,0,1,\cdots,0)\]\(\vec s_{5,5}=(0,\cdots,0,1,0,0,0,1,1)\) 。
前面我们说过，这个游戏的目的就是把全部打开着的开关都关闭了，开关的状态我们已经用\(s_{1,1},\cdots,s_{5,5}\) 表示，不多不少刚好25个，如果我们用1来表示这个开关是打开，0来表示关闭，那么一个游戏初始的开关状态也可以用一个向量来表示，
\(\vec x=(x_{1,1},x_{1,2},\cdots,x_{1,5},x_{2,1},\cdots,x_{5,5})^T\) 。由于游戏的开关状态时未知的，是我们玩这个游戏的目的，所以这里用x表示。\(\vec x\)即是初始局面打开的开关，也是灯全暗变换到棋盘初始状态所需要点开的开关，所以我们也把\(\vec x\)称为一个策略。\(\vec b\)表示初始状态，\(\underline{0}\)灯光全暗的状态。
\[\vec b =\underline{0}+x_{1,1}\vec s_{1,1}+\cdots+x_{1,5}\vec s_{1,5}+x_{2,1}\vec s_{2,1}+\cdots+x_{5,5}\vec s_{5,5}\]解上面的方程可以用下面这个线性方程来表示：\(A\vec x=\vec b\) 其中A是一个 25 * 25 的矩阵：
\[A = \begin{vmatrix}B & I & O & O & O \\I & B & I & O & O \\O & I & B & I & O \\O & O & I & B & I \\O & O & O & I & B \\\end{vmatrix}\]I是一个 5 * 5 的单位矩阵，O是一个 5 * 5 其元全部为零的矩阵。而B是这样一个矩阵：
\[B = \begin{vmatrix}1 & 1 & 0 & 0 & 0 \\1 & 1 & 1 & 0 & 0 \\0 & 1 & 1 & 1 & 0 \\0 & 0 & 1 & 1 & 1 \\0 & 0 & 0 & 1 & 1 \\\end{vmatrix}\]如果把 I, O, B 代入 A 那么 A 的每一列都对应着一个开关的s向量。
采用高斯-若爾當消元法对A的增广矩阵\((A \vec b)\)，就可以求出\(\vec x\) 。
如果令 \(\vec b = \bf{0}\)，在 5 * 5 的游戏规模下，解\(A\vec x=\bf{0}\)。除了 \(\vec x = \bf{0}\)外，还有另外两个解，分别是：
\[\vec x_{1}=(0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0)^T\] \[\vec x_{2}=(1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1)^T\]由此可见，5 * 5 游戏的解并不是唯一的，即便是灯光全暗，也不一定表示开关全部被关闭。另外，并不是所有可能性都有解。好了就先到这里，了解更多请见下面的链接：