高斯消元法破解《黑白迭代》游戏

《最强大脑》的第七季中，有一个游戏项目叫《黑白迭代》。其游戏规则是在一个空白盘面上，每点击一个方格，该方格和四周的方格会出现反色。如下图所示：

选手需要在空白盘面上，通过不断点击方格完成对目标图形的构建。

这个游戏本质和关灯游戏是一样的。给一个由灯泡构成的灯阵，灯的开关规则如下：

当改变某盏灯的状态时，这盏灯的上下左右相邻的灯的状态也随之改变。游戏规则是对于任意给定的“亮灭”灯阵，通过一系列动作开关，最终使得所有的灯关闭。

本文将直接给出关灯游戏破解的高斯消元法（非齐次线性方程组），类似的方法（齐次线性方程组的高斯消元法）也可以用来破解《黑白迭代》游戏。至于破解原理，我们将在之后的文章中给出。

1

第一步：通过

的灯阵

, 其中,

如果第

行

列位置灯亮

如果第

行

列位置灯灭

构造一个

元向量

SPRING

例子

对这个灯阵，我们得到：

02

第二步：通过

的灯阵, 构造一个

的系数矩阵

其中

是一个

元列向量, 这里

例如对一个

灯阵来说,

因为点击

位置，改变状态的位置有

这时有四个位置的状态会发生改变. 一般情况下，最多有5个位置会发生改变.

这时的系数矩阵为

03

第三步，在域

中利用高斯消元法解齐次线性方程组

其中，

是一个有两个元素构成的集合(只需将

理解为奇数，

理解为偶数), 元素

之间的运算"

,

"满足奇数与偶数的“加、乘”运算法则。例如：

奇数

奇数

偶数

奇数

偶数

奇数

奇数

奇数

奇数

奇数

偶数

偶数

以上面灯阵为例，将增广矩阵

利用初等行变换化为简化阶梯形：

解得特解

选择

为自由未知数, 解得方程组的通解：

取不同的

, 计算可得：

04

第四步，方程组解向量中非零的位置即为需要点击开关的位置.

下面分别为方程组四个解对应的关灯游戏的四个解法：

X1=（0，0，0，1，0，0)

X2=(0,1,0,0,1,1)

X3=(1,1,1,1,1,0)

X4=(1,0,1,0,0,1)

从这个例子可以看到，高斯消元法不仅仅在数域上的线性方程组成立，还可以应用到一般的域上。这时一个线性方程组解的三种情况：无解、唯一解、无穷解将变为：无解、唯一解与解不唯一。