翻转点灯谜题（IBM Ponder This Apr 2023）

, 2023-08-22

, 共 1776 字 , 共阅读 7 次

一个正方形棋盘，每个格子里都有一个灯泡，有些亮着有些没亮。我们每次可以选择其中一个熄灭的灯泡，点亮它的同时，翻转同行和同列的其它所有灯泡（亮着的关闭，熄灭的打开）。

问从任意给定的状态，求操作，使得最后将所有的灯泡打开。

如果操作不要求选定熄灭的灯泡，问题就相当简单了。

假设灯泡状态是wi,jwi,j， 0 表示打开， 1 表示熄灭（注意和题目给的表示方法相反）。我们假设对(i,j)(i,j)的灯泡做的操作为si,si,，也是 0 ， 1 变量（显然此时操作顺序没有关系，而且对于同一个灯泡操作多次无意义）。那么我们有方程：

wi,j=si,j+∑k≠isk,j+∑k≤jsi,k(1)(1)wi,j=si,j+∑k≠isk,j+∑k≤jsi,k

这里的加法是基于 0 ， 1 的异或。当棋盘边长为偶数时，我们可以直接猜出其表达式解：

si,j=wi,j+∑k≠iwk,j+∑k≤jwi,k(2)(2)si,j=wi,j+∑k≠iwk,j+∑k≤jwi,k

此时，对偶数大小的棋盘，我们直接解决了问题。

另一个问题：奇数大小的棋盘怎么弄？答案是，奇数的时候，我们不一定能打开所有的灯。我们记：

WRi=∑jwi,j(3)(3)WRi=∑jwi,j

WCj=∑iwi,j(4)(4)WCj=∑iwi,j

SRi=∑jsi,j(5)(5)SRi=∑jsi,j

SCj=∑isi,j(6)(6)SCj=∑isi,j

S=∑i,jsi,j(7)(7)S=∑i,jsi,j

那么上面的条件 11可以写作：

wi,j=si,j+SRi+SCj(8)(8)wi,j=si,j+SRi+SCj

对上面式子的jj求和，可得：

RWi=(n+1)SRi+∑jSCj=S(9)(9)RWi=(n+1)SRi+∑jSCj=S

同理对ii求和，可得：

RWj=S(10)(10)RWj=S

这意味着原来状态每一行每一列，其状态之和（在 1,0 的 mod 2 加法下）相等。直观地说，要么每一行每一列熄灭的灯都是偶数个，要么每一行每一列熄灭的等都是奇数个。

直接从单次操作上也可以看出，每次操作都改变了每一行每一列熄灭灯个数的奇偶性。但最终状态每一行每一列都是偶数。所以最初状态的奇偶性也必定相同。

这个条件也是充分的。因为我们先不管第一行第一列，对剩下的(n−1)×(n−1)(n−1)×(n−1)$棋盘做操作，可以将这些灯全部打开。这时候第一行和第一列的灯要么全是打开的（已经 OK ），要么全是熄灭的，此时对第一行第一个灯做一次操作即可。

不过这种解也不是唯一的。上面的操作选择任何一行一列作为例外，都能得到一组解。

但如果操作要求每次选定熄灭的灯泡，这时候问题就复杂了。显然，上述的s_{i, j}仍可能是一个可行的解，我们需要谨慎地安排先后顺序，使得每次选择系列的灯泡。直接暴力搜索的代码附在后面。

可能存在某种特殊的状态，使得需要某个灯泡操作两次或多次，这就不在上面的搜索路径。问题就变得复杂很多。

Q. E. D.

Recommend