我有一个围绕着一个小游戏的任务，叫做熄灯。
游戏
游戏由一块尺寸为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];
}
}
}算法
如果可能的话，我也会感兴趣的纯数学参数，解决或证明这一点，而不写代码，解决它的尝试。
4条答案
按热度按时间nzk0hqpo1#
“熄灯”问题可以通过观察移动是可交换的来简化，也就是说，如果你翻转以某一组单元格为中心的加号形状，那么翻转它们的顺序无关紧要。因此不需要通过图的实际有序路径。我们还可以观察到，每个移动都是自逆的，因此没有解决方案需要多次执行相同的移动，如果一组移动
m是解决问题的方法p，那么m也产生位置p从一块空木板开始。基于这一观察，python中有一个简短的解决方案：我已经为所有0的目标解决了这个问题，即“灯光”是“熄灭”的，但是将它改为为为所有1的目标是微不足道的。
常量列表
masks表示9个可能的移动中的每一个都应翻转哪些单元格。这个
bitcount函数用于测量一个解决方案的移动次数，给定一个表示9个可能移动的子集的位掩码。这个
position函数在执行一组移动后计算板的位置，使用异或运算来累加多次翻转的结果。这个
positions字典将每个可到达的电路板位置Map到从空电路板开始产生它的移动集列表。事实证明，所有的位置都可以通过一组移动到达，但是如果事先不知道这一点，那么列表字典给出了一个更一般的解决方案。这个
max(..., min(...))零件根据需要找到位置，使求解它所需的最小移动次数最大化。输出：
也就是说，“最差初始位置”是一个x形状（所有四个角加上中心单元格都是1），解决方案是执行所有9个移动。
lrpiutwd2#
如果可能的话，我也会感兴趣的纯数学参数，解决或证明这一点，而不写代码，解决它的尝试。
我提出了一个完全基于线性代数的解决方案。
板作为矩阵
游戏可以解释为一组线性方程组，可以用标准的线性方程求解技术来求解。
为此，游戏板被解释为矩阵
.
总共有9个可能的操作（一个用于单击电路板的每个单元格）。我们在9个相应的矩阵中编码每个动作必须翻转的细胞：
哪里
是对应于行中单击单元格的动作矩阵
i和列j.动作是可交换的和自逆的
因为条目在
，将动作应用到给定的板上，只需将相应的动作矩阵添加到板矩阵即可。例如：
这意味着应用一组操作只不过是一些矩阵加法。矩阵加法是交换的。这意味着它们的应用顺序无关紧要：
此外，任何行动矩阵
在加法上是自逆的。再次应用它将撤消操作，即。
因此，对于任何初始游戏板，我们最多只需应用一次每个动作，并且我们执行的顺序并不重要。
线性方程组
这导致了以下等式：
与最初的游戏板矩阵
L，系数哪些是
1如果行动应该应用，否则
0; 以及1是表示游戏获胜的全一矩阵。方程可以通过移动来简化
L另一边：哪里
L*是L但是所有的细胞都翻转了。最后，这个方程可以改写成标准的线性方程组
Ax = b这就很容易解决了：因为这个矩阵有最大秩
一个非零行列式
在3x3棋盘上的博弈总是可解的，通过简单求解线性方程组或应用cramer规则给出了一个解。
最差初始板
也就是说，最差的初始板是一个矩阵
L使系数最大化正在使用，最好是所有
9.结果是
是这样一个初始的董事会，需要所有9个系数来设定一个解决方案。i、 e.解决系统问题
只产生一个解决方案，即
对所有人
i, j.这也可以通过将所有系数设置为
1以及解决L取而代之的是：这就产生了
为了
L再一次。rqqzpn5f3#
根据zabuzard的答案将谜题视为一个图，然后从解出的节点开始执行广度优先搜索。您到达的最后一个节点是到解决方案具有最长最短路径的集合中的一个。
bcs8qyzn4#
我提出了一个迭代的解决方案来解决这个（和相关的问题）基于图论。
最短路径问题
该问题可以转化为最短路径问题，并且可以用任何标准的spp算法来求解，例如dijkstr算法。
为此，我们将所有可能的游戏板解释为顶点，单击单元格的动作解释为图形的边。
例如
将是图中的一个顶点，共有9条出站边（每个单元格单击一条）。例如，我们会有优势
有成本的
1. 所有边缘成本1，表示计数圈数。给定一个初始电路板（如上所述），我们将spp描述为在图中从表示初始电路板的顶点到表示已求解状态的顶点之间寻找最短路径的任务
通过使用标准算法求解ssp，我们得到了最优路径及其总代价。路径是游戏状态的序列，总成本是需要的回合数。
*-1个spp
但是，您不仅对求解给定的初始板感兴趣，而且还对寻找最差的初始板及其最佳圈数感兴趣。
这可以被重新表述为spp族的一个变体，即试图找到到达已求解状态的最长最短路径。这是图中所有以求解状态结束的最短路径中，使总成本最大化的路径。
这可以通过
*-1（多对一）spp。也就是说，计算从任何顶点到单个目的地的所有最短路径，这将是求解状态。从那些选择了总成本最大的道路。dijkstra的算法可以很容易地计算出来，方法是在一个以解的状态为源的反转图（所有边都反转方向）上完全执行算法，直到它解决了整个图（去掉停止条件）。
请注意，在您的特殊情况下，图形反转是不需要的，因为您的游戏中的图形是双向的（任何回合都可以通过再次执行它来撤消）。
解决方案
应用上述理论产生一个伪代码
不久前，我创建了一个用于解决最短路径问题的java库maglev。使用该库，完整代码是：
这将为您的问题提供以下解决方案：
所以最糟糕的初始游戏状态是
而且，如果发挥最佳，它需要9轮来解决游戏。
一些琐事，游戏共有512个州(
2^9)以及4608个可能的动作。