Hmm, more thoughts.
Some notation. Let the board be B, B[m,n] be the mth row, nth column. Let F[m,n] be a flip of a 4x4 area whose top left hand corner is [m, n]. 1 <= m,n <= 8.
Now, if a given board has a solution, then there must exist a series of flips F1 .. Fn such that the board after this series is all 0s.
Also, note that the order in which the flips are applied is irrelevant: the end result is that each cell of the board has been flipped a certain number of times. So, we can order the flips. Say the lowest being top LH corner, then increasing across the row, then onto the next row. (I could define this formally but I won't). Now, that means the last flip, if it is used, has coordinates F[5,5].
Now, with this in mind, I think the following algorithm will find a solution if there is one, or demonstrate that there isn't one:
Now, as to what properties this algorithm implies in terms of the number of 1s/0s at the start and anything else, I don't know. But I think it sounds good
It's also O(n) on the number of squares on the board.
--Tim
[ May 11, 2004: Message edited by: Tim West ]