#1: Jan Wolter (jan) on Feb 15, 2009

A couple days ago my son was home sick from school, so I decided to distract him from his boredom by showing him how a little computer game could be written from scratch.

The result of that project is this page:

http://unixpapa.com/flixel

I found it rather interesting to play around with.

The object is to turn the grid entirely green. I'm not sure if all grid sizes are solvable, but many more are solvable than would think at first.

Reminds me of a game I used to play - Lights Out. It was a handheld game and the object was to turn off all the lights that were lit.

Could be the same. I've seen this before other places but never played with it much.

I'm beginning to think everything might be solvable. I'd noodled around with a 5x5 grid for an awful long time before figuring out how to solve it.

I've run across this type of game inside computer games, and they just don't like me much, I think. I couldn't solve this one I think that maybe the Flixel on my screen really wants to be red. :)

That's pretty cute, even though apparently I stink at it.

If you play with it, especially with the "cheat" switch on, you can start seeing some sense in it, but I still don't feel like I entirely understand it.

Here are some things I know:

The order on which you click on cells doesn't matter. All that matters is which cells you have clicked on an odd number of times and which cells you have clicked on an even number of times. The "cheat" mode displays a yellow dot on each cell that has been clicked an odd number of times.

Finding a solution can be thought of as finding a pattern of yellow dots that paints the grid green. A cell is green if a plus sign centered on that cell contains an odd number of yellow dots.

The following systematic procedure can be used to search for solutions to grids: Try every possible arrangement of yellow dots in the top row. For each top row, you can fill in the rest of the rows of the puzzle by going down row by row, click each cell that has a red cell above it. This may be systematic but it's still a lot of work for larger puzzles.

The following grid sizes are solvable:
1 x anything
2 x anything
3 x anything
4 x anything (I think)
5 x anything up to 17 (haven't tried 18 and up)
6 x anything up to 15
6 x 17
6 x 18
7 x anything up to 13
7 x 15
7 x 16
8 x 8
8 x 15
9 x 9
9 x 10
10 x 12
10 x 13
10 x 14
10 x 15
10 x 16

You can note down solutions for a grid size by just noting down the pattern of yellow dots in the top row. The rest of the solution can then be easily found by the method described above. For example, to solve the 9x9 puzzle, fill in the top row as 'XX-----XX' (X's are yellow dots). Then in the second row click on any cell that has a red cell over it, and so on to fill in the whole puzzle. You get a solid green grid, a happy flixel, and an interesting pattern of yellow dots. Some solutions have very symmetrical patters of dots, and others are very strange.

The number of possible red-green patterns is 2 to the n-th power, where n is the number of cells. The number of yellow-dot patterns is the same. If every yellow dot pattern gave a different red-green pattern, then we would know that there had to be a yellow dot pattern that gave a solid green solution, so every puzzle would have to be solvable.

This is not, however, the case. In a 2x3 grid, click all four corners. You get solid red. That means there (at least) two yellow dot patterns that give the same red-green pattern. That means that there must be red-green patterns that cannot be achieved by any yellow-dot pattern. Some possible goal states are unreachable. So it is possible that for some grid sizes "solid green" is unreachable.

Yet, although I have found many, many cases of different dot patterns that give the same image, so many, many goal states must be unreachable, every puzzle size that I have really beaten on has turned out to have a solution. More grid sizes are solvable than one would reasonably expect. So I think there is some subtler structure here.

In fact, in a 2x3 grid, there are only five different patterns that can achieved, not counting rotations, reflections and red-green inversions as different.

Note that if the puzzle is solvable, then any state is invertable (you get the same pattern with red and green swapped). Also if you find any pair of states that are inverses of each other, then the puzzle must be solvable.

Yes Jen! I was trying to figure out why it looked so familiar..the "lights out" game

Wikipedia has a page: http://en.wikipedia.org/wiki/Lights_Out_(game)

Analysis doesn't go much beyond what I've done, but they have a solution for a 10x10 grid, which I hadn't found yet. Apparantly the "lights out" game starts with a randomixed 5x5 grid, never other sizes.

This guy has lots of analysis:
http://www.geocities.com/jaapsch/puzzles/lomath.htm

Looks like all grid sizes are solvable if you start from an all red state.

Well, I give up... It took me a while even to figure out what was going on. Then I managed to get a 3x3 grid, but I can't to the 6x6 for the life of me.

OK, for those who get stuck, I added a feature to flixel. It now solves itself if you check the two check boxes at the bottom of the page. This looks cool, but I kind of cheated. I wrote a program to find solutions for all grid sizes 20x20 and below, then stored the top rows of all possible solutions in a data structure loaded with flixel.

So it solves puzzles by filling in the top row from its list of solutions and the filling in all other rows by clicking cells under red cells. I also animated it, so you can watch it fill in.

This auto-solve thing is fun to watch, but not as much fun as I had figuring out how to solve these things myself. Probably the auto-solve thing makes the flixel page more frustrating: you can spend hours trying to figure it out, or you can spend seconds watching it solve itself. Oh well. I had my fun.

i got it all green except for one red dot slight up and right of center. looks like a square olive...makes me want a square martini.

Goto next topic

You must register and log in to be able to participate in this discussion.