[chaoxu]

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.

[anon4]

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.

[sillysaurus3]

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.

[poulson]

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

[pantaskios]

It's been done: http://library.wolfram.com/infocenter/Articles/1231/

[poulson]

Thanks for the link! There is even a nice discussion of the explicit solutions for Inverter up to 7x7's on the page: http://mathworld.wolfram.com/LightsOutPuzzle.html

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.

[chaoxu]

I think it would work for all finite fields. One of the solutions to this IOI problem was solved that way, and it's not of the form GF(p) but it's GF(p^2). http://olympiads.win.tue.nl/ioi/ioi94/contest/day2prb1/probl... see solution 2: http://olympiads.win.tue.nl/ioi/ioi94/contest/day2prb1/solut...

[poulson]

Good point. So it would seem to be hard to find solutions for 6, 10, 12, etc. colors. Have you given any thought to how to solve those cases?

[chaoxu]

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.