熄灯 - 寻找最差的初始状态
Lights Out - finding worst initial state
我有一个任务围绕着一个小游戏，叫做 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];
}
}
}
算法
如果可能的话，我也会对解决或证明这个问题的纯数学论证感兴趣，而无需编写通过尝试解决它的代码。
我提出了一个基于图论的迭代解决方案来解决这个问题（以及相关问题）。
最短路径问题 (SSP)
问题可以重新表述为shortest-path-problem and, by that, be solved with any standard SPP algorithm, for example Dijkstr's algorithm。
为此，我们将所有可能的游戏板解释为顶点，将单击单元格的动作解释为图形的边。
例如
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 个可能的移动.
根据 Zabuzard 的答案将谜题视为图形，然后从已解决的节点开始执行广度优先搜索。您到达的最后一个节点位于具有最长最短路径的集合中。
“熄灯”问题可以通过观察移动 commutative 来简化，即如果您翻转以特定单元格为中心的加号形状，那么顺序无关紧要您将它们翻转过来。因此不需要通过图形的实际有序路径。我们还可以观察到每一步都是自逆的，所以没有解决方案需要多次进行相同的移动，如果一组移动 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步全部走
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.
我提出的解决方案完全基于线性代数。
棋盘矩阵
游戏可以解释为一组线性方程，可以使用标准线性方程求解技术求解。
为此，游戏板被解释为矩阵 。
总共有 9 个可能的操作（一个用于单击面板的每个单元格）。我们在 9 个对应的矩阵中对每个动作必须翻转哪些单元格进行编码：
其中 是与单击行 i 和列 j 中的单元格对应的操作矩阵。
动作是可交换的和自逆的
由于条目在 中，将动作应用到给定的面板就像将相应的动作矩阵添加到面板矩阵一样简单。例如：
这意味着应用一组动作只不过是一些矩阵加法。矩阵加法 可交换。这意味着它们的应用顺序无关紧要：
此外，任何动作矩阵 在加法时 自逆 。再次应用它会撤消操作，即
因此，对于任何初始游戏板，我们最多只需应用每个动作一次，执行顺序无关紧要。
线性方程组
这导致等式：
对于初始游戏板矩阵L，系数如果应该应用动作则为1，否则0； 1 是表示游戏获胜的全一矩阵。
等式可以通过将 L 移到另一边来简化：
其中 L* 是 L 但所有单元格都翻转了。
最后，这个方程可以改写为标准线性方程组Ax = b，然后可以很容易地求解：
由于此矩阵具有最大秩 and a non-zero determinant , the game on a 3x3 board is always solvable and a solution is given by simply solving the linear equation system or by applying Cramer's rule。
最差初始板
由此可见，最差的初始棋盘是一个矩阵 L，它使所使用的系数 最大化，理想情况下所有 9.
结果
0 1 0
1 0 1
0 1 0
就是这样一块初始板，需要设置全部9个系数才能求解。 IE。求解系统
只产生一个解，即 对所有 i, j。
这也可以通过将所有系数设置为 1 并求解 L 而从相反的方向获得：
产生
0 1 0
1 0 1
0 1 0
再次 L。
我有一个任务围绕着一个小游戏，叫做 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];
}
}
}
算法
如果可能的话，我也会对解决或证明这个问题的纯数学论证感兴趣，而无需编写通过尝试解决它的代码。
我提出了一个基于图论的迭代解决方案来解决这个问题（以及相关问题）。
最短路径问题 (SSP)
问题可以重新表述为shortest-path-problem and, by that, be solved with any standard SPP algorithm, for example Dijkstr's algorithm。
为此，我们将所有可能的游戏板解释为顶点，将单击单元格的动作解释为图形的边。
例如
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 个可能的移动.
根据 Zabuzard 的答案将谜题视为图形，然后从已解决的节点开始执行广度优先搜索。您到达的最后一个节点位于具有最长最短路径的集合中。
“熄灯”问题可以通过观察移动 commutative 来简化，即如果您翻转以特定单元格为中心的加号形状，那么顺序无关紧要您将它们翻转过来。因此不需要通过图形的实际有序路径。我们还可以观察到每一步都是自逆的，所以没有解决方案需要多次进行相同的移动，如果一组移动 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步全部走
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.
我提出的解决方案完全基于线性代数。
棋盘矩阵
游戏可以解释为一组线性方程，可以使用标准线性方程求解技术求解。
为此，游戏板被解释为矩阵
总共有 9 个可能的操作（一个用于单击面板的每个单元格）。我们在 9 个对应的矩阵中对每个动作必须翻转哪些单元格进行编码：
其中 i 和列 j 中的单元格对应的操作矩阵。
动作是可交换的和自逆的
由于条目在
这意味着应用一组动作只不过是一些矩阵加法。矩阵加法 可交换。这意味着它们的应用顺序无关紧要：
此外，任何动作矩阵
因此，对于任何初始游戏板，我们最多只需应用每个动作一次，执行顺序无关紧要。
线性方程组
这导致等式：
对于初始游戏板矩阵L，系数1，否则0； 1 是表示游戏获胜的全一矩阵。
等式可以通过将 L 移到另一边来简化：
其中 L* 是 L 但所有单元格都翻转了。
最后，这个方程可以改写为标准线性方程组Ax = b，然后可以很容易地求解：
由于此矩阵具有最大秩
最差初始板
由此可见，最差的初始棋盘是一个矩阵 L，它使所使用的系数 9.
结果
0 1 0
1 0 1
0 1 0
就是这样一块初始板，需要设置全部9个系数才能求解。 IE。求解系统
只产生一个解，即 i, j。
这也可以通过将所有系数设置为 1 并求解 L 而从相反的方向获得：
产生
0 1 0
1 0 1
0 1 0
再次 L。