Lights Out - finding worst initial state
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.
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
masksrepresents which cells should be flipped for each of the 9 possible moves. - The
bitcountfunction is used to measure how many moves a solution takes, given a bitmask representing a subset of the 9 possible moves. - The
positionfunction computes the board position after a set of moves is made, using the exclusive-or operation to accumulate the results of multiple flips. - The
positionsdictionary 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.