求将N×N二进制网格转为全1的多项式时间最小翻转算法

核心结论 #

对于N≥4的二进制网格翻转问题，存在多项式时间算法，可完成两项核心任务：

• 判定给定初始状态是否能转化为全1；
• 若有解，找出点击次数最少的最短序列。

问题的数学模型（延续你的核心观察） #

你对问题的底层数学抽象完全正确：

• 点击操作等价于当前网格与对应十字形1网格的异或（XOR）运算；
• 同一单元格点击两次等价于未点击（a XOR a = 0）；
• 点击顺序不影响结果（异或满足结合律），因此点击集合可表示为一个N×N二进制网格（1表示点击，0表示不点击）。

基于此，问题可转化为二元域GF(2)上的线性方程组求解问题：
设初始网格为A（A[i][j]为0或1），点击集合为X（X[i][j]为0或1），全1网格为U。我们需要满足：
A XOR (X的十字形影响叠加) = U
转化为GF(2)的线性方程（异或等价于GF(2)中的模2加法）：
对于每个格子(i,j)，有：
A[i][j] + X[i][j] + X[i-1][j] + X[i+1][j] + X[i][j-1] + X[i][j+1] = 1
（边界格子需去掉不存在的相邻项，加法为GF(2)中的模2加法）

N≥4时的多项式解法步骤 #

1. 高斯消元判定解的存在性 #

将上述n²个方程组成的方程组在GF(2)上执行高斯消元：

• 时间复杂度为O((n²)^3) = O(n^6)，属于多项式时间范畴；
• 消元后可直接判定：若增广矩阵的秩大于系数矩阵的秩，则该初始状态无解；否则存在解。

2. 寻找最短点击序列 #

若方程组有解，解空间由一个特解加上齐次方程组的解空间构成。要找到点击次数最少的解（即X中1的个数最少）：

• 先求出齐次方程组的线性基；
• 从特解出发，尝试用线性基中的向量组合迭代减少1的个数，该过程可在多项式时间内完成（线性基的大小不超过n²）。

为什么N≤3的算法在N≥4时失效 #

N≤3时，对应的系数矩阵是满秩矩阵，方程组有唯一解，因此所有初始状态都能转化为全1，你之前的算法可直接找到唯一解（即最优解）。但当N≥4时：

• 系数矩阵的秩小于n²，齐次方程组存在非零解；
• 这意味着部分初始状态无法转化为全1（无解），且有解时可能存在多个有效点击集合，需要从中筛选最优解，因此依赖“全状态可达”的旧算法不再适用。

补充说明 #

你发现的1->(1->(1->(1->A))) = A（N≤3）本质是因为N≤3时系数矩阵存在逆矩阵，四次作用等价于单位操作；但N≥4时系数矩阵不可逆，该性质不再成立。

内容的提问来源于stack exchange，提问作者bad-at-math