2

The game consists of a 8-by-8 grid of lights, when the game starts, a random set of these lights are switched on. Pressing one of the lights will toggle it, and the four lights adjacent to it, on and off. Diagonal neighbours are not affected. The game provides a puzzle: given some initial configuration where some lights are on, some are off and some are unusable, the goal is to switch all the lights off, preferably in as few button presses as possible.

Can any one tell me an correct approach using iterative backtracking to solve this problem?

7lYNdYzwbY
  • 21
  • 2
  • You're going to need something a little more clever than backtracking to solve this problem because backtracking alone is going to be a brute-force search, which is far too slow. At the very least, you're going to need something to narrow down the search space and prevent cycles. – Beefster Dec 15 '17 at 20:35
  • I don't care about the performance. – 7lYNdYzwbY Dec 15 '17 at 20:36
  • 1
    According to [this](http://www.unf.edu/~wkloster/fibonacci/congnum.pdf), Lights Out is NP-complete, meaning it's hard to do better than a brute force search. If you need to find the optimal solution, that is guaranteed exponential complexity. – Beefster Dec 15 '17 at 20:43
  • @Beefster There's a polynomial-time algorithm for the problem of "is this board solvable?" The linked question seems to be about a minimization problem of "given an arbitrary graph representing connectivity, minimize the number of lights turned on," which is a slightly different question. – templatetypedef Dec 15 '17 at 21:04
  • @templatetypedef Even still, there's the problem of state explosion which I touched on in my answer. At any rate, he wants to find a solution, which is not the same thing as checking for solvability. – Beefster Dec 15 '17 at 21:13
  • You could set this up as a system of 64 equations in 64 unknowns over Z/2Z, and then use Gaussian elimination to solve the system. (Given that the coefficient matrix is relatively sparse, and there's a great deal of regularity to it, I wouldn't be at all surprised if this particular case could have some optimizations applied to use less than on the order of 64^3 operations. Still, even 64^3 isn't that bad.) – Daniel Schepler Dec 15 '17 at 21:41
  • If you press a button on the edge of the grid, does it "wrap around" so that a light on the opposite edge is also triggered? (And similarly, does pressing a corner button wrap around on two edges, e.g. pressing button A1 would trigger lights A1, B1, A2, H1, A8?) – Daniel Schepler Dec 15 '17 at 21:46
  • It doesn't wrap around. – 7lYNdYzwbY Dec 15 '17 at 21:58

1 Answers1

0

The Naive Solution

First, you're going to need a way to represent the state of the board and a stack to store all of the states. At each step, make a copy of the board, changed to the new state. Compare that state to all states of the board you've encountered so far. If you haven't seen it, push that state on top of the stack and move on to the next move. If you have seen it, try the next move. Each level will have to try all possible 64 moves before popping the state from the stack (backtracking). You will want to use recursion to manage the state of the next move to check.

There are at most 264 possible board configurations, meaning you could potentially go on a very long chain of unique states and still run out of memory. (For reference, 1 GB is 230 bytes and you need a minimum of 8 bytes to store the board configuration) This algorithm is not likely to terminate in the lifetime of the known universe.

You need to do something clever to reduce your search space...

Greedy-First Search

You can do better by searching the states that are closest to the solved configuration first. At each step, sort the possible moves in order from most lights off to least lights off. Iterate in that order. This should work reasonably well but is not guaranteed to get the optimal solution.

Not All Lights-Out Puzzles Are Solvable

No matter what algorithm you use, there may not be a solution, meaning you might search forever (or several trillion years, at least) without finding a solution.

You will want to check the board for solvability (which is a much faster algorithm as it turns out) before wasting any time trying to find a solution.

Beefster
  • 723
  • 7
  • 19
  • I'll give it a try. How can I check for solvability? – 7lYNdYzwbY Dec 15 '17 at 22:10
  • @7lYNdYzwbY IIRC, it's a simple parity check. You count the number of lights that are on and make sure it's even or odd (I forget which). It might be a little more complicated. – Beefster Dec 15 '17 at 22:22
  • Thx. The number of switched on lights in each row and colum must be even. Right? – 7lYNdYzwbY Dec 15 '17 at 22:43
  • @7lYNdYzwbY I'm actually not sure. Look it up. – Beefster Dec 15 '17 at 22:44
  • @7lYNdYzwbY - the terminal condition for the search should be specified on your assignment - so one person's solution may not work in your case. Best of luck. – Bob Jarvis - Слава Україні Dec 16 '17 at 00:12
  • @Beefster Can you please explain "and move on to the next move. If you have seen it, try the next move. Each level will have to try all possible 64 moves before popping the state from the stack (backtracking). You will want to use recursion to manage the state of the next move to check." in a bit more detail? What is my next move? How can I try all possible 64 moves before popping the state from the stack? How can I use iterative backtracking? Three for loops? Many thanks for your efforts. – 7lYNdYzwbY Dec 16 '17 at 01:48
  • @BobJarvis My assignment doesn't state any terminal condition. – 7lYNdYzwbY Dec 16 '17 at 01:52
  • @7lYNdYzwbY This isn't a homework help forum. Use your brain. – Beefster Dec 16 '17 at 17:48