这是一个功课。我必须使用回溯描述设计并点亮游戏，如下所示。
游戏包括一个5乘5的网格灯;当游戏开始时，一组这些灯（随机的，或一组存储的拼图模式中的一个）被打开。按下其中一个灯将打开和关闭它旁边的四个灯。 （对角线邻居不会受到影响。）游戏提供了一个难题：给定一些初始配置，其中一些灯亮，一些灯关闭，目标是关闭所有灯，最好按尽可能少的按钮。
我的方法是1到25，检查所有灯是否都关闭。如果没有，那么我将检查1到24，依此类推，直到我达到1或找到解决方案。不，如果没有解决方案，那么我将从2到24开始并按照上述过程直到我达到2或找到解决方案。
但通过这个我没有得到结果？例如，（0,0）（1,1）（2,2）（3,3）（4,4）的光是ON？
如果任何人需要代码，我可以发布它。
任何人都能告诉我使用回溯来解决这个游戏的正确方法吗？
谢谢。
有一种解决这个问题的标准算法，它基于GF（2）上的高斯消元法。我们的想法是设置一个表示按钮的矩阵按下代表灯光的列向量，然后使用标准矩阵简化技术来确定要按哪些按钮。它以多项式时间运行，不需要任何回溯。
我有一个这个算法的implementation，其中包括我个人网站上如何工作的数学描述。希望对你有帮助！
编辑：如果您被迫使用回溯，您可以使用以下事实来执行此操作：
有了这种方法，您可以使用回溯来解决这个问题，使用简单的递归算法来跟踪电路板的当前状态以及您已经做出决定的按钮：
这将探索225大小的搜索空间，大约3200万。这很重要，但并非难以置信的大。
希望这可以帮助！
回溯意味着：
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;
如前所述，您应首先形成一组联立方程。
首先要注意的是，一个特定的灯按钮最多应按一次，因为将灯组切换两次是没有意义的。
Let Aij = Light ij Toggled { Aij = 0 or 1 }
应该有25个这样的变量。
现在对于每个灯光，你可以形成一个看起来像的方程式
summation (Amn) = 0. { Amn = 5 light buttons that toggle the light mn }
所以你将有25个变量和25个未知数。您可以同时解决这些方程式。
如果您需要使用回溯或递归来解决它，您可以通过这种方式求解方程式。只需假设变量的初始值，看它们是否满足所有方程式。如果没有，那么回溯。
首先，您需要一种方法来表示电路板的状态和堆栈来存储所有状态。在每一步，制作一块板，改为新的状态。将该状态与您目前遇到的所有董事会状态进行比较。如果您还没有看到它，请将该状态推到堆栈顶部并继续下一步。如果您已经看过它，请尝试下一步行动。在从堆栈弹出状态（回溯）之前，每个级别都必须尝试所有可能的64个移动。您将需要使用递归来管理下一步要检查的状态。
最多有264种可能的电路板配置，这意味着您可能会进入一长串独特的状态并且仍然会耗尽内存。 （作为参考，1 GB是230字节，您需要至少8个字节来存储电路板配置）此算法不太可能在已知Universe的生命周期内终止。
你需要做一些聪明的事情来减少你的搜索空间......
您可以通过首先搜索最接近已解决配置的状态来做得更好。在每个步骤中，按照从大多数灯关闭到最少灯关闭的顺序对可能的移动进行排序。按顺序迭代。这应该可以很好地工作，但不能保证获得最佳解决方案。
无论您使用什么算法，都可能没有解决方案，这意味着您可能永远搜索（或至少几万亿年），而无需找到解决方案。
在浪费任何时间试图找到解决方案之前，您需要检查电路板的可解决性（事实证明这是一个更快的算法）。