Lights Out

Lights Out is a logic puzzle played on a grid of lights, each of which can be on or off. Pressing any light toggles it and all of its orthogonally adjacent neighbors (up, down, left, right). The goal is to turn off all the lights. The puzzle is deceptively challenging because every move affects multiple lights, and turning one off might turn others on. The classic version uses a 5x5 grid, but the concept works on any grid size.

Rules

1. The game starts with a grid of lights, some on and some off (or all on in the classic version).
2. Pressing a light toggles its state (on becomes off, off becomes on).
3. Pressing a light also toggles all directly adjacent lights (up, down, left, right — not diagonals).
4. The goal is to turn all lights off.
5. Pressing the same light twice cancels out, so each light only needs to be pressed once or not at all.

Strategies

• Order Does Not Matter: The final state depends only on which lights were pressed, not the order. This means you can plan your solution without worrying about sequence.
• Each Light Pressed At Most Once: Since pressing a light twice returns it (and its neighbors) to the original state, an optimal solution never presses the same light more than once.
• Light Chasing (Top-Down): Start from the top row. For each lit cell in a row, press the cell directly below it to turn it off. This "chases" the lights downward. After processing all rows, only the bottom row may still have lights on.
• Wrap-Around Fix: After light chasing, if the bottom row still has lights on, specific patterns in the top row must be toggled before chasing again. There are known lookup tables for which top-row presses fix each bottom-row pattern.
• Linear Algebra Approach: The puzzle can be modeled as a system of linear equations over GF(2) (the field with two elements, 0 and 1). Each button press is a vector, and the solution is a combination of vectors that produces the target state. Not all initial configurations are solvable.
• Quiet Patterns: Some combinations of presses leave the board unchanged. Understanding these "null patterns" helps identify whether a puzzle has a solution and find alternative solutions.

Lights Out was originally released as an electronic handheld game by Tiger Electronics in 1995. The device featured a 5x5 grid of backlit buttons and became a popular toy and puzzle. The game presented players with random starting configurations and challenged them to turn off all the lights.

However, the underlying mathematical concept predates the commercial product by decades. The toggle mechanic — where pressing one element affects its neighbors — was studied in mathematics as early as the 1960s in the context of sigma automata and cellular automata. The mathematical theory behind the puzzle involves linear algebra over finite fields, specifically GF(2), where addition is equivalent to the XOR operation.

The puzzle gained significant attention from mathematicians and computer scientists. In 1998, Marlow Anderson and Todd Feil published a thorough mathematical analysis showing that exactly 4 of the 2^25 (about 33.5 million) possible starting configurations of the 5x5 grid are unsolvable. They also demonstrated that the solvable configurations can always be completed in at most 15 moves. The analysis uses eigenvalues of the adjacency matrix over GF(2), connecting the puzzle to graph theory and linear algebra in elegant ways.

Tiger Electronics released a sequel called "Lights Out 2000" with a 6x6 grid, and the concept has been widely adapted in video games, appearing as a puzzle mechanic in adventure games, RPGs, and puzzle compilations. Variants include hexagonal grids, toroidal (wrap-around) grids, and versions with more than two light states. The puzzle remains a staple of recreational mathematics and is frequently used in university courses to illustrate applications of linear algebra.