Lights Out Solver

Lights Out (or Flip Tiles game) is an electronic puzzle game composed of a grid of lighted (sometimes with bulbs or switches) or numbered cells (originally 5x5) which consists of turning off all the lights in a grid.

At the start of the game, a pattern of cells is lit (different states). By pressing one of the boxes, it acts like a switch, it changes state (it goes from on to off, or flips from off to on or changes color), as well as the four adjacent boxes (neighboring top, right, bottom and left).

The goal of the game is to switch all the lights to the off (or on) position, preferably by pressing as few boxes as possible.

The player must think about which squares to press to turn off all the lights.

A click on the middle box gives the following result:

(the box clicked as well as the 4 adjacent cells (top, bottom, right, left) have changed state)

For a game with $ n $ states, pressing a box $ n $ times returns it to its initial state.

By hand

— Work row by row (or column by column): start by solving the first row.

— Click on the boxes in the second row to correct the errors in the first.

— Repeat until the last row.

Mathematically

— Represent the grid (initial state of the puzzle) as a vector $ \vec{b} \in \mathbb{F}_2^n $ (with $ \mathbb{F}_2 $ the finite field, 2 corresponding to the number of states)

— Construct the matrix $ A $ of the effects of clicking on the grid ($ A_{ij} = 1 $ if clicking on $ j $ affects $ i $).

— Solve the system $ A \vec{x} = \vec{b} $ in $ \mathbb{F}_2 $.

With a solver

— Specify the initial state of the grid and the number of possible states (usually 2 for black/white or on/off)

— Click on solve

No, not all configurations are solvable.

If all lines are solved except the last row and it can be turned off by clicking only the last row, then the configuration is solvable, otherwise it is unsolvable.

Mathematically, solvability depends on the image of the matrix $ A $. A configuration $ \vec{b} $ is solvable if and only if it belongs to the image of $ A $ in $ \mathbb{F}_2^n $

There are several variations and options in Lights Out:

— Grid size: Various grid formats are possible, ranging from 3x3, 4x4, 5x5, 6x6 to larger or even rectangular grid sizes (dCode accepts any square or rectangular grid size).

— Random or defined starting state: Lights can start in various configurations (dCode accepts any initial state).

— Empty or defined final state: Lights may need to be in a specific final configuration (dCode only accepts a uniform final state of all off or all on, but it is possible to return to a defined final state by solving the initial state and then the final state: the state changes required to turn off a configuration are the same as those required to turn it on).

— Cross or custom pattern: The cross pattern of neighboring cells can be customized to affect other cells (dCode accepts any 3x3 pattern; the center cell can also remain unchanged).

— Limited actions: The number of allowed state changes can be restricted to increase difficulty (use dCode to obtain the solution with the minimum number of moves)

— Timed game: A countdown can add an extra challenge to completing the game within a given time limit (use dCode to get the solution quickly)

— Obstacles: Some variants introduce black squares that cannot be changed (dCode does not handle inert cells, but if dCode provides a solution, then it is valid whether or not there are black/empty cells, if dCode does not provide a solution, try changing the initial state to 1 for one or more of these cells)

An effective strategy is to observe the patterns and symmetries in the grid, if there are any, then carry out symmetrical actions: bulb on the right then bulb on the left etc.

The optimal strategy, however, is to perform linear algebra mathematical calculations that allow all the grids to be mathematically resolved.