Should have realised this... "there is no other strategy" is a bit hasty...
I should have put 'there is no other human playable strategy'.

You can actually think of this problem as a matrix of a field domain in modulo 2.
And you can solve this in O(MxN) time using gauss-jordan elimination.
Already verified, random 1000x1000 board solved in just under a minute on a single core.
It would surprise me however this is the kind of solution your teacher is looking for.