Is there an algorithm for solving “Magic Squares” puzzles?

Question

In case you don't know what I'm referring to, it would be those "lights on, lights off" puzzles where you are free to toggle the status of any light in the grid, but doing so also toggles adjacent lights (but not diagonal).

The goal is usually to toggle all of the lights on, or to match a certain pattern of lights (i.e. middle light off).

The puzzle I'm currently stumped on begins as such:

O X O
O O O
X X O

The goal is to make a T shape, or:

O O O
X O X
X O X

I can never figure out a "tried and true" method to solve these, and am wondering if there is some lovely match trick that can be used to figure them out. More often than not, I end up just toggling at random and hoping for the best.

A solution to this particular problem would be nice but I'm also looking for an "algorithm" of sorts for future puzzles.

Thanks!

Answer 1

One thing to note is that it makes no sense to toggle a light more than once, because the toggles commute and two toggles takes you back where you started. An algorithmic approach is to find a series of toggles that flips each light leaving all the others alone. You only have to find three, one each for a corner, edge, and center, then can get the rest by symmetry. Having done so, for a particular problem you identify all the lights you want to change, make a list of all the changes that would change each one individually, then strike matching pairs until you have a list that includes each light at most once.

For example, I believe toggling the center and each edge will flip the center light and no others. In your sample problem you would not need this as the center does not change.