Inverter
gorried.github.io
gorried.github.io
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.
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;
returnAlmost 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.
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.
Mine is different in that it it's way less polished, starts with a randomly-initialized grid, and rows/columns that are all the same color disappear (so the goal is to make them all disappear).
It wasn't quite fun enough for me to clean it up more, but it was mildly amusing for a while. It's here in case anyone would like to try: https://rawgit.com/zwegner/switchy/master/switchy.html (or the source repo: https://github.com/zwegner/switchy)
Past a certain size I lose all intuition and start clicking everywhere until something manageable appears.
PS: I have not updated that page in years, which is why it contains a link to a Dutch noodle seller. It was a link to an online game service back when I wrote the page.
I remember playing a version of this game that was posted on HN a few weeks ago. Jennifer Dewalt (the person who learned to code by making a website every day for 180 days) made it! http://jenniferdewalt.com/lights_on/game
The mathematics behind this game are apparently pretty interesting. I'm not big on matrix math, but I bet a lot of you guys are.
There's also an infamous quest that ends with a lights out puzzle with a large, arbitrary board (some squares completely removed) while an overpowered, invincible, impossible-to-tank scorrow boss chases you around. And both the boss and the dozen infinitely-respawning trash mobs activate squares when they step on them.
https://github.com/lgastako/leds-out
I haven't hooked it up to trigger samples yet, but I've done the work in my Conway's Game of Life for the Launchpad I just have to find the time to port it over.
Screenshot for comparison: http://i.imgur.com/U4ZlgY9.png
Huh, looks like it's still up[1] on slideme.org, but I don't recommend buying it. I'm not supporting it anymore. I'll see about taking it down.
Are there "easy" mathematical strategies? Is there a solution for an arbitrary large grid? Complexity?
From a first glance this reminds me of "constraint satisfaction" classes of problems. I remember studying the famous one where you are asked to colour a map such that no two adjacent cities share the same colour.
Does this fall into that group or is there a better way?
Edit: just saw chaoxu's comment. cool.
EDIT: On further play, I find the self-dismissing notifications on level completion distracting; I would like it better if they hung around until I manually dismissed them.
http://www.macrumors.com/2007/08/13/lights-off-first-native-...