“Flip all”（灯泡游戏）有哪些算法？

Question

在这个游戏中：http://www.mathsisfun.com/games/allout.html

无论你如何“滥用”原始板块，solve函数都可以解决任何情况。请告诉我解决此游戏的算法。我已经尝试思考了数天，但仍然没有找到解决所有情况的线索。

好的，在阅读一些答案和评论后（并快速查看Light out游戏），我扩展了我的问题：

如果我扩大网格的大小（例如到25x25），游戏是否会有所不同？仍然有可能使用任何算法以可接受的时间（＜2秒）解决吗？

- Luke Vo

---

请参阅灭灯游戏。 - trashgod

Answer 1

这个游戏更为人所知的名字是“熄灯游戏”，有许多优雅的解决方案，都基于一些标准但有些高级的数学。我不会在此介绍所有解决方案，但如果你搜索一下，可以找到各种各样的解释，从简单的过程到线性代数或群论的转换。以下是一些链接：

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）时间内解决n x n棋盘，这意味着你应该能够快速解决一个25 x 25棋盘。

- Phil

---

是的，我正在阅读，非常有趣！一旦我阅读完毕就会回来。 - Luke Vo

Answer 2

像大多数AI“游戏”问题一样，有一个通用的方法：

实现一个树形结构，其中每个节点都是游戏状态，状态的子节点表示这些状态之间的转换。

可以使用广度优先搜索（如果您保留了过去看到的状态的日志并拒绝重新访问它们，并且您不关心找到最佳解决方案，则深度优先搜索也可以），或者想出一个乐观的启发式算法，使您可以使用A*。我能想到的一个相当糟糕的启发式算法是“需要翻转以赢得谜题的圆圈数量除以5。”我不确定是否有更好的算法；我很想听听人们对此的意见（请注意，它必须是乐观的，即，启发式算法永远不能过度计算所需的移动次数。）

进一步详细说明有点愚蠢，因为这是一个如此庞大的主题，而且如果您知道如何进行广度优先搜索或A*，那么这非常简单。

- Jeremy

---

我仍然不知道A如何解决这个游戏（我还没有完全研究A），BFS似乎是可能的，但是...从哪里开始呢？在25x25的网格中，也许无法用所有情况来适应手机内存。 - Luke Vo

@W.N. Yeah, 直接的BFS在25x25的情况下可能不会很好地解决，至少不能算是优雅的解法。如果你能想到一个更有用的启发式方法，A*算法是可行的。如果没有的话（也许一个合理的启发式方法可以是解决一个简化的问题？例如，尝试解决这个游戏的一个版本，在这个版本中，当你翻转一个方块时，它和周围的4个方块也会翻转，但只有当它们颜色相反时才会翻转）。如果即使这样还无法达到足够好的效果，你就需要具体考虑这个特定问题，并寻找可以用来解决它的具体技巧。 - Jeremy