任何算法＆QUOT;全部翻开＆QUOT; （光输出）游戏？ [英] Any algorithm for "Flip all" (Light Out) game?

问题描述

在本场比赛： http://www.mathsisfun.com/games/allout.html 该解决功能，可以解决任何情况下，不管你如何虐待原板。请告诉我该算法求解这个游戏。我试图想了好几天，但仍然没有发现任何线索来解决所有的情况。

in this game: http://www.mathsisfun.com/games/allout.html The 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.

确定，之后读了一些答案和注释（并有一个快速浏览一下轻了比赛），我展开我的问题：

将游戏不同，如果我扩大电网规模（如以25×25）？不过任何可能的算法来解决的任意的情况下，的在接受的时间（小于2秒）？

Will the game different if I expand the size of the grid (like to 25x25)? Still any possible algorithm to solve any case, in acceptable time (< 2s)?

推荐答案

这个游戏通常被称为熄灯，并拥有多项优雅的解决方案，都是基于一些标准，但有些高等数学。我不会描述他们都在这里，但如果你在Google上搜索了一下，你可以找到各种解释，从简单的程序，以转换成线性代数和群论改变。几个环节：

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:

<一个href="http://www.hamusutaa.com/pilot/solution.html">http://www.hamusutaa.com/pilot/solution.html

<一个href="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

<一个href="http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf">http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf

修改：回复：你的第二个问题。 psented在我张贴能解决的N×N板为O（n ^ 6）的时间，这意味着第二个链接的算法$ P $，你应该能够快速解决25×25板。

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.

这篇关于任何算法＆QUOT;全部翻开＆QUOT; （光输出）游戏？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！