The following is his solution. It may still be an exponential problem, but it only took him a couple minutes to come up with this solution. Create a graph where each node is a state of the game. An edge between two nodes represents the fact that I may create one node from the other by selecting one light. A game is decidable if the game state of all lights off is in the graph.
Solution finding then becomes one of a graph search from a given initial board.
A large drawback to this approach is it still requires the creation of 2 n nodes in the graph. Also, graph searches can be inherently slow, and in this case, exponential.