Problem 44751. Lights Out 1 - 5x5, 3 moves

Lights Out is a logic game wherein all lights need to be turned off to complete each board. Pressing any button on the board toggles that button as well as adjacent buttons vertically and horizontally, where present (and no wrapping here), to the opposite state (i.e., on to off and off to on). For example, pressing a corner button toggles three button states, an edge button four button states, and an interior button five button states (as can be visualized by the example below).

This first problem uses a 5x5 board and requires that your function return a column-major vector of button presses (indices) that will solve the board by turning off all lights. Since pressing any button twice will return to the same board state, only one move is needed (and allowed) per button. For example, if

 board = [0 1 0 0 0
          1 1 1 0 1
          0 1 0 1 1
          1 0 0 0 1
          1 1 0 0 0]

the answer is:

 moves = [5 7 23]

In this first problem, all boards have solutions of only three moves.

Note: while brute-force solutions will solve some problems in this series, they will time out on later ones. Solving the first few problems by developing a robust solver function is encouraged.

As a potential starting point, you might check out one or more of the following resources by Vicente Muñoz; Chen, et al.; Vincent Russo; Margherita Barile (on; Keith Schwarz; or Rebecca Meyer (a master's thesis).

Next: 5x5, 4 moves

Solution Stats

18.94% Correct | 81.06% Incorrect
Last Solution submitted on Jun 12, 2020

Problem Comments