java “全部翻转”（Light Out）游戏的任何算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7212966/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Any algorithm for "Flip all" (Light Out) game?
提问by Luke Vo
in this game: http://www.mathsisfun.com/games/allout.htmlThe solve function can solve any case, no matter how you "abuse" the original board. Please tell me the algorithm for solving this game. I have tried to think for days but still found no clue to solve all cases.
在这个游戏中：http: //www.mathsisfun.com/games/allout.html解决功能可以解决任何情况，无论你如何“滥用”原版。请告诉我解决这个游戏的算法。我已经尝试思考了几天，但仍然没有找到解决所有情况的线索。
OK, after read some answers and comments (and have a quick look at Light out game), I expand my question:
好的，在阅读了一些答案和评论（并快速查看 Light out 游戏）后，我扩展了我的问题：
Will the game different if I expand the size of the grid (like to 25x25)? Still any possible algorithm to solve anycase, in acceptabletime (< 2s)?
如果我扩大网格的大小（比如 25x25），游戏会有所不同吗？在可接受的时间内（< 2s），还有任何可能的算法来解决任何情况吗？
采纳答案by Phil
This game is more commonly known as Lights Out, and has a number of elegant solutions, all based in some standard but somewhat advanced mathematics. I won't describe them all here but if you Google a bit you can find all kinds of explanations varying from straightforward procedures to transformations into linear algebra or group theory. A few links:
这个游戏通常被称为 Lights Out，并且有许多优雅的解决方案，所有解决方案都基于一些标准但有点高级的数学。我不会在这里一一描述，但如果你谷歌一下，你可以找到各种解释，从简单的程序到线性代数或群论的转换。几个链接：
http://www.hamusutaa.com/pilot/solution.html
http://www.hamusutaa.com/pilot/solution.html
http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf
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
http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf
Edit: Re: your second question. The algorithm presented in the second link I posted can solve an n x n board in O(n^6) time, meaning you should be able to quickly solve a 25 x 25 board.
编辑：回复：你的第二个问题。我发布的第二个链接中提供的算法可以在 O(n^6) 时间内解决 nxn 板，这意味着您应该能够快速解决 25 x 25 板。
回答by Jeremy
Like most AI "game" problems, there's a general approach:
像大多数人工智能“游戏”问题一样，有一个通用的方法：
Implement a tree structure where each node is the game state and children of states represent transitions between those states.
实现一个树结构，其中每个节点都是游戏状态，状态的子节点代表这些状态之间的转换。
Either do this as a breadth-first search (depth-first OK if you keep a log of past states you've seen and refuse to revisit them, and you don't care about finding the optimal solution) or come up with an optimistic heuristic that allows you to use A*. A pretty-awful heuristic I can think of is "The number of circles that need to be flipped to win the puzzle, divided by 5." I'm not sure if there's a better one; I'd be interested in hearing people's input on this (Note that it has to be optimistic, that is, the heuristic can never OVER-calculate the number of moves needed.)
要么将此作为广度优先搜索（深度优先，如果您保留您所看到的过去状态的日志并拒绝重新访问它们，并且您不关心找到最佳解决方案）或提出一个乐观的启发式，允许您使用 A*。我能想到的一个非常糟糕的启发式方法是“赢得拼图需要翻转的圆圈数除以 5”。我不确定是否有更好的；我很想听听人们对此的意见（请注意，它必须是乐观的，也就是说，启发式算法永远不能过度计算所需的移动次数。）
Going into more detail is a little silly since this is such a big topic, and besides that, it's pretty simple if you know how to do a breadth-first search or A*.
深入细节有点愚蠢，因为这是一个如此大的话题，除此之外，如果您知道如何进行广度优先搜索或 A*，那就很简单了。
