This problem can be generalized to the following graph light out game: Given a graph where each vertex is labeled 0 or 1. Each move flips all the bits on a vertex and all its neighbors. If you are given the end label configuration, find a set of moves that reaches the end configuration. (why a set of moves? you can show that you never need to make a move on a vertex twice, and the order doesn't matter).
So the question is, which vertices do I have to touch once?
It's easy to solve the problem by solving a system of linear equation(in F_2, not in R). Ax=b, where A is the adjacency matrix, and (b[i]= (current bit on vertex i != desired bit on vertex i)).
Naively, for the light out game on a nxn board, this implies a O(n^6) using Gaussian elimination algorithm. Or O((n^2)^ω)) (where ω is the matrix multiplication constant) by finding a matrix pseudoinverse and then multiply.
The graph light out game can be solved in O(n^(ω/2)) time for planar graphs! Because most matrix operations can be done much faster on the adjacency matrix of a planar graph due to nested dissection. http://en.wikipedia.org/wiki/Nested_dissection
In particular, the current game is a planar grid graph. So there exist a O(n^ω) algorithm.
That kind of game is part of S.G. Tatham's portable puzzles collection (available on everything, including toasters running NetBSD). You can either solve a normal NxN board where each tile flips the 4 adjacent tiles, or a hard (generalized) variant where each tile flips some amount of tiles around it.
Ok, so let's implement the algorithm. Where would you start? Which math libraries would make this easier? It seems like Mathematica might be good here.
I've manually verified that the binary matrix printed out by the following Octave/MATLAB routine provides solutions to Inverter. (NOTE: You may want to use the gflineq.m implementation from http://lost-contact.mit.edu/afs/cs.stanford.edu/package/matl...)
function M = Inverter(nx,ny)
A=eye(nx*ny,nx*ny);
for x=1:nx, for y=1:ny,
i=x+(y-1)*nx;
if( x ~= 1 ), A(i,i-1)=1; end;
if( x ~= nx ), A(i,i+1)=1; end;
if( y ~= 1 ), A(i,i-nx)=1; end;
if( y ~= ny ), A(i,i+nx)=1; end;
end; end;
b=ones(nx*ny,1);
s=gflineq(A,b);
M=zeros(ny,nx);
for x=1:nx, for y=1:ny, M(x,y)=s(x+(y-1)*nx); end; end;
return
Almost nothing about the solver would need to change in order to support computation over GF(p), which suggests that someone should create a version of Lights Out / Inverter which cycles through a prime number of colors rather than just off/on.
Wikipedia has an article on this, http://en.wikipedia.org/wiki/Linear_equation_over_a_ring it would take a long time to read up the background to understand it, and I don't have the background to distill it to the exact result we want.
Note the wiki article references this book: Ideals, Varieties, and Algorithms by Cox, Little and O'Shea. This is a standard and approachable reference on this kind of topics.
Although this topic is interesting, I think it's best to treating it as a technology. Knowing it's existence and know when to apply them is good enough. Understanding how it works would be a big time sink and sadly doesn't give much useful insights.
So the question is, which vertices do I have to touch once?
It's easy to solve the problem by solving a system of linear equation(in F_2, not in R). Ax=b, where A is the adjacency matrix, and (b[i]= (current bit on vertex i != desired bit on vertex i)).
Naively, for the light out game on a nxn board, this implies a O(n^6) using Gaussian elimination algorithm. Or O((n^2)^ω)) (where ω is the matrix multiplication constant) by finding a matrix pseudoinverse and then multiply.
The graph light out game can be solved in O(n^(ω/2)) time for planar graphs! Because most matrix operations can be done much faster on the adjacency matrix of a planar graph due to nested dissection. http://en.wikipedia.org/wiki/Nested_dissection
In particular, the current game is a planar grid graph. So there exist a O(n^ω) algorithm.