lightsout game and its solution

游戏描述

---

Lightsout 游戏是本人在上高等线性代数课程时，邵老师提到的一个有趣的例子。以前邵老师的个人网页上有这个游戏，但是可惜现在他的个人网页已经过期了，无法再在上面玩了，我自己使用 html + javascript 写了一个极其简陋的关灯游戏

游戏的规则非常简单：点击一盏灯，它自己以及与它相邻的灯都会改变状态，即亮的变为暗的，暗的变为亮的，当所有灯都被点亮时，游戏胜利

以下为 $5 \times 5$ 地图的解法（不唯一）

建模

---

这个游戏可以用数学语言描述。我们很容易知道这个游戏的几个简单性质

• 点灯的顺序对结果是没有影响的，我们只关心点了哪些灯
• 对一盏灯点击偶数次相当于没有操作，点击奇数次相当于点了一次
• 当一盏灯和它相邻的点被点击的次数之和为奇数时，它就被点亮；否则，依然是暗的

于是，我们可以用 $1,\ 0$ 来表示某盏灯 $x_i$ 是否被点击（$1$ 表示被点击, $0$ 表示没有点击），我们的目标是让每一盏灯及它周围的灯被点击次数之和均为奇数。假设我们在玩 $2\times 2$ 的地图，则问题可表示为

$\left.\begin{aligned} x_1+x_2+x_3\\ x_1+x_2+x_4\\ x_1+x_3+x_4\\ x_2+x_3+x_4 \end{aligned} \right\} is\ odd$

“为奇数”这个问题就很难求解，因为奇数有很多，如果我们奇数可能的取值代进去，当问题的规模很大时，会有指数级的计算复杂度。如果熟悉布尔运算的话，很容易可以知道这与异或操作其实是等价的

• 奇数个 $1$ 进行异或结果是 $1$，否则为 $0$

所以问题又可以表示为

$\left\{\begin{aligned} 1\cdot x_1\wedge 1\cdot x_2\wedge 1\cdot x_3\wedge 0\cdot x_4=1\\ 1\cdot x_1\wedge 1\cdot x_2\wedge 0\cdot x_3\wedge 1\cdot x_4=1\\ 1\cdot x_1\wedge 0\cdot x_2\wedge 1\cdot x_3\wedge 1\cdot x_4=1\\ 0\cdot x_4\wedge 1\cdot x_2\wedge 1\cdot x_3\wedge 1\cdot x_4=1 \end{aligned} \right.$

到这里为止，对问题的建模就完成了。

求解

---

最后的问题与求解线性方程组的问题十分相近，差别无非是将 + 变成 $\wedge$ ，那么道理上也可以用求解线性方程组的方法来求解这个问题。由于 $x$ 的取值和系数均为 $1,\ 0$，我们可以用高斯消元法相同的思路来做，而不会引入误差。

我们回忆一下高斯消元法的主要思路：

• 构造增广矩阵
• 对于第 $i$ 列，从第 $i$ 行开始找第一个非零元素，将它移到第 $i$ 行，并对第 $i+1$ 到 $n$ 行，减去第 $i$ 行的倍数，使得每一行的第 $i$ 列元素为 $0$。最终可以得到一个上三角阵
• 对于上三角矩阵是很容易求解的，只要一直把后面的解代到上面，每次求解一个一元方程即可

可以看出，和求解线性方程组的问题相比，有两处操作需要做修正：

• 第二步的“减去第 $i$ 行的倍数”
• 第三步的“回代法”

将两处的地方合理地改为异或操作，直觉上就可以解决问题了。

先来看“减去第 $i$ 行的倍数”。若 $A_{ji}=0$($A_{ji}$ 表示第 $j$ 行第 $i$ 列的元素)，则不需要进行任何操作；否则 $A_{ji}=1$。“减”的作用是去除第 $i$ 行的操作，也就是将两行的操作加起来，等价于原来的操作。由异或的性质，很显然，只需要对应位置的元素做异或即可。举个例子，假设第 $i$ 行为 $1$, 第 $j$ 行也为 $1$, 那么相减后的操作为 $0$。

而“回代法”是在知道后面的操作的情况下，求解前一个操作。假设我们已知 $i+1$ 到 $n$ 的操作，来求第 $i$ 行，那么只需要将第 $i$ 行的状态异或与第 $i$ 盏灯相邻的灯的操作即可。

Matlab 代码

---

输入求解问题的规模 $m,\ n$，输出可视化的结果

function []=solve_xor(m,n)
	% generate matrix
    N=m*n;
    T1=diag(ones(m-1,1),1);
    T1=T1+T1'+eye(m);
    T2=diag(ones(n-1,1),1);
    T2=T2+T2'+eye(n);
    A=kron(T2,eye(m))+kron(eye(n),T1)-eye(N);
    b=ones(N,1);
    
	% solve
    for i=1:N
        for p=i:N
            if A(p,i)~=0
                break
            end
        end
        A([i p],:)=A([p i],:);
        b([i p])=b([p i]);
        for j=i+1:N
            if A(j,i)
                for k=i:N
                    A(j,k)=xor(A(j,k),A(i,k));
                end
                b(j)=xor(b(j),b(i));
            end
        end
    end
    for i=N:-1:2
        for j=i-1:-1:1
            b(j)=xor((A(j,i)&&b(i)),b(j));
        end
    end
    
    %displat
    b=reshape(b,m,n);
    imagesc(b);

输入 $m=5,\ n=5$，可以得到：

旋转一下，与前面给出的解法是一样的