"Lights Out" Game Optimization Inquiries

Question

I hope things are going well for people. I have what I believe are some interesting questions on the game Lights Out.

Here I

1. Discuss the game
2. Present some integer programming formulations of it
3. Pose the questions
4. Include additional displays

The Game

In Tiger Electronics’ handheld electronic solitaire game Lights Out, the player strives to turnout all $nm$ lights that make up a $n \times m$ grid of cells. On each turn, the player is allowed to click on any one cell. Clicking on a cell activates a switch that causes the states of the cell and its neighbors to change from on to off or from off to on. Corner cells are considered to have two neighbors, edge cells to have three, and interior cells to have four. Linear Optimization/Bosch/4.5.212placed in it does not exceedw, and (2) that if a bin isn’t used, the total weight of the objects placedin it does not exceed0(i.e., no objects are placed in the bin).3.In Tiger Electronics’ handheld electronic solitaire gameLights Out, the player strives to turnout all25lights that make up a5×5grid of cells. On each turn, the player is allowed to click onany one cell. Clicking on a cell activates a switch that causes the states of the cell and its neighborsto change from on to off or from off to on. Corner cells are considered to have two neighbors, edgecells to have three, and interior cells to have four. Formulate an integer programming problem for finding a way to turn off all of the lights in as few presses as possible.

For example, the diagram demonstrates what happens when the player clicks on cells $(1,1)$ and $(1,2)$ for a $5 \times 5$ grid.

$(1,1)$ and $(1,2)$ for a $5 \times 5$ grid" />

A Formulation

Let $x_{i,j}$ equal 1 if cell $(i,j)$ is clicked and $0$ if it is not. Let $N_{i,j}$ denote the set of cells $(i',j')$ that are neighbors of cell $(i,j)$. Then we have the following IPP:

Minimize: $\sum_i \sum_j x_{i,j}$

Subject To: \begin{align} &x_{i,j}=\sum_{(i',j')\in N_{i,j}} x_{i',j'} = 2z_{i,j} + 1 \quad \text{for all } (i,j)\\ &x_{i,j} \in \{0,1\} \quad \text{for all } (i,j)\\ &z_{i,j} \in \{0,1,2\} \quad \text{for all } (i,j)\\ \end{align}

The Questions

• Suppose you decide to start with some random state of on / off lights (see the image below). Is there always a way to solve the Lights Out problem regardless of the starting state?
• Instead of considering an $n \times m$ grid, imagine we have a arbitrary collection of $z$ cells in no particular shape. They can be in a line for example or a $10 \times 2$ rectangle with individual cell jutting out here and there, but each cell must have at least one side touching another cell, so there are no cells "out in the open", they are all connected in some way (I lack the knowledge to explain what exact property this is but just know that all cells have at least one side touching another cell). What are the properties of the Lights Out game in this case? Can it always be solved for any conglomerate of cells?

$n \times n$ case" />

Some n x n Displays

I wrote Python code that uses Gurobi to solve the $5 \times 5$ case and creates these displays. If you would like the code please comment so. These are to further facilitate understanding of the Lights Out game.

10 x 10 grid with 15 random presses

5 x 5 grid solved