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.
