Lights out game algorithm

My homework is to design a lights-out game using the backtracking description 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: Go from 1 to 25 and check if all the lights are off or not. If not then check from 1 to 24 and so on until I reach 1 or find a solution. If there is no solution then go from 2 to 24 and follow the above process till I reach 2 or find a solution.

But using this I am not getting the right result. For example: lights at (0,0) (1,1) (2,2) (3,3) (4,4) are ON?

How do I use backtracking to solve this?

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!