最近由于疫情隔离在家, 所以正好抽空刷一刷leetcode, 于是刷到了Minimum Number of Flips to Convert Binary Matrix to Zero Matrix这题, 题中讲的是一个将二元数组中的1根据特殊规则全消减成0的游戏. 看到规则, 虽然我记不得这游戏是叫什么名字, 但我确定曾经玩过几次这个游戏, 最近的一次是我拿Lue和Love游戏引擎写点格棋游戏的时候, 在社区里看到有人分享了用Love做的这个游戏. 查了一下, 原来叫灭灯游戏(Lights Out), 在国内貌似一般叫点灯游戏? 不过也没差, 这个点灯游戏规则很简单, 相信很多人都玩过, 长方形中划分网格, 每个网格是盏灯, 且有亮与暗两种状态, 游戏中唯一的操作是选择一盏灯改变状态, 同时这盏灯上下左右的灯(如果存在的话)状态也将同时改变, 游戏初始状态时可能有几盏灯已经是点亮的, 游戏的目的是经过一系列的开关灯的操作, 使网格中的灯全部点亮. 这里有个在线版本可以重温一下.

本来感觉这个点灯游戏也没什么, 感觉还是有博弈的游戏像是点格棋更有意思一些, 直到我看到了知乎专栏的这篇文章点灯游戏: 简单的游戏能否很美?, 说实话确实很美, 甚至感到有些震撼. 于是我打算稍微探索一下这个游戏, 所幸文章作者写得非常认真, 相关的结论和参考都有总结, 遗憾的是没有提到结论的证明. 虽然是已经被前人研究得比较透彻的问题, 但我还是想写点自己的理解, 于是就诞生了这篇不务正业的文章…

搜索算法解

要用搜索算法来解点灯问题就比较简单粗暴, 遍历所有点灯方案找出满足要求的方案即可(在leetcode中还需要得到操作最少的方案). 在解决问题之前首先必须对问题有足够的理解, 我们必须先说明下面虽明显但重要的两点, 即:

  • 操作的顺序无关性. 对于将所有灯从初始状态状态转换成全亮的点灯方案, 其一系列操作的顺序可以是任意的, 这很好理解, 因为对于点灯游戏, 灯的最终状态只取决于两点, 即初始状态与状态翻转的次数, 而与翻转的先后次序无关.
  • 操作的非重复性. 这即是说如果我们需要找到一个操作最少的方案, 那么每盏灯被选择改变状态的次数是最多一次. 结合前面操作的顺序无关性很容易说明. 假设有这么一组操作方案是点灯游戏的一个解, 而这组操作中包含了多次选择同一盏灯进行翻转的操作, 我们可以利用顺序无关把这些操作集中到一起, 也就是连续对同样的灯进行翻转. 由于灯只有两种状态, 偶数次的相同操作相当于没操作, 奇数次的相同操作相当于操作了一次, 因此该方案都不可能是操作最少的方案.

了解了上面两点我们才可以尝试着去解决问题, 其实这里我还尝试着考虑了下操作的唯一性, 但是无果. 有了更多的了解之后才意识到解确实不是唯一的.

算法的大致构思即测试所有点灯方案, 如满足要求记录下该方案. 剩下来的就是一些技术问题, 我们怎么存储点灯方案, 灯的当前状态又如何表示? 这里用二进制数来进行表示是一个比较好的想法, 其一是比较节省存储空间, 其二是状态的翻转可以用对相应位的异或来实现. 但是二进制矩阵不太容易实现, 对于小型规模的点灯游戏, 用c++内置类型即可, 如4字节int型可以用于存储32盏灯的状态, 这里涉及到的一个问题是两者从矩阵到数列坐标的转换. 对于测试的每一种点灯方案, 也可以用一个int来存储, 1的那些位表示直接选择翻转的灯. 当然别忘了选择翻转的灯的上下左右(如果存在的话)也需要进行翻转. 操作的次数只需要计算存储电灯方案int中二进制下1的个数即可. 下面是code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int m = mat.size(); // 灯矩阵行数
        int n = mat[0].size(); // 灯矩阵列数
        int stat = 0; // 存储初始灯的状态
        int plan = 0; // 当前应用的电灯方案
        int ans = -1; // 存储最少的操作次数 若不可解则返回-1

        for (int i = 0; i < m * n; i++) // 初始状态生成
        {
            stat = stat << 1;
            stat += mat[i / n][i % n];
        }

        while (plan < pow(2, m * n)) // 遍历所有点灯方案 共 2^(mn) 种
        {
            int cnt = 0; // 存储当前点灯方案操作次数
            int num = plan;
            while (num)
            {
                ++cnt;
                num &= (num - 1);
            }
			// 如果该方案操作次数超过了之前解的操作次数 直接跳过该方案
            if (ans != -1 && ans <= cnt)
            {
                plan += 1;
                continue;
            }
            
            int temp = stat ^ plan; // 将temp初始化为 初始状态下翻转该方案选择操作的那些灯 后的结果
            for (int i = 0; i < m * n; i++) // 遍历plan
            {
                if (plan & (1 << m * n - i - 1)) // 翻转选择操作的那些灯上下左右的灯
                {
                    if (i / n - 1 >= 0)
                        temp ^= (1 << (m * n - (n*(i / n - 1) + i % n) - 1));
                    if (i / n + 1 < m)
                        temp ^= (1 << (m * n - (n*(i / n + 1) + i % n) - 1));
                    if (i % n - 1 >= 0)
                        temp ^= (1 << (m * n - (n*(i / n) + i % n - 1) - 1));
                    if (i % n + 1 < n)
                        temp ^= (1 << (m * n - (n*(i / n) + i % n + 1) - 1));
                }
            }
            if (temp == 0) // 当temp为0时 即灯全亮 是一个解
                ans = cnt;
            plan += 1; // 处理下一个点灯方案
        }
        return ans;
    }
};

上面的实现思路是比较简单的, 具体实现中其实也并没有遍历所有点灯方案的必要(在只要求找到最少操作方案的条件下), 因此当我们遍历到一个点灯方案操作灯的数量多于已经找到的解时, 将直接跳过这个方案的处理(无论这个方案是否为解). 上述搜索算法时间复杂度显见是$O(2^{mn}*mn)$的. 这意味着当灯的数量较少时才可能在比较短的时间内找到解, 以我现在手头上的i5surface laptop来说, 找到4*4规模初始状态为灯全灭的点灯游戏的最优解(操作最少的解)需0.007s, 5*5需要11.829s, 而6*6则已经在30分钟以上了.

线性代数解

讨论完了暴力的搜索算法, 那么从数学的角度如何求解点灯问题呢? 根据每盏灯最终状态可由总翻转次数与初始状态确定这一点, 可以列线性方程来求解. 以下内容可参考Mathematica博客的这篇文章Lights Out Puzzle.

以3*3规模的点灯游戏为例, 我们首先需要得到一个9*9的二元对称矩阵$\boldsymbol{A}$,

矩阵$\boldsymbol{A}$中只有元素0和1, 且是对称矩阵, 对于同样规模和规则的点灯游戏, 矩阵$\boldsymbol{A}$都是相同的. $\boldsymbol{A}$的每一行是这么来的, 依然把3*3的9盏灯按行展开排成一行, $\boldsymbol{A}$的第i行由将第i盏灯和其上下左右灯(如果存在的话)的位置置1其余置0得到. 如$\boldsymbol{A}$的第一行, 先把第一个位置自己置1, 然后在点灯游戏中第一盏灯在最左上角, 把其下与其右的灯的位置(2与4)也置1, 其余位置为0. 也可以说成$\boldsymbol{A}$的第i行相当于把所有影响第i盏灯状态的位置都置1, 其余置0.

一旦构成了$\boldsymbol{A}$, 那么顺理成章, 我们将点灯方案排成一列, 为9*1的列向量, 规定选择翻转的位置为1其余为0, 用$\boldsymbol{x}$表示. 同理我们可以假设$\boldsymbol{r}$为所有灯最终状态, 而$\boldsymbol{c}$表示所有灯初始状态, 那么上述向量之间的关系为,

注意上式我们只在GF(2)内进行讨论(关于伽罗华域顺便安利一下介绍纠错码的这篇文章), 因为灯的状态只有0和1这两种. 将上式改成,

剩下来的问题就是解上面的非齐次线性方程组了. 可以用我们熟悉的高斯消元法(Gaussian elimination)来解, 就是用初等变换将增广矩阵化为行阶梯型来求解, 解不唯一时需要先求对应齐次方程组通解与其本身一个特解, 然后组合通解与特解得到所有方程组的解. 由于方程组是定义在GF(2)上的, 解的每一位从0与1中取值, 因此化为阶梯型后对于有$d$个自由变量的方程组共有有$2^d$个解. 所以这个解的数目确实不是唯一的, 下图是2*3规模点灯游戏初始状态为全灭的4个解(黑色表示选择翻转的灯, 下同). 从图中可以看出解具有对称性.

求解代码放在这里, 为了能够存储任意位数的二元矩阵使用了bitset类型, 其支持一些方便的位操作. 高斯消元法的时间复杂度为$O((mn)^3)$, 接着遍历找多解复杂度$O(2^d)$, 同样初始全灭的条件下, 解100*100规模点灯游戏找到所有的解需要15s, 相比搜索算法已经快了不少. 至于更快的方法主要是优化GF(2)下的方程组求解, 使用并行计算或改进高斯消元法. 下图为100*100的唯一解,

随便再放些不同规模解的图案吧, 可以发现有相当多的解是对称的, 特别是5倍数规模的解, 非常具有对称美. 以下为部分5倍数规模且解唯一的解图.

对于一些多解的情况也有不少是对称的, 下面是4*4, 5*5, 9*9, 16*16的多解图.

部分规模的解实在是太多了, 如30*30规模有$2^{20}$个解. 另外一个比较有意思的是对于有多解的情况, 存在着一种或多种最终不改变所有灯状态的点灯方案, 可由对应齐次方程组的解得到. 如下图是5*5不变的方案.

番外 解存在性讨论

事实上对于任意的m和n, 只要是满足自反(reflexive)与对称(symmetric)的点灯游戏, 初始状态为灯全灭的情况下, 可以证明游戏必定有解. 当然, 如果初始状态时已经有部分灯点亮则不一定有解. 证明之前先解释一下点灯游戏满足的自反与对称是什么.

自反即是说当选择一盏灯时, 除了翻转与这盏灯相邻灯的状态, 这盏灯本身也会状态翻转. 而对称是说相邻的两盏灯的状态相互影响, 当其中一盏翻转时, 另一盏灯的状态也会翻转. 其实点灯游戏有非常多的变种(就和魔方一样), 有些并不完全满足上面的两点, 比如Merlin Magic square游戏.

说明完毕, 推理证明如下.

使用反证, 假设存在着满足上述要求(自反, 对称, 初始状态为灯全灭)的点灯游戏无解, 且我们认为无解的情况中规模最小的有n盏灯, 此时n-1盏灯的点灯游戏则是可解的(如果不可解, 那么无解情况中规模最小的就应该是n-1盏灯了). 需要注意的是, 这里我们其实无视了灯的空间排列, 前面的讨论中, 点灯游戏普遍把所有灯排列成一个正方形或矩形, 这样只是为了让人容易看清(共享边的两盏灯是相互影响的), 但就本质上说, 我们完全可以用有向图(Directed Graphs)的结构来描述这个点灯游戏, 每盏灯是图中的一个结点, 由于游戏是对称的, 相互影响的灯的关系可以用双向的连线来表示, 因此这里不需要纠结n或者n-1盏灯能不能排列成矩形的空间结构的问题, 或者说能构成矩形空间结构的有向图在我们现在讨论的图的基础上需要更苛刻的条件.

如前所述, 那么我们必然有把这n盏灯中n-1盏灯点亮而只剩1盏灯灭掉的点灯方案(点灯方案指的就是n盏灯中选择哪几盏灯进行状态翻转), 这里的根据就是n-1盏灯的点灯游戏是可解的. 从n盏灯中选出n-1盏灯构成一个更小规模且可解的点灯游戏, 如果当这个小规模的点灯问题解决后(这n-1盏灯全点亮), 剩下来的那盏灯的状态是点亮的, 那么这个n盏灯的点灯游戏就也是可解的了, 这与假设矛盾, 因此孤立出来的那盏灯的状态必定是灭掉的. 对于总共n盏灯, 这n-1盏灯的选择显然有n种, 且这n种选择都能够完成上面所说的n-1盏灯亮1盏灯灭, 如此便得到了相应的n种点灯方案.

将上面得到的n种点灯方案从灯全灭的初始状态开始连续施行一次, 我们发现当n为偶数时, 所有灯的状态正好翻转奇数(n-1)次, 如此一来最终n盏灯的状态就都是点亮的了! 因而n盏灯的点灯游戏就可解, 与假设再次矛盾, 推出结论n只可能是奇数(当n为奇数时, 我们执行完上述n种点灯方案后, 所有灯翻转偶数次, 即状态不变, 全为灭).

我们继续讨论这n盏灯中是否存在着与偶数(包含0)盏其他灯相关联的灯(从有向图的观点来说, 就是这n个结点中是否存在着与偶数个其他结点双向连接的结点), 也就是这盏灯的状态翻转将影响其他奇数盏灯的状态翻转. 我们先假设存在这样满足条件的灯, 取其中的一盏来讨论, 把这盏灯和其关联的另外奇数盏灯单独划分为一组, 组内就有奇数盏灯. 我们从前面得到的n种点灯方案中挑选出以组内灯为最后灭掉的灯的那些方案, 将挑选出的这奇数个点灯方案同样从灯全灭的初始状态开始连续施行一次, 此时n盏灯中非组内灯的状态都改变了奇数次, 故都为点亮状态, 而组内灯状态则都改变了偶数次, 状态不变. 最后我们选择改变前面提到的满足条件的那盏灯, 如此组内灯的状态将再都改变一次, 即也都将被点亮. 此时我们发现所有灯都被点亮, 此n盏灯的点灯游戏可解, 再次与假设矛盾, 由此得到结论这n盏灯的每一盏灯都与其他奇数盏灯相关联, 而不可能是偶数盏.

推到这里, 其实我们已经找到了矛盾, 只是不是特别明显, 即点灯游戏的对称性与我们前面推出的有奇数盏灯且每盏灯都与其他奇数盏灯相关联之间存在矛盾. 点灯游戏的对称性也可以推出一个结论, 那就是当执行所有灯都选择点亮一次的点灯方案时, 不计算那些直接选择的灯的那次翻转, 只计算那些因其他灯选择翻转由于受关联而间接翻转的次数, 在这个意义下所有灯的累计翻转次数总是偶数次的. 道理也是显而易见的, 这里所谓游戏的对称性就是两盏相关联的灯是相互影响的, 选择一盏灯直接地状态翻转会间接地翻转相关联的另一盏灯, 而对那另一盏灯来说也同理. 当上述点灯方案都选择一次翻转后, 就这两盏相互关联的灯来说实际翻转了4次, 前面说这里我们不计算因直接选择的翻转, 所以计间接翻转的2次. 可见每一组相关联的灯都会计间接翻转的两次, 故最终所有灯累计的间接翻转次数必为2的倍数即偶数. 严谨起见, 我想还需要补充两点说明. 其一是这里计算的是因间接影响的翻转次数, 这仅仅是为了推理讨论的便利性(虽然其本身的理解增加了复杂性?). 其二是严格来说, 对于实际的一个点灯问题自然是不会出现孤立的灯的情况(这盏灯不与其他任何灯相关联), 但当存在孤立的灯时, 上述由对称性得到的结论仍然是正确的, 因为当选择点亮孤立的灯时, 由于没有与其相关联的灯, 所以计入的翻转次数为0.

但是如果点灯游戏中有奇数盏灯, 依然执行所有灯都选择翻转状态一遍的点灯方案, 为了能获得总共偶数次的间接翻转, 必然不可能每盏灯相关联的灯的数目都是奇数的, 或者说必定存在着与其他偶数盏灯(包括关联0盏的孤立的灯)相关联的灯, 这样我们就推得了最后一个矛盾, 从而否定了最开始无解的n盏灯的点灯游戏的存在性假设, 命题得证.

文字描述的证明有些地方确实啰嗦了点, 但我想还是尽可能留下更多的细节便于理解. 用线性代数的视角我们可以得到更简洁又严密的证明. 这里最后再说明一点, 在我参考的The Mathematics of Lights Out博客中, 作者对于最后一个矛盾的阐述举了一个更生动的例子, 但需要注意其与点灯游戏之间的差异. 这个例子是说有奇数个人参加聚会, 在聚会上自然少不了有些人会相互握手, 但是无论有多少人握手, 总存在和偶数个其他人握手的人(包括一次都没有和其他人握手的人). 这个例子确实容易理解很多, 而这个例子与点灯游戏的差异在于握手是关联的双方同时进行的, 且每一次握手操作都只涉及握手的双方. 而对于点灯游戏, 每一次的操作是选择一盏灯进行状态翻转, 故灯之间的相互影响(间接翻转)是分开进行的, 且一次操作同时影响多盏其他的灯, 但我们依然可以理解这背后其实是一回事, 也就是对称性的体现. 另一个差异则是点灯游戏具有自反性, 握手则自然不可能自己与自己握手, 因此在上面讨论中我们忽略了直接选择时的状态翻转.

同样引入线性代数能很大程度简化证明, 我们知道当非齐次线性方程组无解时有$\mathrm{rank}(\boldsymbol{A})<\mathrm{rank}(\boldsymbol{A|\boldsymbol{c}’})\leqslant mn$. 那么必然存在着非$\boldsymbol{0}$列向量$\boldsymbol{v}$有,

并且,

这里稍微解释下, 若上式不成立则,

这样方程组便有解了.

由于点灯游戏的自反与对称性, $\boldsymbol{A}$是定义在GF(2)上的对称矩阵, 且对角线元素都为1, 因此有,

这是因为左边展开后混合项都是成对出现, 故其系数皆为0, 只留下二次项. 结合最前面的式子便可得到,

于是,

这与$\boldsymbol{v}$为非零向量矛盾, 假设不成立, 因此解必定存在.

其实在线性代数中有一个更强的定理, 对于定义在GF(2)上的对称矩阵$\boldsymbol{A}$, 存在$\boldsymbol{x}$满足$\boldsymbol{Ax}=\mathrm{Diag}(\boldsymbol{A})$, 翻译过来就是二元对称矩阵$\boldsymbol{A}$对角线元素构成的列向量必定在$\boldsymbol{A}$的列空间中, 详细证明见这里. 如果知道这个定理对点灯游戏解的存在性甚至都不需要进一步说明, 因为在点灯游戏的设定下, 对称保证了$\boldsymbol{A}$是对称矩阵, 自反保证了$\boldsymbol{A}$对角线元素全为1, 而初始状态的$\boldsymbol{c}’$也总是全为1…

最后的最后, 这点灯游戏竟然让我找回了小时候摆弄万花筒的感觉, 这大概也算是数学的魅力之一吧…

参考

.

.

.

.

.

.

終わり