7

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

Luke Vo
  • 17,859
  • 21
  • 105
  • 181

2 Answers2

7

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.

Phil
  • 706
  • 5
  • 6
0

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

Jeremy
  • 5,365
  • 14
  • 51
  • 80
  • I still don't know how A* can solve this game (I haven't fully researched A* yet), the BFS seems possible, but... where to start? In 25x25 grid, it maybe impossible to fit phone memory with all cases. – Luke Vo Aug 27 '11 at 07:12
  • @W.N. Yeah, straight-up BFS won't be able to do 25x25, at least not elegantly. A* is doable if you can think of a more useful heuristic. If there isn't one (perhaps a reasonable heuristic would be solving a relaxed problem? For example, try solving a a version of this game where when you flip a square, it and the 4 around it flip, but only if they're the wrong color.) If even that won't do well enough, you'll have to consider this problem in particular and look at specific tricks you can use to solve it. – Jeremy Aug 27 '11 at 07:20