lights_out

lights_out, a MATLAB code which analyzes the "Lights Out" game, in which lights on a 5x5 board are randomly lit up. Pushing a light reverses its status, as well as the status of the north, south, east and west neighbor lights. The user seeks to push buttons in such a way that all the lights are turned off.

Only some initial states are actually solvable.

A strategy to solve the game begins by driving all the lighted squares to the bottom row. This is done by starting in the second row, and clicking just below any light in the first row. This blacks out row 1. Repeating this process by working downwards results in turning off all the lights except in the last row.

For the 5x5 case, the strategy then depends on the pattern of lights in the bottom row. Depending on that pattern, click lights ON in the first row, and then repeat the process of driving all the lighted squares to the bottom row. This time, you should end with no lights on.

      if bottom is   start top as

         00111            00010
         01010            01001
         01101            10000
         10001            00011
         10110            00001
         11011            00100
         11100            01000
      

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

lights_out is available in a MATLAB version.

Related Data and Programs:

lights_out_game, a MATLAB code which sets up the "Lights Out" game, lighting up a few squares on a grid. An interactive user must then try to press squares in such a way that all the lights are turned off.

Reference:

1. Marlow Anderson, Todd Feil,
   Turning Lights Out With Linear Algebra,
   Mathematics Magazine,
   Volume 71, Number 4, October 1998, pages 300-303.
2. Oscar Martin-Sanchez,
   Two Analyses of Lights Out,
   Mathematics Magazine,
   Volume 74, Number 4, October 2001, pages 295-304.

Source Code:

• ksub_random2.m, returns a random subset of size k from a set of size n.
• lo_dot.m, returns the dot product modulo 2 of two board configurations, used for the solvability test.
• lo_initialize_random.m, randomly initializes the board with ILLUM lights illuminated.
• lo_initialize_solvable.m, randomly initializes the board to a solvable state, using PUSH button pushes.
• lo_light_chase.m, turns off all the lights except for the last row.
• lo_light_chase_top.m, shows how, after doing the light chase algorithm once, you should push buttons at the top to restart the light chase algorithm and finish the puzzle, if it is solvable.
• lo_matrix.m, returns a 25x25 matrix which applies a set of button pushes.
• lo_matrix_index.m, maps indices (i,j) to a single index k in the Lights Out matrix.
• lo_print.m, prints a Lights Out configuration.
• lo_solvability_matrices.m, returns the solvability matrices N1 and N2.
• lo_solvable.m, reports whether a board configuration is solvable.
• lo_update.m, updates the board after button (i,j) has been pushed.