This is a very nice exposition of the strategy, but I still don't see how it answers my more specific question, about whether you can solve the problem row by row (is the grid).
Sorry, it turns that was misunderstanding from my part. It turns out we cannot solve a board row by row without revisiting the previous rows. The board below is a counterexample:
101
010
100
The first and second rows are solved. However we cannot solve the last row without re-doing the first and second rows. The two solutions of this board shows this:
solution #1:
110
100
000
solution #2:
110
110
000
Actually, seeing my mistake made me challenge my assumption that a singular matrix over the reals might not be over integers modulo 2. This is likely wrong too. I don't know much about abstract algebra (and I am not a mathematician). Wikipedia (https://en.wikipedia.org/wiki/Determinant#Square_matrices_ov...) states "the reduction modulo m of the determinant of such a matrix is equal to the determinant of the matrix reduced modulo m."
The move matrix M for all boards of size 3n + 2 appears to be singular. This means these boards may have no solution or a large number of solutions.
FYI, a singular matrix taking values in {0,1} that is singular over R if and only if it is also singular over Z/2, for exactly the reason you provide, that the determinant commutes with modding by 2.
