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.
Huh, I just made a pretty similar game a couple weeks ago.
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).
Ah, yes, I had forgotten that I didn't test in anything other than Firefox. I'm very much not a web developer--working with JS is really quite a pain, and I had to use as much ES6 magic as possible to make it tolerable. Looking now into Traceur to de-ES6ify the code...
Very interesting game. Unfortunately I found it just devolved into random clicking - there weren't enough clues to give me much strategy. Gave up when the grid got to ~9x9, and it was just a waste trying to get it working.
I'm not sure I understand about the clues. When you click a square, it inverts the colour of that square and the ones around it (up, down, left and right).
Oh I see what you mean. I can see a few patterns around but I've not got a good understanding about how to solve many of them, so I can't logically work through things after a certain point.
That's the clever solution. Here's a solution that is actually brute force, but tries to fake being clever: http://www.tzs.net/lights.html
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 agree. Can't ever dismiss it with return or escape so I have to track over there to click and back again. The process is enough of a distraction that at the first hint of frustration it's a natural point to stop.
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.
Anyone who's played Dungeons and Dragons Online (the MMO) for any length of time is familiar with lights out. It was a favorite puzzle for the designers of the earlier-vintage quests, and notably the most popular raid in the game for many years has an entire phase devoted to locking each of the twelve participants in their own lights out puzzle. Low-effort people find a solver, really low effort people beg other people to solve theirs for them. Go-getters learn to solve lights out without a solver.
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.
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.
Wow, that takes me back. I wrote a game very similar to that (but with randomly generated symmetric boards) a while ago called Cesare. And by "while ago" I mean around 1998 or so.
I find this frustrating, because it reminds me just how un-clever I am. Other commenters are progressing quite far, but I've gotten stuck already at level 5. Puzzle games cause me to call into question my entire sense of being.
Emacs, at least on OS X, has “level 5” in its games as “5x5”, including the “how many moves has it taken so far” counter. I couldn’t beat that, and once I got to level 5 here, I couldn’t beat this! Someday I’ll finally figure it out…
Fun and attractive! I did something similar for android years ago with six states for each cell (represented by blank, card suites and a gold bar graphic). It rapidly became so hard I had trouble solving it myself after just a few levels. If I had stayed with it I would have written a hinting feature, (best next move flashes).
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.
I kinda like this. Years ago I toyed with building a similar inversion type puzzle game based on a hexagon field. It also had the problem of devolving into more or less random clicking once the field got bigger, and so frustrating the player fairly quickly as the play progressed. The hexagon play field did lend itself to having differently shaped playfields which added something to the play on smaller fields. Not sure if that idea has any merit for this game, though...
Can someone expand upon Artificial Intelligence strategies for solving this?
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?
As others have said, this is a nice casual game; good job! One small comment: "Lets go" in the start prompt should be "Let's go".
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.
Probably unintended, but you've got a nice Hermann grid illusion (https://en.wikipedia.org/wiki/Grid_illusion) there! Haven't seen that done with colors other than black and white.
It's just like an old game, when I was a middle student in China. The only different place is game map. Different level has different map to increase the difficulty.
Minor UX issue: on level up, it scrolls the page back to the top, but on my laptop I have to scroll down just a hair to see the whole board. Very annoying.
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.