一、序言

继续日常父女观影，这周的“黑白迭代”游戏实际上就是“点灯游戏”的变异版，我十几年前研究过该游戏的算法。这篇攻略将在程序算法的基础上，整理出5x5、6x6、8x8方格的人工计算方法，并做适当优化。如果下周有空的话，就补齐几种程序算法并对比算法复杂度。另外，现场比赛时采用8X8方格，实际上根据简单观察做题的话，往往是要尝试很多次的。比赛的题目很多选取了采用贪心策略可以做出来的，否则最坏情况下要尝试16次，时间根本不够，详见吐槽分析章节。贪心法不好用，那么有没有其他办法又快又准的做出来呢？答案是有的，就是要提前计算好关联表，可以轻松解决，也就是这篇攻略的主要内容了。

二、题目

共有8x8个电灯及对应位置的按钮，点击一个按钮后，这个按钮对应的电灯和周围四个相邻的电灯的状态全部都会改变（由暗变为亮或者亮变为暗）。目标是通过点击按钮让所有的电灯形成要求的图案。

ps：游戏里貌似图案都是轴对称图形，根据这点可以做优化。

三、吐槽分析

为什么说比赛时实际上是题目放水，要不然贪心法根本是无效的呢。实际上对于8x8方格的灯阵，解是唯一的。当灯阵是轴对称时，按钮答案也对应的是轴对程。（注：如果答案不是轴对称，那么它的轴对称答案也是正确答案并与它不同，与唯一解矛盾。）

只要选定第1行按钮方式，都可以推算出1种n*n按钮方式，使前n-1灯阵符合要求。但是其中只有1种第1行按钮方式，能使第n行也满足要求。而哪种第1行按钮方式是正确解，是取决于全盘灯阵，而不是通过贪心法能确定的。怎么理解这段话呢？让我们通过一个示例来说明下。这是比赛时的一道题目，这道题就是不能用贪心法计算的。

对于该图中的前两行有多种解法可以满足要求（实际上共有16种）

实际上这16种方法只有1种是正确的，而这题用贪心法往往选择的是方法一，那么这题最终正确解法是什么呢？

是不是觉得正确解法有点神奇？实际上我甚至可以轻松编出一个前七行点阵图一模一样，但是需要第1行按钮全点的图形。

综上所述，比赛题目放水，不然盲试的话，按期望值平均得尝试8次才有可能解出。

下面我将带你出坑，找到1种100%能够1次解出的方法。特别是对于轴对称图形，只需背几个简单的数字代码就可以轻松解答。

四、 5阶灯谜精确求解

4.1约定及引理

约定
将第1行的按钮按下次数分别依次记为 $b_{11}, b_{12}, b_{13}...b_{21}, b_{22}, b_{23}...b_{31}, b_{32}, b_{33}...$ ，将电灯状态是否改变按矩阵编码为 $l_{11}, l_{12}, l_{13}...l_{21}, l_{22}, l_{23}...l_{31}, l_{32}, l_{33}...$ 。
引理1
$b_i$ 只需记0, 1值， $l_{ij}$ 同理。
（简证：由于偶数次效果抵消。）
引理2
每个 $l_{ij}$ 仅受该 $b_{ij}$ 按钮及四周按钮影响，且有类似的关系式存在： $l_{22}= b_{12}+b_{21}+b_{22}+b_{23}+b_{32}$ ，其中加号为模2加，程序实现可使用异或。
（简证：可以理解为灯状态是否改变取决于所有能影响该灯的按钮按下次数和的奇偶性。）
引理3
根据引理2，因为 $l_{ij}$ 为固定变量，所以当 $b_{(i-1)1}, b_{(i-1)2}, b_{(i-1)3}...b_{i1}, b_{i2}, b_{i3}...$ 确定后， $b_{(i+1)1}, b_{(i+1)2}, b_{(i+1)3}...$ 唯一确定。
推论当 $b_{11}, b_{12}, b_{13}...$ 确定后，所有 $b_{ij}$ 均唯一确定。

4.2 公式推导

以下为繁琐的公式推导，没有耐心看的可以直接跳到4.3看结论。

$l_{11}=b_{11}+b_{12}+b_{21} \implies b_{21}=b_{11}+b_{12}+l_{11}$
$l_{12}=b_{11}+b_{12}+b_{13}+b_{22} \implies b_{22}=b_{11}+b_{12}+b_{13}+l_{12}$
$l_{13}=b_{12}+b_{13}+b_{14}+b_{23} \implies b_{23}=b_{12}+b_{13}+b_{14}+l_{13}$

如同引理3，当 $b_{11}, b_{12}, b_{13}...$ 确定后，所有 $b_{ij}$ 可表为 $b_{11}, b_{12}, b_{13}...$ 及 $l_{ij}$ 的关系式。以下为方便人工计算，将其拆为两张表分别计算，将表中将 $b_{11}, b_{12}, b_{13}...$ 简记为 $1,2,3...$ ，加号省略， $l_{ij}$ 简记为 $ij$ ，加号以“,”代替。
（注：计算过程中注意同样的数值两次可抵消，如 $b_{12}+b_{13}+b_{14}+b_{13}+b_{15}=b_{12}+b_{14}+b_{15}$ ）

即有
$b_{12}+b_{13}+b_{15}=l_{15}+l_{22}+l_{23}+l_{24}+l_{31}+l_{33}+l_{41}+l_{42}+l_{51}$
$b_{11}+b_{12}+b_{13}=l_{14}+l_{21}+l_{22}+l_{24}+l_{25}+l_{34}+l_{41}+l_{42}+l_{43}+l_{52}$
$b_{11}+b_{12}+b_{14}+b_{15}=l_{13}+l_{21}+l_{23}+l_{25}+l_{31}+l_{35}+l_{42}+l_{43}+l_{44}+l_{53}$
而 $b_{13}+b_{14}+b_{15}=(b_{11}+b_{12}+b_{13})+(b_{11}+b_{12}+b_{14}+b_{15})$ ， $b_{11}+b_{13}+b_{14}=(b_{12}+b_{13}+b_{15})+(b_{11}+b_{12}+b_{14}+b_{15})$ ，说明该行列式非满秩，有两个自由变量，于是不妨设 $b_{11}=0, b_{12}=0$ 进行求解。
如果考虑到图形是轴对称图形，该表可进一步化简为下表

至此为止，已经快速的找到其中一组解。

（ps1：由于有两个自由变量，所以总共有四组解。可以依次设 $b_{11}=0, b_{12}=1$ 或 $b_{11}=1, b_{12}=0$ 或 $b_{11}=1, b_{12}=1$ 即可解出其他三组解。）

（ps2：注意到 $b_{11}+b_{12}+b_{13}=l_{12}+l_{32}+l_{41}+l_{42}+l_{43}+l_{52}$
$b_{11}+b_{12}+b_{14}+b_{15}=l_{13}+l_{23}+l_{43}+l_{53}$
$b_{13}+b_{14}+b_{15}=l_{12}+l_{32}+l_{41}+l_{42}+l_{43}+l_{52}$
以及 $b_{13}+b_{14}+b_{15}=(b_{11}+b_{12}+b_{13})+(b_{11}+b_{12}+b_{14}+b_{15})$ ，所以有
$l_{13}+l_{23}+l_{43}+l_{53}=0$ ，即不满足该条件的轴对称图形无解。）

4.3 结论总结

以下为轴对称图形的第1行的1组解，其他行可顺推。
$b_{11}=b_{12}=0$
$b_{13}=l_{12}+l_{32}+l_{41}+l_{42}+l_{43}+l_{52}$
$b_{14}=b_{15}=l_{11}+l_{12}+l_{23}+l_{31}+l_{32}+l_{33}+l_{43}+l_{52}$

4.4 实战

那么，首先来个理工男的浪漫吧，点个心。

直接套公式，第1行按钮状态为

其他行推理如下：

五、 6阶灯谜求解

5.1公式推导

以下为繁琐的公式推导，没有耐心看的可以直接跳到5.2看结论。

考虑轴对称性，直接采用简化表格。

可以看出该行列式满秩，因此解唯一，并且解具有对称性，可分为两组。
按照三中方法，同理可以得到

而实际上

5.2 结论总结

$b_{11}=b_{16}=l_{12}+l_{13}+l_{23}+l_{33}+l_{42}+l_{43}+l_{51}+l_{61}+l_{63}$
$b_{12}=b_{15}=l_{11}+l_{12}+l_{22}+l_{23}+l_{32}+l_{33}+l_{41}+l_{42}+l_{52}+l_{63}$
$b_{13}=b_{14}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{23}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}$

5.3 实战

例一

$b_{11}=l_{12}+l_{13}+l_{23}+l_{33}+l_{42}+l_{43}+l_{51}+l_{61}+l_{63}$
$=1+1+1+1+0+1+0+1+1=1$
$b_{12}=l_{11}+l_{12}+l_{22}+l_{23}+l_{32}+l_{33}+l_{41}+l_{42}+l_{52}+l_{63}$
$=1+1+1+1+0+1+0+0+1+1=1$
$b_{13}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{23}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}$
$=1+1+1+0+1+1+0+0+1+0+1+1+1=1$
所以第1行按钮为111111。
例二

$b_{11}=l_{12}+l_{13}+l_{23}+l_{33}+l_{42}+l_{43}+l_{51}+l_{61}+l_{63}$
$=1+1+1+1+1+1+0+0+1=1$
$b_{12}=l_{11}+l_{12}+l_{22}+l_{23}+l_{32}+l_{33}+l_{41}+l_{42}+l_{52}+l_{63}$
$=1+1+1+1+1+1+0+1+0+1=0$
$b_{13}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{23}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}$
$=1+1+1+1+1+1+0+1+1+0+1+0+0=1$
所以第1行按钮为101101。

六、 8阶灯谜求解

6.1公式推导

以下为繁琐的公式推导，没有耐心看的可以直接跳到6.2看结论。

8阶类似6阶，也是满秩的。考虑轴对称性，直接采用简化表格。

6.2 结论总结

求解过程略去，得解
$b_{11}=b_{18}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{24}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}+l_{63}+l_{64}+l_{72}+l_{74}+l_{83}+l_{84}$
$b_{12}=b_{17}=l_{11}+l_{13}+l_{14}+l_{21}+l_{22}+l_{24}+l_{31}+l_{33}+l_{34}+l_{42}+l_{52}+l_{54}+l_{61}+l_{71}+l_{74}+l_{82}+l_{83}$
$b_{13}=b_{16}=l_{11}+l_{12}+l_{31}+l_{32}+l_{43}+l_{51}+l_{53}+l_{54}+l_{61}+l_{63}+l_{64}+l_{73}+l_{81}+l_{82}$
$b_{14}=b_{15}=l_{12}+l_{14}+l_{21}+l_{22}+l_{24}+l_{32}+l_{34}+l_{44}+l_{52}+l_{53}+l_{54}+l_{61}+l_{63}+l_{71}+l_{72}+l_{81}$

6.3 实战

$b_{11}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{24}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}+l_{63}+l_{64}+l_{72}+l_{74}+l_{83}+l_{84}$
$=0+0+1+0+1+0+0+0+0+1+1+0+1+1+0+0+0+1+1=0$
$b_{12}=l_{11}+l_{13}+l_{14}+l_{21}+l_{22}+l_{24}+l_{31}+l_{33}+l_{34}+l_{42}+l_{52}+l_{54}+l_{61}+l_{71}+l_{74}+l_{82}+l_{83}$
$=0+1+0+0+1+0+0+0+1+0+0+0+0+1+0+0+1=1$
$b_{13}=l_{11}+l_{12}+l_{31}+l_{32}+l_{43}+l_{51}+l_{53}+l_{54}+l_{61}+l_{63}+l_{64}+l_{73}+l_{81}+l_{82}$
$=0+0+0+0+0+1+1+0+0+1+0+0+1+0=0$
$b_{14}=l_{12}+l_{14}+l_{21}+l_{22}+l_{24}+l_{32}+l_{34}+l_{44}+l_{52}+l_{53}+l_{54}+l_{61}+l_{63}+l_{71}+l_{72}+l_{81}$
$=0+0+0+1+0+0+1+0+0+1+0+0+1+1+0+1=0$
所以第1行按钮为01000010。

七、比赛技巧

可能有人要说了，上面算出来的关联表是好用，但是这么复杂，比赛时怎么用呀？实际上，上面的例子只需要稍加编码，结合记忆方法，就能用起来了。
下面以最复杂的8阶灯谜为例，
$b_{11}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{24}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}+l_{63}+l_{64}+l_{72}+l_{74}+l_{83}+l_{84}$
$b_{12}=l_{11}+l_{13}+l_{14}+l_{21}+l_{22}+l_{24}+l_{31}+l_{33}+l_{34}+l_{42}+l_{52}+l_{54}+l_{61}+l_{71}+l_{74}+l_{82}+l_{83}$
$b_{13}=l_{11}+l_{12}+l_{31}+l_{32}+l_{43}+l_{51}+l_{53}+l_{54}+l_{61}+l_{63}+l_{64}+l_{73}+l_{81}+l_{82}$
$b_{14}=l_{12}+l_{14}+l_{21}+l_{22}+l_{24}+l_{32}+l_{34}+l_{44}+l_{52}+l_{53}+l_{54}+l_{61}+l_{63}+l_{71}+l_{72}+l_{81}$
按照每行进行编码， $2^4=16$ ，只需要一位16进制数字就可以编码1行。
以下是编码结果：
$b_{11}=EDE82F53$
$b_{12}=BDB45896$
$b_{13}=C0C2BB2C$
$b_{14}=5D517AC8$
采用记忆宫殿8个桩，每个桩4个数字，就可以记住这个32位编码。
做题时，可以对照实图过码，算出第1行4位正确初始值。

首先第一个编码EDE82F53，对照实图数数01311111=1，同理第二个编码BDB45896，对照实图数数11312010=1，第三个编码C0C2BB2C，对照实图数数00203100=0，第三个编码5D517AC8，对照实图数数11213000=0。

然后记住4个初始值“1100”以及实图就可以开始做题了。记忆实图也可以采用此编码方法，将图编码为8位数字，这样可以提高记忆准确性和持久性。（实图可编码为11FDF111）
开始解题，先点出11000011，然后根据实图编码11FDF111，从第2行开始递推。

七、后记

时间仓促，简单整理了下思路写的这篇攻略，基本上通过记忆关联代码，可以解决5x5、以及轴对称的6x6、轴对称的8x8方格灯谜。规模再增加或者无对称性，记忆量将大大增加，不适合普通人练习（好像简单规模普通人愿意玩的也不多-_-）。

大规模的无规律复杂图形，可以采用计算机程序求解。如果下周有空的话，我就补个算法，按照上述思路，首行固定推导加高斯消元法设计算法，复杂度应该在 $O(n^3)$ ，应该可以轻松解决100x100方格灯谜。

另外关于n阶方阵灯谜，还有很多有意思的地方。比如，数列A159257就表述了在不同n时方阵满秩的情况（0, 0, 0, 4, 2, 0, 0, 0, 8, 0, 6, 0, 0, 4, 0, 8, 2, 0, 16, 0, 0, 0, 14, 4, 0, 0, 0, 0, 10, 20, 0, 20, 16, 4, 6, 0, 0, 0, 32, 0, 2, 0, 0, 4, 0, 0, 30, 0, 8, 8, 0, 0, 2, 4, 0, 0, 0, 0, 22, 0, 40, 24, 0, 28, 42, 0, 32, 0, 8, 0, 14, 0, 0, 4, 0, 0, 2, 0, 64, 0, 0, 0, 6, 12, 0, 0, 0, 0, 10, 0, 0, 20, 0, 4, 62, 0, 0, 20, 16, 0, 18, 0, 0, 4, 0, 0, 6, 0, 8, 0, 0, 0, 2, 4, 0, 0, 0, 8, 46, 0, 0, 0, 80, 4, 50, 56, 0, 56, 56, 0 ），而解个数就是对应的2的对应数字方幂。又比如，如果你把灯全点亮的解显示出来，会是十分优美的图案（ps再次感叹数学之美）。

该图为网图，感谢原作者。

最强大脑之黑白迭代吐槽攻略v1.0

最强大脑之黑白迭代吐槽攻略v1.0

一、序言

二、题目

三、吐槽分析

四、 5阶灯谜精确求解

4.1约定及引理

4.2 公式推导

4.3 结论总结

4.4 实战

五、 6阶灯谜求解

5.1公式推导

5.2 结论总结

5.3 实战

六、 8阶灯谜求解

6.1公式推导

6.2 结论总结

6.3 实战

七、比赛技巧

七、后记

最强大脑之黑白迭代吐槽攻略v1.0

一、序言

二、题目

三、吐槽分析

四、 5阶灯谜精确求解

4.1约定及引理

4.2 公式推导

4.3 结论总结

4.4 实战

五、 6阶灯谜求解

5.1公式推导

5.2 结论总结

5.3 实战

六、 8阶灯谜求解

6.1公式推导

6.2 结论总结

6.3 实战

七、比赛技巧

七、 后记

七、后记