数学与计算机碰撞的地方

关灯游戏和扫雷问题

关灯问题

2005年1月lkrich7在csdn询问
有一个5\times 6的灯泡构成的矩阵,灯的开关规则是这样:当改变某盏灯的,状态时,这盏灯的上下左右相邻的灯的状态也随之改变。例如:

\begin{matrix} 0&1&1&0&1&0\\ 1&0&0&1&1&1\\ 0&0&1&0&0&1\\ 1&0&0&1&0&1\\ 0&1&1&1&0&0 \end{matrix}

当按下2行3列的开关时,状态变为:

可以注意到的是:
1.矩阵的状态与按开关的顺序无关
2.如果某个开关按下了两次,那么就相当于取消了第一次的操作,也就是说没有开关需要按超过1次

现在问题是:对于给定的初始状态,求出需要按哪些开关来完成游戏.
mathe在14年将问题转载到数学研发论坛
这个问题也经常在某些ACM在线测试中出现,比如poj1222

扫雷算法问题

2007年10月pavelalex在csdn提问
已知把雷区的雷布好了,每个格子数字都填好(可见),怎么通过这些数字把雷找出来?
zgg__提问: 那么地雷上填什么数字呢?
pavelalex要求:数字是它周围雷的数目。

二维递推数列求解

2007年11月goodenfeet在csdn提问
f(x,y)=f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1),求f(x,y)
其中,
f(x,0)=0,f(500,y)=50,f(x,500)=75,f(0,y)=100.
然后,
0\le x,y\le 500,x,y是正整数。
要求,
输入x,y,返回f(x,y)

算法分析

上面三个看似完全独立的问题,在数学上却密切相关。

关灯问题最初分析

mathe通过把关灯问题看成有限域F_2上的线性变换 来提出初步有效的解决方案:
把上面的矩阵看成有限域F_2上一个mn阶的向量X=(x_1,x_2,\dots,x_{m\times n})
对于位置k上的开关,它将变化最多5个位置的开关,对应一个向量
C_k=(0,0,\dots,1,0,\dots,1,\dots,0), 其中开关状态改变的位置为1,开关状态不改变的位置为0。
对于初始向量X=(x_1,x_2,\dots,x_{m\times n}),使用了开关C_k后,状态会变成 X+C_k(\mod 2), 也就是在F_2上做一次加法运算。
所以对初始向量X,我们需要选择一系列的k_1,k_2,\dots,k_s使得
X+C_{k_1}+C_{k_2}+\dots+C_{k_s}(\mod 2)=O=(0,0,0,\dots,0)
我们可以同样构造一个0,1向量Y,使得,如果位置k出现在k_1,k_2,\dots,k_s中,那么Y
在位置k的值是1,不然是0,这样,我们就可以将上面公式写成F_2上的矩阵形式X+YC(\mod 2)=O
其中C=(C_1^{\prime} C_2^{\prime} \dots C_{m\times n}^{\prime})^{\prime}
也就是C是由这mn个行向量构成的矩阵,第k行就是向量C_k
在二阶域上,加和减是相同的,也就是上面的方程等价于YC(\mod 2)=X,其中C,X已知,求Y。
我们可以直接在二阶域上用高斯消元法求解(注意加减是\mod 2的,对应计算机上的异或运算),
其中,如果C可逆,解是唯一的,如果C不可逆,解可能不存在,也可能不唯一。
如果解不唯一时,这时解的数目同C的秩有关系,比较有意思的是,如果我们记f(n,2x)是n次第二类切皮雪夫多项式,
那么gcd(f(m,x)(\mod 2),f(n,1-x)(\mod 2))的次数就是C的自由度(也就是矩阵的阶数减去秩)。

而这里C是一个分块三对角阵,我们可以使用追逐法求解,时间复杂度可以只有O(n^3)

mathe提供了一个C程序 , 时间复杂度为O(n^4),这是因为其中稀疏矩阵的乘法没有优化。

必然有方案关闭所有灯

在网络上,mathe还找到一个俄国人的一个证明:如果开始所有的灯都是开的,那么必然存在一种方案将所有的灯关闭.这个证明用到线性代数知识:

Puzzle 2: for this problem, we are giving up the detailed information about how the lights are connected. We are left knowing only that the connections are reflexive and symmetric, and that our task is to go from all lights ON to all lights OFF. Lossers gives a short explanation of how to see that this is so. First, we define the obvious matrix A with 1’s indicating which switches control which lights. The matrix is symmetric and has 1’s on its diagonal.

Now it’s equivalent to show that there is some strategy x of button pushing that can go from all lights OFF to all lights ON. But that’s just asking if there is a vector x such that

A x = d,
where d is the vector of all 1’s. That is equivalent to asking if d is in the column space of A. And that is equivalent to asking if the “perpendicular space” of A^{\prime} is contained in the “perpendicular space” of d. In other words, it is enough to show that A^{\prime}x=0 implies d^{\prime}x=0.

So let x be any vector in the perpendicular space of A^{\prime}. Then

\sum_{i=1}^N x_i A_{i,j} = 0 for all j. This implies \sum_{j=1}^N \sum_{i=1}^N x_i A_{i,j} x_j = 0,

Now we know that A is symmetric (assumption 2). Therefore, in the preceding sum, let us consider, for distinct i and j every pair of terms

x_i A_{i,j} x_j + x_j A_{j,i} x_i = ( A_{i,j} + A_{j,i} ) x_i x_j = 2 A_{i,j} x_i x_j = 0
because we are working in arithmetic module 2! Therefore, all the offdiagonal terms pair up and drop out.

Our sum now only involves the diagonal terms:

\sum_{i=1}^N x_i^2 A_{i,i} = 0
Now A_{i,i} = 1, because the light-switch relationship is reflexive (assumption 1), and d_i = 1 too, so in the sum, we can replace A_{i,i} by d_i. Moreover, we know that x_i^2=x_i, because x_i is either 0 or 1. Therefore, we now have
\sum_{i=1}^N x_i d_i = 0.

Hence x is in the perpendicular space of d. This means d is in the column space of A, so a button strategy exists that turns a set of “off” lights all “on”, and the same strategy will turn a set of “on” lights all “off”.

扫雷的进一步分析

对于m\times n阶雷区
我们记I为n阶单位矩阵
B为一个n阶矩阵,所有同主对角线相邻的位置是1(不包含主对角线),其余位置都是0,比如对于n=4,B如下
0100
1010
0101
0010
那么,原题目写成矩阵形式,所有方程系数构成如下mn阶矩阵

\begin{bmatrix} B&I+B&0&0&\dots&0&0&0\\ I+B&B&I+B&0&\dots&0&0&0\\ 0&I+B&B&I+B&\dots&0&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&0&0&\dots&0&I+B&B \end{bmatrix}

当然如果这个方阵可逆,那么问题的解唯一.
f(n,x)n第二类切皮雪夫多项式
f(0,x)=1,
f(1,x)=2x
f(2,x)=4x^2 – 1
另多项式:
g(a,b)=f(m,\frac a{2b})b^m
那么上面矩阵同矩阵g(B,I+B)可逆性相同.
也就是我们只要判断g(B,I+B)是否可逆就可以判断问题的解是否唯一了.
如果修改题目将周围理解成只有上下左右,那么上面分析中的I+B替换成I就可以了.
对于m=1, g(a,b)=a, 所以g(B,I+B)=B=0 不可逆.实际上1\times 1的情况解就是不唯一的.
对于m=2, g(a,b)=a^2-b^2, g(B,I+B)=-I-2B,通过切皮雪夫多项式的行列式形式可以知道
    \det(g(B,I+B))=(-2)^n f(n,\frac 14),
通过切皮雪夫多项式的三角函数形式可以知道上面值非0.
所以对于两行或两列的情况解都唯一.
对于m=3, g(a,b)=a^3-2ab^2, g(B,I+B)=B^3-2B(I+B)^2=-2B-4B^2-B^3
这个就比较难分析了.但是我们知道 B|g(B,I+B)
但是\det(B)=f(n,0)在n为奇数的时候是0.
实际上,对于m和n都是奇数的情况,总是有B|g(B,I+B),而且\det(B)=f(n,0)=0,所以\det(g(B,I+B))=0.
也就是说,我们证明了在m,n都是奇数的情况,上面方程不可逆,解可能不唯一(但是没有证明解必然不唯一,毕竟挖雷中要求所有数字都是0,1,这个解方程是无法限制的).
但是对于m,n至少有一个数是偶数时,我们还没有很好的结果.

我们再考虑n+1不被3整除的情况:
由于\det(I+B)=f(n,\frac12),根据切皮雪夫多项式的三角函数形式可以知道这个值只有再3|n+1时为0,
所以n+1不被3整除时,I+B可逆,这时\det(g(B,I+B))=\det((I+B)^m)\det(f(m, \frac12B(I+B)^{-1})).
上面第一项非0,而对于第二项,如果对于B的某个特征值u,
    f(m,\frac12\frac u{1+u})=0,那么它为0,不然必然非0.
根据切皮雪夫多项式的三角函数:设x=\cos(t),那么f(n,x)=\frac{\sin((n+1)t)}{\sin(t)},
得到使f(n,x)=0x\cos(\frac{k\pi}{n+1}),
所以B的所有特征值是2\cos(\frac{k\pi}{n+1})
所以只有对于存在k_1,k_2使得\frac{2\cos(\frac{k_1\pi}{n+1})}{1+2\cos(\frac{k_1\pi}{n+1})} = 2\cos(\frac{k_2\pi}{m+1})的情况下,上面第二项才为0.
分析对于什么样的m,n上面式子成立也是挺难的,不过计算机验算很简单.

上面的分析过程给出了一个这道题目在解唯一时比较有效的解法,
就是解方程,方程对应矩阵是

对于1+u=0(也就是特征值-1),结果就是f(m,-1)展开的第一项,当然不是0.
对于1+u\ne 0,g(u,1+u)=f(m,\frac u{2(1+u)}),所以我们实际上还是可以用判断式\frac{2\cos(\frac{k_1\pi}{n+1})}{1+2\cos(\frac{k_1\pi}{n+1})}=2\cos(\frac{k_2\pi}{m+1})来判断.

所以判断方程中矩阵是否可逆,我们可以用如下方法.
i)如果m,n都是奇数,不可逆.
ii)不然,对于x=\cos(\frac{k\pi}{n+1}), (k=1,2,\dots,n)
    计算\sin((m+1)\cos^{-1}(\frac x{1+2x})),如果这个值为0,矩阵不可逆; 不然,矩阵可逆.
当然第二步只能近似计算.

还有一个有意思的结论:
如果\det(g(B,I+B))是奇数, 那么我们只要知道每个格子周围的雷的总数的奇偶性就可以唯一确定结果了.
比如对于上面列出的4\times 5的例子,可以算出\det(g(B,I+B))是奇数 (模2计算就可以了),
所以对于这个例子,我们只要知道雷数的奇偶性就可以唯一确定结果了.
只知道雷的总数的奇偶性的问题关灯游戏问题就几乎一模一样了,除了每次关灯影响的灯的数目不同.
而上面解法的思想也来源于关灯游戏的解法。 只是对于关灯游戏,所有计算都是模2运算,计算更加方便.

二维递推数列的求解

关于这个递推数列,mathe首先想到,记a=f(x,0)=0, b= f(0,y)=100, c=f(x,500)=75, d= f(500,y)=50,
定义,B和I都是499\times 499阶方阵,其中空格位置为0, G是一个249001\times 249001阶方阵(249001=499\times 499),写成分块矩阵形式.空格位置也都是0
那么这道题目写成方程形式就是解方程Gx=r, 这道题目可以用追赶法求解,复杂度为O(n^4),这里n=499,基本上是可行的。

随后mathe发现:
对于n\times n的问题(在这个题目里面n=499)
上面问题存在唯一解的充分必要条件是
对于任意的整数k_1,k_2 0\lt k_1\lt k_2\lt n+1, 有
\cos(\frac{k_1\pi}{n+1})-\cos(\frac{k_2\pi}{n+1})\ne \frac12.
而对于这个题目,由于k_1=300,k_2=400时会不满足上面条件,也就是
\cos(\frac35\pi)-\cos(\frac45\pi)=\frac12, 所以方程不一定有解,而且即使有解的时候解也不会唯一。
随后,mathe给出了改自关灯问题的代码 ,连里面的注释都还是关灯问题的。

此后mathe发现,这个题目可以用O(n^2\log(n))的算法达到,
而其中离散正弦变换竟然可以得到应用。也许,这个题目一开始就应该用傅立叶变换来分析。
还是采用前面的记号,分别用a,b,c,d代替四条边界上的取值(其实每条边界上不需要要求所有点的初始值相同)。
首先我们可以发现,这个题目满足可加性。
我们可以先计算出(a,b,c,d)=(a,0,0,0)的解,然后计算(a,b,c,d)=(0,b,0,0)的解,然后再计算另外两个只有一条边界为0的解。算出来后,将4个解对应位置相加,就是所求的解了。所以我们可以先只分析(0,0,0,d)这组情况。
记函数f(1,x)=1,f(2,x)=x, f(n+1,x)=x f(n,x)-f(n-1,x),
那么f(n,2x)就是第二类切皮雪夫多项式.
记矩阵T为一个n阶对称阵,其中,
T_{i,j}=\sqrt(\frac2n)\sin(\frac{ij\pi}{n+1}), (1\le i\le n,1\le j\le n).
可以知道T是正交阵, 而且对于任意一个长度为n的向量X, TX其实就是X的离散正弦变换,而计算离散正弦变换可以有O(n\log(n))的快速算法。

现在回到题目,n=499.
由于a=b=c=0,所以题目中r_1,r_2,\dots,r_{n-1}都是0,只有r_n=(-d,\dots,-d)不等于0. (其实对于这个边界条件,可以直接求解不同的位置不同的情况,只要修改r_n的值就可以了).
所以得到上面递推式中u_1=u_2=\dots=u_n=0, u_{n+1}=r_n,而V_{n+1}=f(n,-B),所以我们得到
f(n,-B)x_1=-r_n

TBT=diag{2\cos(1\times\frac{\pi}{n+1})-1,2\cos(2\times\frac{\pi}{n+1})-1,\dots,2\cos(n\times\frac{\pi}{n+1})-1}
所以, 如果假设Tx_k=y_k, Tr_n=-R_n,
那么我们得到
f(n,(-2\cos(\frac{h\pi}{n+1})+1)y_1(h)=-R_n(h),
其中y_1(h)R_n(h)分别表示这两个向量的第h项。
所以我们可以
i)首先计算r_n的离散正弦变换R_n. (如果所有d相同,我们可以发现,R_n的所有奇数项都是0)
ii)计算f(n, -2\cos(\frac{h\pi}{n+1})+1), (h=1,2,\dots,n)
    这个可以采用f(n,.)的迭代式计算,计算每个时间复杂度为O(n),总共O(n^2)
iii)解出y_1,如果对于某个h,对应f(n,-2\cos(\frac{h\pi}{n+1})+1)=0, 而R_h\ne 0,那么方程无解。
            而如果对于f(n,-2\cos(\frac{h\pi}{n+1})+1)=0h都有,R_h=0,那么方程有无穷个解,这时y_1(h)可以任意取.
        而对于f(n,-2\cos(\frac{h\pi}{n+1})+1)=0的情况,不论那种情况,取y_1(h)=0都是x_1的最小二乘解。
        而在我们的题目中,d这条边界对应所有数据相同,所以对于h是偶数的情况R_n才为0.
        而对于n=499,我们发现h=100,200,300,400的情况f(n,-2\cos(\frac{h\pi}{n+1})+1)=0. 所以我们知道,对于这个题目,有无穷的解,但是我们可以取y_1(100)=y_1(200)=y_1(300)=y_1(400)=0,求出最小二乘解。
iv)通过再次离散正弦变换(逆变换)计算出x_1
上面部分计算x_1总共花费了O(n^2)的时间。
此后,我们就可以通过方程
  x_k=f(k-1,-B)x_1来计算x_k
同样做离散正弦变换,上面等式变成
  y_k(h)=f(k-1,-2\cos(\frac{h\pi}{n+1})+1)y_1(h)
而其中f(k-1,-2\cos(\frac{h\pi}{n+1})+1在ii)中已经产生,直接使用就可以解出y_k.
所以最后我们只要在通过n-1次离散正弦变换(逆变换)可以计算出x_2,x_3,\dots,x_n.
这一步需要花费O(n\times n\log(n))的时间,
所以总共时间复杂度O(n^2\log(n)).
点击可以下载对应的C代码 .

扫雷问题深入分析

通过上面二维递推数列的分析,可以知道,扫雷问题也可以用O(nm\log(n+m))的算法达到。
对于雷区最终和数据矩阵假设为a(i,j),
而每个格子用x(i,j)表示,0表示无雷,1表示有雷,
分别用A和X表示a和x的二维离散正弦变换(也就是先各行做离散正弦变换,再各列做变换)。
那么可以有:
((2\cos(\frac{i\pi}{n+1})+1)(2\cos(\frac{j\pi}{m+1})+1)-1)X(i,j)=A(i,j).
如果左边系数总不是0,马上就可以解出X(i,j),
不然,必然要求对应的A(i,j)也是0,这时,对应X(i,j)可以取任意值,这是一个可变参数。
根据前面的一个分析,我们知道在m,n不超过500的范围内,最多只有m=n都是奇数的情况有可能有一项系数是0,
也就是说,这个可变参数最多只有一个。
所以我们得到了x(i,j)的二维离散正弦变换,其中最多一个可变参数。
然后我们对X做逆变换,变换结果可以写成:
u(i,j)+t\times v(i,j),
其中t就是那个可变参数.
而且矩阵v很特殊,它每个元素都不是0。
由于u(i,j)+t\times v(i,j)总是0或1,
我们只要任意选一个位置,分别让这个位置取0或1就可以得到一个t的值,
然后带入求出其他位置的值,如果对应值不是0和1,说明是非法解。
这个也正好检验了前面zgg__提到的只需要蒙一次的过程,上面分析说明对于任何局面,我们最多需要蒙一次。
而最终的解也可以证明是唯一的。如果不唯一,那么说明存在两个不同的t: t_1,t_2使得
u(i,j)+t_1\times v(i,j)u(i,j)+t_2\times v(i,j)都是0或1,
也就是(t_1-t_2)v(i,j)总是0,-1,1.
由于v(i,j)总是非0t_1\ne t_2,所以(t_1-t_2)v(i,j)都只能是-1,1,
也就是说,|v(i,j)|必须是常数.
而矩阵v的值是有解析形式的,只有mn都不超过2的时候,才会有|v(i,j)|是常数,
而我们前面说过只有m=n而且是奇数时才出现待定系数。所以总共我们就得出m=n=1的这种特殊情况解不唯一(实际上这种情况的确解不唯一).

发现前面我写的判断等式
\frac{2\cos(\frac{k_1\pi}{n+1})}{1+2\cos(\frac{k_1\pi}{n+1})}=2\cos(\frac{k_2\pi}{m+1})
无解的代码写错了,实际上,对于很多m,n都是有解的。
比如4×4,4×9,4×19等都有解。
但是500以内,最多都只有3组解。所以在500以内,最差情况要穷举8种情况。(试验3次)
那个额外的解就是
(2\cos(\frac{\pi}5)+1)(2\cos(\frac{3\pi}5)+1)=1.

有一道关于正三十边形的对角线 可将其为多少部分的题目,
关于这个题目,berkeley大学的Bjorn Poonen给出了一个公式,在其这篇文章中,他分析了所有形如
u_1+u_2+\dots+u_k=0(其中u_1,u_2,\dots,u_k都是1的单位根,也就是有某个整数h_i使得u_i^{h_i}=1)的解。
通过他的文章的结论,得知所有最多8项的这样的表达式中单位根的幂总是7,5,3,2或它们的乘积,
而我上面的等式可以转化为长度为8的这样的和。
由于我已经搜索了500以内的范围,所以不会有其他解了。
也就是所有可能为0的系数已经全部得出。

所以最后的结论是,
一般情况只有唯一解,
如果m和n都是奇数,那么,
((2\cos(\frac{i\pi}{n+1})+1)(2\cos(\frac{j\pi}{m+1})+1)-1)中会有一项为0, 其中(i=\frac{n+1}2, j=\frac{m+1}2).
如果m+1n+1都是5的倍数,那么还有另外两项是0,
(i=\frac{m+1}5, j=\frac{3(n+1)}5i=\frac{3(m+1)}5, j=\frac{n+1}5),
最多有3个自由参数,也就是最多枚举8种情况就可以了。

点击下载对应C代码

2014年zhouguang 将关灯问题整理成一个pdf文件 ,内容相当不错。

OEIS 相关信息

相关数据结果提交到了oeis, 有
正方形关灯问题中唯一解的尺寸 A076437
正方形关灯问题最优解A075464
正方形关灯问题不等价解数目A075463
关灯问题矩阵的秩问题A159257

Next Post

Previous Post

Leave a Reply

© 2020 数学研发论坛

Theme by Anders Norén