设计点灯游戏前的总结

因c语言程序设计实践课，恰好选择了对点灯游戏的实现，则我们先来归纳如何去求点灯游戏的方案。

零——前置芝士

点灯游戏简介

一层大楼共有 \(n×n\) 个房间，每个房间都有一盏灯和一个按钮。按动一个房间的按钮后，这个房间和周围四个相邻的房间的灯的状态全部都会改变（由暗变为亮或者亮变为暗）。目标是通过按按钮把所有的灯都点亮（默认情况下全暗）。

点灯游戏规律

我们不难发现以下规律

\(1.\)按偶数次按钮相当于没有按。

\(2.\)无论按按钮顺序如何结果总是一样的。

因此我们有以下结论

\(1.\)对于盘面上的每一个按钮，我们只需要考虑其按开或关的状态。

\(2.\)每一个按钮的状态都是互相独立的，不需要考虑按按钮的顺序。

壹——解决算法

1.完全穷举法，\(O(2^{n^2})\)

对于每一个按钮，只有开和关两种状态。

而如果所有按钮的状态确定了，那么灯的状态也就确定了。

那么，我们就将点灯的问题转化为了对按钮状态的统计，只需要将所有按钮的所有可能的状态列举出来，算出灯所对应的状态并判断灯是否全部点亮即可。

不难发现，一个按钮的状态有开关 \(2\) 种，因此x个按钮的状态则为 \(2^x\) 种。一个房间共有 \(n×n\) 个按钮，因此共 \(2^{n×n}\) 种状态。复杂度则为 \(O(2^{n^2})\) 。

\[注：此处应为 O(2^{n^2}+n^2)，因为每个灯的计算还需要O(1)，但是n^2远小于2^{n^2},\\故可忽略不记。
\]

2.首行穷举法， \(O(2^n)\)

对于算法1，当 \(n=6\) 时，状态已达到 \(2^{36}=68719476736\) 。所以我们要考虑剪枝或者进一步简化。

比如只按1或2个按钮的状态显然不成立，可以快速排除。

我们将整个房间的每一排从上到下看作有顺序的，那么从第一行开始按按钮。

假设我们已经决定了第一行按钮的状态，此时只有第一行和第二行的灯的状态发生了改变。

由于只有第一行和第二行才会改变第一行灯的状态，那么为了使第一行全亮，而且此时第一行按钮状态已确定，我们只能通过改变第二行按钮的状态来使第一行全亮。

同理，为了使第二行全亮，因第二行按钮已确定，所以要改变第三行按钮的状态，以此类推，整个房间的按钮都被第一行的按钮所确定，而房间里除了最后一行也都是全亮的。

因此，我们不需要把房间里所有的按钮可能的状态列出来，只需第一行。对于每一种第一行的状态，再按上面的步骤计算后面 \(n-1\) 行的按钮状态，然后判断最后一行的灯是否全亮即可。

第一行共 \(n\) 个灯，因此共 \(2^n\) 种状态。复杂度为 \(O(2^n)\) 。

3.完全方程法，\(O(n^6)\)

虽然算法2已经将复杂度降到了 \(O(2^n)\) ，但是当 \(n>30\) 时，这仍是普通计算机无法承受之大。那么我们怎么才能再降一降时间复杂度呢？

在我们从 \(1 \rightarrow 2\) 时，发现了一行灯的状态由它的上一行，这一行和下一行按钮决定，而不是所有按钮，是行与行的关系。

这启发我们是不是对于同一行的按钮或者灯的状态也能找出来关系呢？

答案是肯定的。我们知道，一个按钮可以影响它和它周围4个灯的状态，反过来，一个灯的状态则由它本身和周围最多4个按钮决定的。

\[\color{gold}{——————————奇迹时间到——————————}
\]

我们假设方块为按钮，圆圈为灯，黑表示开，白表示关。

再假设一个灯由两个按钮决定状态，那么具体可以表示为：

\[\Box+\Box= \circ\\
\blacksquare+\Box=\bullet\\
\Box+\blacksquare=\bullet\\
\blacksquare+\blacksquare= \circ
\]

看起来好像可以转化为数学式子，假设

\[\Box=0,\blacksquare=1,\circ=1,\bullet=1
\]

那么，上面四个等式可转化为

\[0+0=0\\
1+0=1\\
0+1=1\\
1+1=0
\]

欸，这个+好像不是加法，而是（逻辑上的）异或运算 \(\oplus\)

现在，把灯转化为一般情况，那么就由本身以及上下左右四个按钮来决定灯的状态。例如

\[\Box12+\Box21+\Box22+\Box23+\Box32=\circ22
\]

那么，对于房间里所有按钮和灯，我们可以列出 \(n*n\) 个式子，而且因为我们的目的是将所有灯点亮，那么灯的状态应均为 \(\bullet\) ，若此时以按钮为未知数，即为 \(n^2\) 元一次方程组。

我们只需要解方程就可以了(✿◡‿◡)

说到解方程，大家可能立马会想到矩阵。没错，我们把方程式表示成矩阵的形式，然后对矩阵高斯消元即可。

高斯消元的过程等同于求逆矩阵，而所得的矩阵的每一行就表示需要单独点亮一个灯，需要按哪些按钮。

而且可以通过矩阵秩的运算求出多解，这里不过多说明。

高斯消元本身的复杂度是 \(O(n^3)\) ，而矩阵边长为 \(n^2\) ，所以总时间复杂度为 \(O(n^6)\) 。（成功进入线性时代）

4.首行方程法， \(O(n^3)\)

如同从1到2，3到4也是实现了由整体到第一行，不再过多说明。

高斯消元复杂度为 \(O(n^3)\) ，由第一行按钮推算全部的按钮复杂度为 \(O(n^2)\) ，总体为 \(O(n^3)\) 。

5.n不同时解的数量

挖个坑，学完线性代数再回来填。

秩真不明白。

逼零集，点灯游戏和解线性方程组 - 知乎 (zhihu.com)

贰——点灯游戏代码的实现

此处代码并非只是方案实现的代码，也要实现程序设计课程的要求以及程序的美观。

（下周这个时候不见不散。）

链接：https://www.dianjilingqu.com/628031.html