["Beyond Tetris" is a column from Tony "Tablesaw" Delgado about puzzle games that transcend mere abstract action and instead plunge deep into the heart of problem-solving. This installment looks at the classic handheld puzzle game Lights Out.]

The most recent edition of Lights Out, published by Hasbro The best puzzles hide great complexity in simple packages, but Lights Out turned out to have more surprises than I bargained for. I thought I'd write a bit about the handhelds, write a bit about the puzzle appearing in videogames, and be done with it. When I sat down to do the research, though, I discovered that the small game was tied up in some big things like linear algebra, patent law, and the collectors of rare mechanical games.

Lights Up

Lights Out was first produced by Tiger Electronics in 1995 (Tiger was bought by Hasbro in 1998). It was a very simple device with a simple puzzle. You were given a 5x5 grid of buttons, each of which concealed an LED. Some buttons were lit, and others were not. The goal, as one might expect, was to turn all the lights out. But every time you pressed a button, you wouldn't just toggle on or off that one button, you would toggle the buttons above it, below it, and to its sides. If you pressed a button that wasn't on an edge, it would create a pattern like a cross or plus sign. Every button had undesired consequences, and going from a given pattern to lights out became difficult. The game contained a set of fifty patterns of increasing difficulty, and another set of one thousand solvable patterns.

Tiger developed several version over the years. There was Mini Lights Out, which used a 4x4 grid. Lights Out Deluxe had a 6x6 grid, and had puzzles where the buttons you were allowed to press were limited. On the Lights Out Cube, the edges weren't boundaries, so the cross pattern applied everywhere (sometimes wrapping to an adjacent face). Lights Out 2000 added a third state to each button (that is, instead of going from off to on to off, you cycled through off to red to green to off). Lights Out even appeared as an actual, honest-to-goodness, console-based videogame. In 1997, Tiger released the Game.Com to compete with the Gameboy, Lights Out was available as a pack-in for the system.

A screenshot of Sigil of Binding, by John Paul Walton, a reskinning of Mini Lights OutUnsurprisingly, Lights Out became a quick hit among puzzle fans. And since puzzle fans make puzzle games, it didn't take long before imitations appeared in videogames. Clones and solvers hit the web quickly, and they continue to be popular. Sigil of Binding, a popular entrant into the first Jay Is Games Game Design Competition, is simply Mini Lights Out with a new skin. Lights Out was also incorporated as a puzzle in puzzle-oriented adventure games; one of its most recent appearances was as the green wall in Mystery of Time and Space. By 1998, the interactive fiction Usenet groups considered it a cliché and encouraged authors to avoid it. In fact, it became a puzzle standard so quickly, I stopped noticing it years and years ago. And when doing the research, I was surprised that such an old chestnut had only surfaced twelve years ago. I should have expected that the truth would lay much farther back.

A Long History

The most recent version of Merlin, a predecessor to Lights Out, now published by Milton BradleyThough Tiger received a patent for Lights Out, they were not the first to produce this type of puzzle. Merlin, produced by Parker Brothers in 1978, played several games on its lit electronic keypad, including "Magic Square." It was similar to Lights Out, but it was smaller (only 3x3) and different buttons had different effects. The corner buttons toggled the 2x2 square in that corner, the edge buttons toggled the three squares on that side, and only the center button toggled values in the familiar cross shape. Moreover, the goal of Magic Square wasn't to turn all the lights out (or on), the goal was to create a specific pattern: lighting up all squares except the center. The pattern may seem odd, but some puzzlers might remember Magic Square's appearance in The 7th Guest as the coffin puzzle. And Magic Square may be even older than that. Google's puzzlesmith Wei-Hwa Huang suggests that it appeared on mainframe computers under the name "Enigma."

But perhaps you're looking for a more direct predecessor, a puzzle that uses the distinctive cross pattern in its puzzles. If so, you need only look to the Vulcan XL-25, first exhibited in London in 1983. This handheld device features the same 5x5 grid that reacts in the same way, creating toggling squares in a cross shape. The only difference between the two is that the XL-25 asked you to turn all the lights on, instead of turning all the lights off. Moreover, it allowed the user to switch from "cross" mode to "knight mode." Knight mode was a variant where pressing a button toggled that square and any square that was one knight's move away. The Hungarian patent, by the way, isn't mentioned by Tiger (Merlin was).

And that's not all. In a post to rec.puzzles, Gary Watson claims to have come up with a close variant in the mid '80s, which he implemented in Basic and called Flip. So, leaving aside the question of whether or not the Lights Out patent is remotely enforceable, where do all these puzzles keep coming from?

Enter the Matrix

The green wall from Mystery of Time and Space by Jan Albartus: a Lights Out puzzle into an adventureThe answer to that question probably comes from the same place as the simplest solutions to Lights Out: math. If you (like me) know a little bit about matrices, it's pretty easy to see how Lights Out can be considered a binary matrix, with lit squares as ones and unlit squares as zeroes. If you know a little more about matrices (unlike me), then you'll be able to find the solution to a level using linear algebra. In fact, there are several journal articles detailing methods for creating the best solutions, and asking questions about general cases. Lights Out even merits its own page at MathWorld.

Jaap Scherphuis maintains a massive site detailing the specifics and and mathematics of many mechanical puzzles. His information on Lights Out and its variants include how to find the maximal solution to every type. He also has a very large page on the mathematics of Lights Out, which explains how the maximal solutions and the methods for finding them were developed. It's not for the layperson, but it contains lots of information including an abbreviation bibliography on the subject.

One of those articles is by Klaus Sutner, building on an earlier paper that's important to thinking about Lights Out. At the time, he was writing about the Merlin Magic Square, but to discuss it, he proposed something called the "Sigma+ Game." The Sigma+ Game is played on a directed graph of any shape. See, Lights Out can be thought of as a directed graph where every square is a node that points to every node that is adjacent to it. And in the Sigma+ Game, like Lights Out, picking a node changes the state of the chosen node and every node it points to. Sigma+ is the metagame of which Lights Out, Magic Square, and the XL-25's knight game are merely specific cases. And when the realm of Lights Out puzzles is expanded to include the Sigma+ game, things get pretty weird.

A Full Spectrum of Variants

The rare Game Jugo, a mechanical variant of Lights Out prized by collectorsDavid Singmaster's copious notes on recreational mathematics includes a section on "Binary Button Games." In addition to the grid-based games I've already mentioned, there are several unusual Lights Out variants that work with nonstandard directed graphs as in the Sigma+ Game. For example, there's the entirely non-electronic predecessor to Lights Out: Game Jugo, or the Jugo Flower. This was apparently made in Japan, and is one of the most sought-after mechanical puzzles in the world. Reportedly, only seven were made. In Jugo, when you manually flip one petal of the flower, four other petals rotate with you. It's the same puzzle as Lights Out, in a totally different presentation. The Orbik is also noncomputerized puzzle around a circle, but in Orbik, each node can be in one of four states. And if you're wild about having extra states, there's always Rubik's Clock, an incredibly complicated puzzle where each of fourteen clocks (and four duplicates) can be in any of twelve states.

These kinds of variants are now a bit more common in adventure and puzzle games. The cross of Lights Out has become too recognizable, so creators are looking for something a bit trickier. For example, the Mystery of Time and Space, in addition to having a blatant Lights Out puzzle, has another, more subtle variant later on. In the colorful level 14 puzzle shown below, there are six tiles with four states, and each tile affects a different set of tiles. This variant was also common in Cliff Johnson's 3 in Three. Still more complicated variants appear in Deadly Roooms of Death, like the "Eight Gates of Bill," where switches don't merely toggle; some will always open a gate, and some will always close it.

A Lights Out variant from level 14 of Mystery of Time and Space by Jan AlbartusAnd yet, the simplicity of the Lights Out has remained constant. When Milton Bradley rereleased Merlin in 2004, it changed the Magic Square game so that it toggled squares like Lights Out. And while seasoned puzzlers may find it to be a bit overused, it's still a satisfying puzzle, no matter how many times its solved.

[Tony Delgado is a member of the National Puzzlers' League, and a solver and creater of puzzles of all sorts. He also works as the copy chief of The Gamer's Quarter.]