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

“熄灯”问题可以通过观察移动是可交换的来简化，即，如果您翻转以一组特定单元格为中心的加号形状，那么翻转它们的顺序并不重要。因此，实际的有序不需要通过图形的路径。我们还可以观察到，每个移动都是自逆的，因此没有解决方案需要多次进行相同的移动，并且如果一组移动m是一个位置 的解决方案p，那么也会产生从空棋盘开始的m位置。p

以下是基于此观察的 Python 简短解决方案：我已针对全 0 的目标解决了它，即“灯”“熄灭”，但更改它以解决全 1 的目标是微不足道的。

• 常量列表masks表示 9 种可能的移动中的每一种应该翻转哪些单元格。
• 该bitcount函数用于测量解决方案需要多少次移动，给定一个表示 9 个可能移动的子集的位掩码。
• 该position函数在进行一组移动后计算棋盘位置，使用异或运算来累积多次翻转的结果。
• 字典positions将每个可到达的棋盘位置映射到从空棋盘开始生成它的移动集列表。事实证明，所有位置都可以通过一组移动到达，但如果事先不知道这一点，那么列表字典会给出更通用的解决方案。
• 该max(..., min(...))部件根据需要找到最大化解决该问题所需的最少移动次数的位置。

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

输出：

board: 0b101010101
moves: 0b111111111

即“最差初始位置”是一个X形状（所有四个角加上中心单元格都是1），解决方案是执行所有9次移动。