java - Lights Out - 寻找最坏的初始状态

Question

我有一个围绕一个小游戏的任务，名为 Lights Out .

游戏
游戏由一个尺寸为 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

任务
现在我必须为游戏找到最糟糕的初始棋盘，并计算出如果玩得最佳，它需要多少回合才能达到已解决状态。

试图
我试图编写一个递归求解器，在给定初始棋盘的情况下，它会找到解决游戏的最佳回合顺序。在那之后，我想用所有可能的初始板来喂养它。
但是，递归遇到堆栈溢出。所以我可能不得不以迭代的方式重写它。我怎样才能做到这一点？
这是代码，作为最小的完整示例:

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];
        }
    }
}

算法
如果可能的话，我也会对解决或证明这一点的纯数学论证感兴趣，而无需编写通过尝试来解决它的代码。

Answer 1

我提出了一个基于图论的迭代解决方案来解决这个(和相关问题)。
最短路径问题 (SSP)
该问题可以重新表述为 shortest-path-problem并且，通过这个，可以用任何标准的 SPP 算法来解决，例如 Dijkstr's algorithm .
为此，我们将所有可能的游戏板解释为顶点，将单击单元格的 Action 解释为图形的边。
例如

0 1 0
1 1 0
0 0 0

将是图中的一个顶点，总共有 9 个传出边(每个单元格一个要单击的边)。所以我们将例如有一个优势

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

与成本 1 .所有边缘成本将为 1 ，表示计数轮次。
给定一个初始板，如上所示，我们将 SPP 公式化为在该图中找到最短路径的任务，从表示初始板的顶点到表示求解状态的顶点

1 1 1
1 1 1
1 1 1

通过使用标准算法解决 SSP，我们可以得到最优路径及其总成本。路径是游戏状态的序列，总成本是所需的回合数。

*-1 SPP
但是，您不仅对求解给定的初始棋盘感兴趣，而且对找到最差的初始棋盘及其最佳回合数感兴趣。
这可以重新表述为 SPP 系列的变体，即试图找到 最长最短路径到解决状态。这是图中所有以求解状态结束的最短路径中，使总成本最大化的路径。
这可以通过 *-1 有效地计算出来。 (多对一)SPP。也就是说，计算从任何顶点到单个目的地的所有最短路径，这将是求解状态。并且从那些选择总成本最高的路径中选择。
Dijkstra 的算法可以通过在以求解状态为源的反转图(所有边都反转其方向)上完全执行算法来轻松计算，直到它解决了整个图(删除其停止标准)。
请注意，在您的特定情况下，不需要图形反转，因为您游戏中的图形是双向的(可以通过再次执行来撤消任何回合)。

解决方案
应用上述理论产生一个伪代码，看起来像

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);

前段时间我创建了一个Java库来解决最短路径问题，Maglev .使用该库，完整代码为:

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];
        }
    }
}

这为您的问题产生了以下解决方案:

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

所以最糟糕的初始游戏状态是

0 1 0
1 0 1
0 1 0

而且，如果以最佳方式进行游戏，则需要 9 轮才能解决游戏。

一些小知识，游戏有 512 个州 总共 ( 2^9 ) 和 4608 个可能的移动 .