algorithm - Lights out puzzle : what is this pro. blem调用，如何解决呢？ (网格)

Question

我有 MATRIX(m*n) 填充 bool 值(0 或 1)

当我们将 x,y 定位在位置附近时，中心将反转 (x,y),(x+1,y),(x-1,y),(x,y+1),(x,y- 1)

我们必须按下某个位置，使其转换为我们想要的某个矩阵

11111                   1-111                   1-1-1                  1-1-1
11111   press(2,2)->    ---11    press(2,4)->   --1--   press(3,2)->   -11--
11111                   1-111                   1-1-1                  -1--1
11111                   11111                   11111                  1-111

这个问题可以使用排列，但它太慢了 O(2^(n*m)) 我们可以制定一些条件使其更快，但对我来说它仍然很慢。

你能告诉我这个问题的名称是什么吗？它的算法是否比排列更好？

Answer 1

这叫做 Lights Out Puzzle .

除了排列算法之外，您还可以使用高斯消去法解决问题，如 this 的答案中所述。问题和上面的 Wolfram Alpha 链接。基本思想是建立一个代表所有可能按下的矩阵和一个代表“灯”( bool 值)的列向量，并解决以获得一组按下以将所有 bool 值设置为假(熄灯)。您可以调整它来解决任意状态，只需翻转列向量中的 bool 值，以获得您想要保持亮起的灯。