“Flip all”（Light Out）游戏的任何算法？
在这个游戏中： http ： //www.mathsisfun.com/games/allout.html求解function可以解决任何情况，无论你如何“滥用”原始板。 请告诉我解决这个游戏的算法。 我试着思考了几天，但仍然没有找到解决所有案例的线索。
好的，在阅读了一些答案和评论后（并快速浏览一下Light out游戏），我扩展了我的问题：
如果我扩大网格的大小（比如25×25），游戏会有所不同吗？ 在可接受的时间内（<2s）仍然有任何可能的算法来解决任何情况？
这个游戏通常被称为Lights Out，并且有许多优雅的解决方案，所有解决方案都基于一些标准但有些高级的数学。 我不会在这里描述它们，但如果你有点谷歌，你可以找到各种解释，从简单的程序到转换为线性代数或群论。 一些链接：
http://www.hamusutaa.com/pilot/solution.html
http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf
http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf
编辑 ：回复：你的第二个问题。 我发布的第二个链接中提供的算法可以在O（n ^ 6）时间内解决nxn板，这意味着您应该能够快速求解25 x 25板。
有一种众所周知的方法可以解决这个问题。 设x_1，…，x_n是对应于是否按下第n个按钮作为解的一部分的变量，并让a_1，…，a_n为初始状态。
假设您正在解决3×3问题，并且变量设置如下：
x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9 这个初始状态是：
a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9
现在，您可以写下解决方案必须满足的一些方程式（在算术模2中）。 它基本上编码了关于哪些开关导致特定灯光切换的规则。
a_1 = x_1 + x_2 + x_4 a_2 = x_1 + x_2 + x_3 + x_5 ... a_5 = x_2 + x_4 + x_5 + x_6 + x_8 ... a_9 = x_6 + x_8 + x_9
现在你可以使用高斯消元法来解决这组联立方程。 因为你在算术模2中工作，它实际上比实数上的联立方程更容易。 例如，要消除第二个等式中的x_1，只需将第一个等式添加到其中即可。
a_1 + a_2 = (x_1 + x_2 + x_4) + (x_1 + x_2 + x_3 + x_5) = x_3 + x_4 + x_5
具体来说，这是算术模2中的高斯消元算法：
- 选择一个带有x_1的等式。 将其命名为E_1。
- 将E_1添加到其他每个未命名的等式中，其中包含x_1。
- 重复x_2，x_3，….，x_n。
现在，E_n是仅包含x_n的等式。 您可以将从此获得的x_n的值替换为之前的等式。 重复E_ {n-1}，…，E_1。
总的来说，这解决了O（n ^ 3）操作中的问题。
这是一些代码。
class Unsolvable(Exception): pass def switches(vs): n, m = len(vs), len(vs[0]) eqs = [] for i in xrange(n): for j in xrange(m): eq = set() for d in xrange(-1, 2): if 0 <= i+d < n: eq.add((i+d)*m+j) if d != 0 and 0 <= j+d < m: eq.add(i*m+j+d) eqs.append([vs[i][j], eq]) N = len(eqs) for i in xrange(N): for j in xrange(i, N): if i in eqs[j][1]: eqs[i], eqs[j] = eqs[j], eqs[i] break else: raise Unsolvable() for j in xrange(i+1, N): if i in eqs[j][1]: eqs[j][0] ^= eqs[i][0] eqs[j][1] ^= eqs[i][1] for i in xrange(N-1, -1, -1): for j in xrange(i): if i in eqs[j][1]: eqs[j][0] ^= eqs[i][0] eqs[j][1] ^= eqs[i][1] return [(i//m,i%m) for i, eq in enumerate(eqs) if eq[0]] print switches(([1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 0]))
你一次给它一个初始状态。 它返回您需要按下的开关以关闭所有灯。
这可以解决我的笔记本电脑上不到半秒的50x50问题。
像大多数AI“游戏”问题一样，有一个通用的方法：
实现一个树结构，其中每个节点都是游戏状态，状态子节点表示这些状态之间的转换。
要么这样做作为广度优先搜索（深度优先，如果你记录你已经看到的过去状态并拒绝重新访问它们，并且你不关心找到最佳解决方案）或者想出一个乐观的启发式，允许您使用A *。 我能想到的一个非常糟糕的启发式是“需要翻转才能赢得拼图的圆圈数除以5”。 我不确定是否有更好的; 我有兴趣听听人们对此的意见（请注意，它必须是乐观的，也就是说，启发式方法永远无法计算所需的移动次数。）
进入更多细节是有点傻，因为这是一个很大的话题，除此之外，如果你知道如何进行广度优先搜索或A *，这很简单。