What is the optimal solution for the game "Puzzle+"?

[MkJones]

A friend challenged me to find an algorithm to solve the game Puzzle+:

In a nutshell: given a NxM array of random booleans, your objective is turn all values to false.
On each move you specify a coordinate (x,y) to toggle (array[x][y] = not array[x][y]), however that action also affects array[x-1][y], array[x+1][y], array[x][y-1], array[x-1][y+1] (on in short - it's adjacent cells).

For example: given a 3x3 board:

|f T f|
|T T T|
|f T f|

The solution it to simply toggle the middle cell.

You can find the actual game here: https://play.google.com/store/apps/d...pps.puzzleplus (android only)

I could only come up with a brute-force solution. Can any one advice an efficient approach? O(n)?