backtracking - Lights out game algorithm

Question

It's a homework. I have to design and lights out game using backtracking description is below.

The game consists of a 5-by-5 grid of lights; when the game starts, a set of these lights (random, or one of a set of stored puzzle patterns) 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 and some are off, the goal is to switch all the lights off, preferably in as few button presses as possible.

My approach is go from 1 to 25 and check if all the lights are off or not. If not then I will check for 1 to 24 and so on until I reach 1 or found solution. No if there is no solution then I will start from 2 to 24 and follow the above process till I reach 2 or found solution.

But through this I am not getting the result ? for example light at (0,0) (1,1) (2,2) (3,3) (4,4) are ON?

If any one need code I can post it.

Can any one tell me correct approach using backtracking to solve this game ?

Thanks.

Answer 1

There is a standard algorithm for solving this problem that is based on Gaussian elimination over GF(2). The idea is to set up a matrix representing the button presses a column vector representing the lights and then to use standard matrix simplification techniques to determine which buttons to press. It runs in polynomial time and does not require any backtracking.

I have an implementation of this algorithm that includes a mathematical description of how it works available on my personal site. I hope you find it useful!

Edit: If you are forced to use backtracking, you can use the following facts to do so:

• Any solution will never push the same button twice, since doing so would cancel out a previous move.
• Any solution either pushes the first button or does not.

Given this approach, you could solve this using backtracking using a simple recursive algorithm that keeps track of the current state of the board and which buttons you've already made decisions about:

• If you've decided about each button, then return whether the board is solved or not.
• Otherwise:
  • Try pushing the next button and seeing if the board is recursively solvable from there.
  • If so, return success.
  • Otherwise, try not pushing the next button and seeing if the board is recursively solvable from there.
  • If so, return success. If not, return failure.

This will explore a search space of size 2²⁵, which is about 32 million. That's big, but not insurmountably big.

Hope this helps!