Lights Out - finding worst initial state

Question

I have a task revolving around a small game, called Lights Out.

---

Game

The game consists of a board with dimensions 3x3, where each cell can either be 1 or 0, for example:

0 1 0
1 1 0
0 0 0

the game is said to be solved when all cells are 1, so:

1 1 1
1 1 1
1 1 1

and in each turn the user can click any cell which will flip its state and the state of the neighbors to the left, right, above and below (if they exist). So clicking on the cell in the middle of the first example board will yield:

0 0 0
0 0 1
0 1 0

---

Task

Now I have to find the worst possible initial board for the game and also figure out how many turns it needs to the solved state if played optimal.

---

Attempt

I tried to write a recursive solver which, given an initial board, finds the optimal sequence of turns to solve the game. And after that I wanted to feed it with all possible initial boards.

However, the recursion runs into a stack overflow. So I probably have to rewrite it in an iterative fashion. How can I do that?

Here is the code, as minimal complete example:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringJoiner;
import java.util.stream.Collectors;
 
public class GameTest {
    public static void main(String[] args) {
        boolean[][] board = {
            {false, false, false},
            {false, true, false},
            {false, false, false}
        };
        List<GameState> solutionPath = GameSolver.solve(board);
 
        printSolutionPath(solutionPath);
    }
 
    private static void printSolutionPath(List<GameState> solutionPath) {
        System.out.printf("Solution path uses %d turns%n", solutionPath.get(solutionPath.size() - 1).getTurns());
        String turnProgression = solutionPath.stream()
            .map(state -> String.format("[%d|%d]", state.getX(), state.getY()))
            .collect(Collectors.joining(" -> "));
        System.out.println("Turns are: " + turnProgression);
        System.out.println("Board progression is:");
        for (GameState state : solutionPath) {
            System.out.println(state.boardToString());
            System.out.println("-----");
        }
    }
 
    private static class GameSolver {
        public static List<GameState> solve(boolean[][] initialBoard) {
            GameState state = new GameState(initialBoard);
            return solve(state);
        }
 
        public static List<GameState> solve(GameState state) {
            // Base case
            if (state.isSolved()) {
                return List.of(state);
            }
 
            // Explore all other solutions
            List<List<GameState>> solutionPaths = new ArrayList<>();
 
            boolean[][] board = state.getBoard();
            for (int x = 0; x < board.length; x++) {
                for (int y = 0; y < board[x].length; y++) {
                    solutionPaths.add(solve(new GameState(state, x, y)));
                }
            }
 
            List<GameState> bestSolutionPath = Collections.min(solutionPaths, Comparator.comparingInt(solutionPath -> solutionPath.get(solutionPath.size() - 1).getTurns()));
            bestSolutionPath.add(state);
            return bestSolutionPath;
        }
    }
 
    private static class GameState {
        private boolean[][] board;
        private int turns;
        private int x;
        private int y;
 
        public GameState(boolean[][] board) {
            this.board = board;
            turns = 0;
            x = -1;
            y = -1;
        }
 
        public GameState(GameState before, int x, int y) {
            board = before.board;
            click(x, y);
            turns++;
            this.x = x;
            this.y = y;
        }
 
        public boolean isSolved() {
            for (boolean[] row : board) {
                for (boolean state : row) {
                    if (!state) {
                        return false;
                    }
                }
            }
            return true;
        }
 
        public int getTurns() {
            return turns;
        }
 
        public boolean[][] getBoard() {
            return board;
        }
 
        public int getX() {
            return x;
        }
 
        public int getY() {
            return y;
        }
 
        public String boardToString() {
            StringBuilder sb = new StringBuilder();
            for (int x = 0; x < board.length; x++) {
                StringJoiner row = new StringJoiner(" ");
                for (int y = 0; y < board[x].length; y++) {
                    row.add(board[x][y] ? "1" : "0");
                }
                sb.append(row);
            }
            return sb.toString();
        }
 
        private void click(int centerX, int centerY) {
            toggle(centerX, centerY);
 
            toggle(centerX, centerY - 1);
            toggle(centerX, centerY + 1);
 
            toggle(centerX - 1, centerY);
            toggle(centerX + 1, centerY);
        }
 
        private void toggle(int x, int y) {
            if (x < 0 || y < 0 || x >= board.length || y >= board[x].length) {
                return;
            }
 
            board[x][y] = !board[x][y];
        }
    }
}

---

Algorithm

If possible, I would also be interested in pure-mathematical arguments that solve or prove this without writing code that solves it by trying out.

Answer 1

The "Lights Out" problem can be simplified by observing that the moves are commutative, i.e. if you flip the plus-shapes centred on a certain set of cells, then it doesn't matter which order you flip them in. So an actual ordered path through a graph is not needed. We can also observe that each move is self-inverse, so no solution requires making the same move more than once, and if a set of moves m is a solution to a position p, then m also produces the position p starting from an empty board.

Here's a short solution in Python based on this observation: I've solved it for the goal of all 0s, i.e. the "lights" are "out", but it is trivial to change it to solve for the goal of all 1s.

• The constant list masks represents which cells should be flipped for each of the 9 possible moves.
• The bitcount function is used to measure how many moves a solution takes, given a bitmask representing a subset of the 9 possible moves.
• The position function computes the board position after a set of moves is made, using the exclusive-or operation to accumulate the results of multiple flips.
• The positions dictionary maps each reachable board position to a list of move-sets which produce it starting from an empty board. It turns out that all positions are reachable by exactly one set of moves, but if this is not known in advance then a dictionary of lists gives a more general solution.
• The max(..., min(...)) part finds the position maximising the minimum number of moves needed to solve it, as required.

masks = [
    int('110100000', 2), int('111010000', 2), int('011001000', 2),
    int('100110100', 2), int('010111010', 2), int('001011001', 2),
    int('000100110', 2), int('000010111', 2), int('000001011', 2),
]

def bitcount(m):
    c = 0
    while m:
        c += (m & 1)
        m >>= 1
    return c

def position(m):
    r = 0
    for i in range(9):
        if (1 << i) & m:
            r ^= masks[i]
    return r

from collections import defaultdict

positions = defaultdict(list)
for m in range(2**9):
    p = position(m)
    positions[p].append(m)

solution = max(positions, key=lambda p: min(map(bitcount, positions[p])))
print('board:', bin(solution))
print('moves:', ', '.join(map(bin, positions[solution])))

Output:

board: 0b101010101
moves: 0b111111111

That is, the "worst initial position" is an X shape (all four corners plus the centre cell are 1s), and the solution is to perform all 9 moves.

Answer 2

I am proposing an iterative solution to solve this (and related problems) based on graph theory.

Shortest-Path-Problem (SSP)

The problem can be reformulated as shortest-path-problem and, by that, be solved with any standard SPP algorithm, for example Dijkstr's algorithm.

For that, we will interpret all possible game boards as vertices and the action of clicking cells as edges of a graph.

For example

0 1 0
1 1 0
0 0 0

will be a vertex in the graph with 9 outgoing edges in total (one for each cell to click at). So we will for example have an edge

0 1 0     0 0 0
1 1 0 --> 0 0 1
0 0 0     0 1 0

with cost 1. All edge costs will be 1, indicating counting turns.

Given an initial board, like above, we formulate the SPP as the task of finding the shortest path in this graph from the vertex representing the initial board to the vertex representing the solved state

1 1 1
1 1 1
1 1 1

By using standard algorithms for solving SSP we receive the optimal path and its total cost. The path is the sequence of game states and the total cost is the amount of turns needed for that.

---

*-1 SPP

However, you are not only interested in solving given initial boards but also in finding the worst initial board and its optimal amount of turns.

This can be reformulated as a variant of the SPP family, namely trying to find the longest shortest path to the solved state. This is, among all shortest paths in the graph that end in the solved state, the path that maximizes the total cost.

This can be computed efficiently by a *-1 (many-to-one) SPP. That is, computing all shortest paths from any vertex to a single destination, which will be the solved state. And from those picking the path which has the greatest total cost.

Dijkstra's algorithm can compute that easily by executing the algorithm fully on a reversed graph (all edges reverse their direction) with the solved state as source, until it settled the whole graph (removing its stopping criteria).

Note that in your particular case graph reversal is not needed, as the graph in your game is bidirectional (any turn can be undone by executing it again).

---

Solution

Applying the above theory yields a pseudo-code looking like

Graph graph = generateGraph(); // all possible game states and turns

int[][] solvedState = [[1, 1, 1], [1, 1, 1], [1, 1, 1]];
List<Path> allShortestPaths = Dijkstra.shortestPathFromSourceToAllNodes(solvedState);

Path longestShortestPath = Collections.max(allPaths);

Some time ago I created a Java library for solving shortest path problems, Maglev. Using that library, the full code is:

import de.zabuza.maglev.external.algorithms.Path;
import de.zabuza.maglev.external.algorithms.ShortestPathComputationBuilder;
import de.zabuza.maglev.external.graph.Graph;
import de.zabuza.maglev.external.graph.simple.SimpleEdge;
import de.zabuza.maglev.external.graph.simple.SimpleGraph;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;
import java.util.StringJoiner;

public class GameTest {
    public static void main(String[] args) {
        Graph<GameState, SimpleEdge<GameState>> graph = generateGraph();

        var algo = new ShortestPathComputationBuilder<>(graph).resetOrdinaryDijkstra()
                .build();

        GameState solvedState =
                new GameState(new boolean[][] { { true, true, true }, { true, true, true }, { true, true, true } });
        var pathTree = algo.shortestPathReachable(solvedState);

        var longestShortestPath = pathTree.getLeaves()
                .stream()
                .map(pathTree::getPathTo)
                .map(Optional::orElseThrow)
                .max(Comparator.comparing(Path::getTotalCost))
                .orElseThrow();

        System.out.println("The longest shortest path has cost: " + longestShortestPath.getTotalCost());
        System.out.println("The states are:");
        System.out.println(longestShortestPath.iterator().next().getEdge().getSource());
        for (var edgeCost : longestShortestPath) {
            System.out.println("------------");
            System.out.println(edgeCost.getEdge().getDestination());
        }
    }

    private static Graph<GameState, SimpleEdge<GameState>> generateGraph() {
        SimpleGraph<GameState, SimpleEdge<GameState>> graph = new SimpleGraph<>();
        generateNodes(graph);
        generateEdges(graph);
        return graph;
    }

    private static void generateNodes(Graph<GameState, SimpleEdge<GameState>> graph) {
        for (int i = 0; i < 1 << 9; i++) {
            String boardString = String.format("%09d", Integer.parseInt(Integer.toBinaryString(i)));
            graph.addNode(GameState.of(boardString, 3, 3));
        }
    }

    private static void generateEdges(Graph<GameState, SimpleEdge<GameState>> graph) {
        for (GameState source : graph.getNodes()) {
            // Click on each field
            boolean[][] board = source.getBoard();
            for (int x = 0; x < board.length; x++) {
                for (int y = 0; y < board[x].length; y++) {
                    GameState destination = new GameState(board);
                    destination.click(x, y);

                    graph.addEdge(new SimpleEdge<>(source, destination, 1));
                }
            }
        }
    }

    private static class GameState {

        public static GameState of(String boardString, int rows, int columns) {
            boolean[][] board = new boolean[rows][columns];
            int i = 0;
            for (int x = 0; x < rows; x++) {
                for (int y = 0; y < columns; y++) {
                    board[x][y] = boardString.charAt(i) == '1';
                    i++;
                }
            }
            return new GameState(board);
        }

        private final boolean[][] board;

        private GameState(boolean[][] board) {
            this.board = new boolean[board.length][];
            for (int x = 0; x < board.length; x++) {
                this.board[x] = new boolean[board[x].length];
                for (int y = 0; y < board[x].length; y++) {
                    this.board[x][y] = board[x][y];
                }
            }
        }

        public boolean[][] getBoard() {
            return board;
        }

        @Override
        public String toString() {
            StringJoiner rowJoiner = new StringJoiner("\n");
            for (int x = 0; x < board.length; x++) {
                StringJoiner row = new StringJoiner(" ");
                for (int y = 0; y < board[x].length; y++) {
                    row.add(board[x][y] ? "1" : "0");
                }
                rowJoiner.add(row.toString());
            }
            return rowJoiner.toString();
        }

        @Override
        public boolean equals(final Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            final GameState gameState = (GameState) o;
            return Arrays.deepEquals(board, gameState.board);
        }

        @Override
        public int hashCode() {
            return Arrays.deepHashCode(board);
        }

        private void click(int x, int y) {
            toggle(x, y);

            toggle(x, y - 1);
            toggle(x, y + 1);

            toggle(x - 1, y);
            toggle(x + 1, y);
        }

        private void toggle(int x, int y) {
            if (x < 0 || y < 0 || x >= board.length || y >= board[x].length) {
                return;
            }

            board[x][y] = !board[x][y];
        }
    }
}

Which yields the following solution to your problem:

The longest shortest path has cost: 9.0
The states are:
1 1 1
1 1 1
1 1 1
------------
1 0 1
0 0 0
1 0 1
------------
1 0 1
1 0 0
0 1 1
------------
1 1 0
1 0 1
0 1 1
------------
1 1 0
1 0 0
0 0 0
------------
1 1 0
1 1 0
1 1 1
------------
0 0 1
1 0 0
1 1 1
------------
1 0 1
0 1 0
0 1 1
------------
0 1 1
1 1 0
0 1 1
------------
0 1 0
1 0 1
0 1 0

So the worst initial game state is

0 1 0
1 0 1
0 1 0

and, if played optimally, it needs 9 turns to solve the game.

---

Some trivia, the game has 512 states in total (2^9) and 4608 possible moves.

Answer 3

Treat the puzzle as a graph per Zabuzard's answer, then perform breadth-first search starting from the solved node. The last node you reach is among the set having the longest-shortest path to the solution.