n×n棋盘约束型打地鼠游戏求解算法及可解性问题

规则说明：n×n网格上的打地鼠游戏，初始状态部分位置有地鼠弹出；仅可击打当前已弹出的地鼠，击打后当前位置及上下左右相邻位置的状态翻转（地鼠变空洞，空洞变地鼠）；目标是将所有位置变为空洞。

问题1：是否存在多项式时间复杂度的求解算法？ #

答案是存在的。
这个问题本质可以转化为二元域（GF(2)，即0/1异或运算规则）下的线性方程组求解问题：

• 定义变量x[i][j]为0或1，代表是否击打(i,j)位置的地鼠
• 定义初始状态s[i][j]为1表示该位置初始有地鼠，0表示没有
• 翻转操作是异或操作，和击打顺序无关，要让最终所有位置都为0，对每个位置(i,j)都满足：s[i][j] XOR x[i][j] XOR x[i-1][j] XOR x[i+1][j] XOR x[i][j-1] XOR x[i][j+1] = 0（边界位置的不存在相邻项直接忽略）

对这个n²个变量、n²个方程的线性方程组用高斯消元求解，时间复杂度为O(n^6)，属于多项式时间范畴。如果利用网格的稀疏结构做优化，还可以把复杂度降到O(n³)，效率更高。
同时可证明，只要方程组存在解，就一定能找到符合「仅击打当前弹出地鼠」规则的操作顺序，不需要额外的指数级步骤验证合法性。

问题2：是否所有初始配置都存在合法求解路径？ #

答案是否定的，存在很多初始配置没有合法解。
我们可以用极小的2×2网格举反例：初始只有左上角有地鼠，其他三个位置都是空洞。代入上面的线性方程组可以直接推导得到矛盾，不存在满足条件的击打组合，自然也没有合法求解路径。
本质上这个问题的解空间是GF(2)下的线性子空间，只有当初始状态属于这个子空间时才有解，随机初始配置有相当概率不属于解空间，无法通关。

内容的提问来源于stack exchange，提问作者LeHalfW