Any algorithm for "Flip all" (Light Out) game? [duplicate]

This question already has answers here: Lights out game algorithm (4 answers) Closed 2 years ago.

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.

OK, after read some answers and comments (a开发者_如何学Cnd have a quick look at Light out game), I expand my question:

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)?

---

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:

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

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.

---

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.)

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*.