News for hackers. Stuff that matters.
Re:Inverter by sillysaurus3 on Wednesday July 16, 2014 @12:05AM (#8040515)
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.
Re:Inverter by poulson on Wednesday July 16, 2014 @12:33AM (#8040583)
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
Re:Inverter by pantaskios on Wednesday July 16, 2014 @02:07AM (#8040778)
Re:Inverter by poulson on Wednesday July 16, 2014 @09:50AM (#8041960)
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.

Re:Inverter by chaoxu on Wednesday July 16, 2014 @12:31PM (#8042913)
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...
Re:Inverter by poulson on Wednesday July 16, 2014 @04:01PM (#8044177)
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?
Re:Inverter by chaoxu on Thursday July 17, 2014 @04:44PM (#8050098)
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.