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 225, which is about 32 million. That's big, but not insurmountably big.
Hope this helps!