熄灯游戏算法

Question

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

游戏

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

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

但是通过这个我没有得到结果？ 例如，（0,0） （1,1） （2,2） （3,3） （4,4） 处的灯亮了？

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

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

谢谢。

Answer 1

有一个

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

我有此算法的实现，其中包括有关其工作原理的数学描述，可在我的个人网站上找到。希望你觉得有用！

编辑：如果您被迫使用回溯，您可以使用以下事实来执行此操作：

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

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

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

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

希望这有帮助！

Answer 2

回

溯意味着：

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;

Answer 3

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

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

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

应有25个这样的变量。

现在，对于每个灯，您可以形成一个方程，如下所示

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

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

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

Answer 4

朴素的解决方案

首先，您需要一种方法来表示电路板的状态，以及一个堆栈来存储所有状态。在每个步骤中，制作板的副本，更改为新状态。将该状态与您到目前为止遇到的所有董事会状态进行比较。如果您还没有看到它，请将该状态推到堆栈顶部，然后继续下一步。如果您已经看到它，请尝试下一步。每个关卡都必须尝试所有可能的 64 个动作，然后才能从堆栈中弹出状态（回溯）。您将需要使用递归来管理要检查的下一个移动的状态。

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

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

贪婪优先搜索

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

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

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

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