我有一个围绕一个小游戏的任务，叫做熄灯 https://en.wikipedia.org/wiki/Lights_Out_(game).
Game
该游戏由尺寸为 3x3 的棋盘组成，其中每个单元格可以为 1 或 0，例如：
0 1 0
1 1 0
0 0 0
当所有单元格都为 1 时，据说游戏已解决，因此：
1 1 1
1 1 1
1 1 1
并且每次用户都可以单击任何单元格，该单元格将翻转其状态以及左、右、上、下邻居的状态（如果存在）。因此，单击第一个示例板中间的单元格将产生：
0 0 0
0 0 1
0 1 0
Task
现在我必须找到游戏中可能最差的初始棋盘，并计算出如果发挥最佳效果，需要多少回合才能达到解决状态。
Attempt
我尝试编写一个递归求解器，在给定初始棋盘的情况下，它可以找到解决游戏的最佳回合顺序。之后我想给它提供所有可能的初始板。
然而，递归会遇到堆栈溢出。所以我可能必须以迭代的方式重写它。我怎样才能做到这一点？
这是代码，作为最小的完整示例：
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];
}
}
}
算法
如果可能的话，我也会对纯数学论证感兴趣，这些论证可以解决或证明这个问题，而无需编写通过尝试来解决它的代码。
