6

这是一个家庭作业。我必须使用回溯描述来设计和熄灯游戏如下。

游戏由一个 5×5 的灯光网格组成；当游戏开始时，一组这些灯（随机的，或一组存储的拼图图案中的一个）被打开。按下其中一个灯将切换它，以及与之相邻的四个灯，打开和关闭。（对角线邻居不受影响。）游戏提供了一个谜题：给定一些初始配置，其中一些灯亮，一些灯关闭，目标是关闭所有灯，最好尽可能少按按钮。

我的方法是从 1 到 25 并检查所有灯是否都关闭。如果不是，那么我将检查 1 到 24，依此类推，直到达到 1 或找到解决方案。不，如果没有解决方案，那么我将从 2 到 24 开始并按照上述过程直到达到 2 或找到解决方案。

但是通过这个我没有得到结果？例如 (0,0) (1,1) (2,2) (3,3) (4,4) 处的光亮吗？

如果有人需要代码，我可以发布它。

谁能告诉我使用回溯解决这个游戏的正确方法？

谢谢。

4

5 回答 5

13

有一个标准算法可以解决这个问题，它基于 GF(2) 上的高斯消元法。这个想法是建立一个表示按钮按下的矩阵，一个表示灯的列向量，然后使用标准矩阵简化技术来确定要按下哪些按钮。它在多项式时间内运行，不需要任何回溯。

我有一个该算法的实现，其中包括它在我的个人网站上如何工作的数学描述。希望对你有帮助！

编辑：如果您被迫使用回溯，您可以使用以下事实来这样做：

  • 任何解决方案都不会两次按下同一个按钮，因为这样做会取消之前的动作。
  • 任何解决方案要么按下第一个按钮，要么不按下。

鉴于这种方法，您可以使用简单的递归算法使用回溯来解决此问题，该算法跟踪电路板的当前状态以及您已经做出决定的按钮：

  • 如果您已经决定了每个按钮，则返回板子是否已解决。
  • 除此以外：
    • 尝试按下下一个按钮，看看棋盘是否可以从那里递归求解。
    • 如果是，则返回成功。
    • 否则，尽量不要按下下一个按钮，看看棋盘是否可以从那里递归求解。
    • 如果是，则返回成功。如果不是，则返回失败。

这将探索一个大小为 2 25的搜索空间，大约为 3200 万。这很大，但不是不可逾越的大。

希望这可以帮助！

于 2013-11-05T18:45:33.733 回答
1

回溯的意思：

Incrementally build a solution, throwing away impossible solutions.

这是一种利用输入和输出的局部性这一事实的方法（按下按钮会影响它周围的正方形）。

problem = GIVEN
solutions = [[0],[1]] // array of binary matrix answers (two entries, a zero and a one)
for (problemSize = 1; problemSize <= 5; problemSize++) {
    newSolutions = [];
    foreach (solutions as oldSolution) {
        candidateSolutions = arrayOfNByNMatriciesWithMatrixAtTopLeft(min(5,problemSize+1), oldSolution);
        // size of candidateSolutions is 2^((problemSize+1)^2 - problemSize^2)
        // except last round candidateSolutions == solutions
        foreach (candidateSolutions as candidateSolution) {
            candidateProblem = boardFromPressingButtonsInSolution(candidateSolution);
            if (compareMatrix(problem, candidateProblem, 0, 0, problemSize, problemSize)==0)
                newSolutions[] = candidateSolution;
        }
    }
    solutions = newSolutions;
}
return solutions;
于 2013-11-11T19:21:58.700 回答
0

如前所述，您应该首先形成一组联立方程。

首先要注意的是，一个特定的灯光按钮最多只能按下一次，因为两次切换一组灯光是没有意义的。

Let Aij = Light ij Toggled { Aij = 0 or 1 }

应有 25 个这样的变量。

现在对于每个灯，你可以形成一个看起来像的方程 

summation (Amn) = 0. { Amn = 5 light buttons that toggle the light mn }

所以你将有 25 个变量和 25 个未知数。您可以同时求解这些方程。

如果您需要使用回溯或递归来解决它，您可以通过这种方式求解方程。只需假设变量的初始值，看看它们是否满足所有方程。如果没有，则返回原点。

于 2013-11-05T18:28:06.777 回答
0

天真的解决方案

首先，您将需要一种表示棋盘状态的方法和一个存储所有状态的堆栈。在每一步，制作一个板的副本，更改为新的状态。将该状态与您迄今为止遇到的所有董事会状态进行比较。如果您还没有看到它，请将该状态压入堆栈顶部并继续下一步。如果您已经看到它，请尝试下一步。在从堆栈中弹出状态（回溯）之前，每个级别都必须尝试所有可能的 64 次移动。您将需要使用递归来管理下一步检查的状态。

最多有 2 64种可能的板配置，这意味着您可能会进入很长的独特状态链，但仍然会耗尽内存。（作为参考，1 GB 是 2 30个字节，您至少需要 8 个字节来存储板配置）该算法不太可能在已知宇宙的生命周期内终止。

你需要做一些聪明的事情来减少你的搜索空间......

贪心优先搜索

您可以通过首先搜索最接近已解决配置的状态来做得更好。在每一步，按照从最不熄灯到最不熄灯的顺序对可能的移动进行排序。按该顺序迭代。这应该可以很好地工作，但不能保证获得最佳解决方案。

并非所有熄灯谜题都可以解决

无论您使用哪种算法，都可能没有解决方案，这意味着您可能永远（或至少数万亿年）搜索而找不到解决方案。

在浪费任何时间试图找到解决方案之前，您需要检查板的可解性（事实证明这是一种更快的算法）。

于 2017-12-15T22:24:33.523 回答
0

我使用答案集编程制作了一个简洁的优化求解器。见：https ://github.com/jachymb/lights-out

于 2021-02-21T21:04:30.483 回答