我正在寻找可以找到Lights Out game的解决方案的算法以最少的步数。我找到了使用高斯消元法的解决方案,但是这个解决方案正在寻找任何解决方案,不一定是最好的解决方案。
主要问题是,在侧面和角落的某些地方,如果单击,只有三到四个灯光会发生变化。没有它们,就可以在 O(n²) 内解决这个问题。我想过尝试角落和侧面这些地方的所有可能性,但 n 太大了。
有什么想法吗?
n - 边的大小。 n 最大为 10。
PS。我只是在寻找能够找到解决给定正方形所需的最少移动次数的解决方案,或者说这是不可能的。最佳答案
让高斯消元法返回跨越移动 -> 灯光线性变换的零空间的向量并不难。然后你可以在比 2^100 个元素小得多的空间上应用蛮力(我不认为有超过一百万个的可能性)。
关于algorithm - 熄灯游戏 - 最少步数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31959913/