Inverter

http://gorried.github.io/inverter/game.html

by dgorrie • 12 years ago

179 53 12 years ago

gorried.github.io

chmullig• 12 years ago

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.

IanCal2• 12 years ago

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).

BoppreH• 12 years ago

The problem is strategy clues. I know how the game works, but that doesn't tell me where to play.

Past a certain size I lose all intuition and start clicking everywhere until something manageable appears.

jamestomasino• 12 years ago

Perfect little casual game. I played around with something similar during a github game challenge, but never finished. Nice work.

allannienhuis• 12 years ago

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...

dickeytk• 12 years ago

it's lights out! http://kbarr.net/static/lo/

dkhar• 12 years ago

Yup! Est. 1995! Here's a Wikipedia link: http://en.wikipedia.org/wiki/Lights_Out_(game)

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.

dgorrie3• 12 years ago

I knew I had played a game like this in the past, thanks for finding it!

cdr• 12 years ago

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.

lgas• 12 years ago

I made a version of this game that uses the Novation Launchpad S as an input/output device using Overtone from Clojure.

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.

Kiro• 12 years ago

Clicking in symetric patterns reminds me of Game of Life. Not sure if it's a good strategy though.

dmitrygr• 12 years ago

very old game called lights out

zwegner3• 12 years ago

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).

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)

rumdz2• 12 years ago

Doesn't work for me. I'm clicking the blue square and nothing happens. Chrome 37

zwegner3• 12 years ago

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...

zwegner3• 12 years ago

OK, so it's fixed now. Tested in Firefox, Chrome, and Safari. As soon as rawgit refreshes its copy, the new version will be live.

linkeex• 12 years ago

For anyone wondering how to solve this algorithmically: http://en.wikipedia.org/wiki/Lights_Out_(game)#Light_chasing

Procrastes• 12 years ago

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.

1. http://slideme.org/application/skeedle

octatone2• 12 years ago

I find the "on to level x" popover slow and unnecessary, I just want to invert more colors :)

lotsofcows• 12 years ago

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.

JadeNB• 12 years ago

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.

josephschmoe• 12 years ago

What libraries/tools did you use to make this game?

dgorrie3• 12 years ago

Just bootstrap and jquery! Here's a link to the repo: https://github.com/gorried/inverter

ojiikun• 12 years ago

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.

dgorrie3• 12 years ago

Sorry to hear, I totally didnt think about that when I was testing :P

rando289• 12 years ago

This is a variation on the game of life.

superchink• 12 years ago

This reminded me of the first native iPhone game back in 2007:

http://www.macrumors.com/2007/08/13/lights-off-first-native-...

elwell2• 12 years ago

Eeek! I ended up with a swastika on level 6.

elwell2• 12 years ago

77 points by 4 hours, a valiant effort. But, I don't think we'll be seeing Doge Flappy Bird Inverter anytime soon.

munificent• 12 years ago

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.

http://robot-frog.stuffwithstuff.com/misc/index.html

S4M• 12 years ago

Same, I wrote the exact same game - with the exception that the board was constant, 6x6 maybe - when I was in highschool - 1998-99.

dperny• 12 years ago

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.

rubberbandage• 12 years ago

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…

Screenshot for comparison: http://i.imgur.com/U4ZlgY9.png

Sarien• 12 years ago

Best screenshot ever.

wzsddtc• 12 years ago

This is the classic lights out right? http://en.wikipedia.org/wiki/Lights_Out_(game)

LVB• 12 years ago

Upon reaching level 3, I couldn't help but think of Merlin. http://en.m.wikipedia.org/wiki/Merlin_(game)

hexleo• 12 years ago

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.

bcuccioli• 12 years ago

Others have pointed out that this is Lights Out. If anyone's interested, there is a known algorithm (PDF):

https://linux.ime.usp.br/~renatolg/lights_out.pdf

tzs• 12 years ago

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.

chaoxu3• 12 years ago

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.

sillysaurus3• 12 years ago

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.

poulson3• 12 years ago

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• 12 years ago

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

anon4• 12 years ago

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.

jkrause314• 12 years ago

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.

samirmenon• 12 years ago

This game is frequently a part of Legend Of Zelda: Phantom Hourglass (in the Ocean Temple). It's cool that you've made it a standalone game.

borplk• 12 years ago

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?

Edit: just saw chaoxu's comment. cool.

Inverter

Related Stories