Show HN: Lights Out: my 2D Rubik's Cube-like Game
raymondtana.github.io"Lights Out" is a mathematical puzzle that lives on an grid where each cell of the grid is one of two colors: either red or white. The goal is to eventually get all the cells in the grid to be red.
What's the catch? Clicking a cell will not only flip its color, but also that of all cells sharing the same row or column as it.
To me, this game feels like playing with a Rubik's cube --- every time you think you are fixing one cell, you mess up its neighbors!
There are many ways to arrive at a solution... some mathematical (linear algebra, or combinatorics), others more logical,... and yet others which are brute force.
The title “Lights Out” comes from a classic handheld game from 1997. The “rule” they follow for which-cells-get-flipped-on-click is what I call “Adjacent.” Additionally, my mathematics teacher showed me this game following another variant which I call “Same Row & Column,” but on a bigger board. He had worked out an algorithm for his version. I found the same strategy before he revealed the answer, and I feel that the process of discovering a solution is quite rewarding—it’s fundamentally related to computing on restrictive computer architectures.
I implemented this app with pretty basic TypeScript. It’s been used for some experiments to discover more general of strategies for different click variants, board sizes, and even board dimensions! It has also been the basis for the corresponding video produced using the Python library manim.
Try it out and let me know how you do!
Memorize which cells are white when the board first loads. Tap all of those in order without regard to the way the board changes as you go.
Edit: above tested for 5x5 rows&cols. For even boards it seems there’s a small end-game to repeat the process — something about parity I assume.
And you can do that at any board state, so if it starts with like 16 white squares you can make one or two greedy moves to minimize white squares, then do your memorize trick.
Yea that can shave a few moves off.
For fun you can also, for example, invert any board in N moves by tapping every cell straight across any row or column.
Interesting, and black magic as far as I'm concerned. How does that algorithm translate onto the Rubik's cube (which I evidently never learned to solve)?
Why does that work?
If you think of each button press as a matrix being added to the board state where only the row and column are set to 1, along with the commutative nature of the moves (order doesn't matter), then as long as the total number of "flips" from the cumulative matrices of moves is odd, then it will reset the board.
Mathematically I might say that the system's precomputed solution vector is readily apparent.
I think this only works with an odd grid size. With an even grid size you might have to do it twice.
What if there was only one white block on the grid?
The game is initialized with a guaranteed solvable board:
https://github.com/RaymondTana/Lights_Out/blob/31fe5e866c45c...
I’m pretty sure this case is solvable too. Click the white block, then click all the blocks which turned white after that. This flips each block twice (bringing them back to their original state), except for the original white block which was only flipped once.
Hi everyone, I'm the OP and wanted to share a few comments that might come as spoilers. So read with caution!
1. The default game has a simple winning strategy: the app begins with a 5x5 board under the "Same Row & Column" variant. Some here have already figured out how to get all reds: [Memorize all the white squares on the board at some fixed moment, and click those cells in any order.] Some of the info below helps see why.
2. The game is always winnable: the app is set up to secretly begin with all reds and then perform many random clicks to mess it up; it's always reversible.
3. The order of clicks doesn't matter: the click actions commute.
4. Every click is self-inverse: clicking a cell twice under any variant leads to the same board as before.
5. A winning strategy need only list out which cells to click once: Because of the properties of commutativity and self-inverse, any winning strategy could be freely shuffled in order and have any duplicate clicks cancel out, leading to a strategy of cells meant to be clicked just once---the rest ignored.
6. Suppose "n" is odd and play the "Same Row & Column" variant. Then, the n-by-n board is solvable by the strategy of "click all the cells that were white." But when "n" is even, then this strategy fails on the n-by-n board. However, there indeed is another strategy that solves those systematically.
7. Very little is known about the other variants, nor about other sizes and dimensions of boards. And it is not true in general that any random pattern of white-and-red can be turned into all-reds. Try to find a good heuristic for separating out winnable vs. unwinnable boards!
8. I did forget to mention other versions of Lights Out besides the handheld game. Other physical games and video games used the 5x5 "Adjacent" variant, too.
Bonus Questions:
1. Can you think of an interesting clicking-rule variant that would not be commutative?
2. Can you come up with the winning strategy for winning n-by-n boards when n is even under the "Same Row & Column" variant?
3. Can you figure out any winning strategy for the other variants? I haven't found any good way to proceed without just memorizing the solutions.
Thanks for the comments!
Among the 2^n configurations, how many are solvable?
There are two significant ways in which this differs from a Rubik's cube.
1. It's abelian. Moves can be done in any order, to the same result.
2. there's a simple algo to solve this. Working from top to bottom, left to right: click the first white cell, then click the cell below it. (Then there's a simple endgame at the end once the bottom row is reached.)
Enjoyable, after getting the hang of the "full rows/cols" variant it became like popping packing bubbles.. I kind of wanted to keep playing with the kaleidoscopic shapes you can make with the near-complete positions.
I'd seen the "adjacent only" variant before but not the other two, I'm glad the default was one I hadn't seen or I might not have noticed there was a choice!
Have you considered allowing the all-white state as a terminal state too? First time I completed it was with a detour to there (I know the text says make them red but my instincts went with the lights-out being to the color matching the background)
Thanks for the diversion. On the 5x5 my scores went from ~100 to dozens (sometimes 8-10). On larger boards I'm not as consistent but also not as interested in path length.
I loved that handheld as a kid! I was discovering how powerful vibecoding was last year and used this exact game to show some friends https://drive.google.com/file/d/1jVLpVfUWDkdgImLo45VDtroB-EZ...
One other variant that I've made in the past is cells have N states which increment and cycle mod N.
A straightforward solution for larger puzzles: if you click on the four corners of a rectangle, you flip those corners while leaving the rest of the rows/columns the way they started. So after you pick the low hanging fruit at the start, find any rectangle with 3 or 4 white corners, and then click on all 4 corners of that rectangle. If this leaves you with a just one white in each row and column, it's easy and doesn't require memorization to click each of those whites to get to the solved state.
Here’s my solution: clicking four boxes that form the corners of a rectangle will flip them leaving the rest of the board unchanged. Using this move you can find sets of rectangle corners with more white than red and just click them. This will converge to a solution. If you can find a symmetric board where all rectangle corners have equal red and white then this method would fail. I haven’t found one yet.
EDIT: I found some positions where this technique cannot be directly applied.
Years ago, I developed a 2D Rubik's Cube game for my son, in order to learn JavaScript: https://www.thelyonsfamily.us/games/FlipYourLid/
As far as I know, my son is the only person who plays it. :-)
Fun game, kudos!
Calling it a 2d rubik's like makes me wonder if I should try to turn the code at the bottom of https://taeric.github.io/cube-permutations-1.html into a game.
Not to be confused with the other grid based light flipping game, Lights Out, from 1995.
https://en.wikipedia.org/wiki/Lights_Out_(game)
Math article https://matroidunion.org/?p=2160
Or 80s Merlin’s Magic square game.
https://en.wikipedia.org/wiki/Merlin_(console)
Which was only 3x3. But red LEDs which were all the rage in handhelds in the 80s.
When learning JavaScript I made a dupe of the Merlin game in JavaScript. It’s really old but still seems to run. Lacks the depth of this game with its larger grid.
https://www.aramcomjean.com/magic_squares.html
Amazing. I had one of these, and playing your version just took me back to the frustration I had figuring out that game when I was 7 years old.
Once you figure out the trick to the row column puzzle it becomes trivial to solve, except that you need a steady hand.
I'm glad I got to play it for a bit before learning the trick. Quite a simple and clever puzzle!