这是一项作业。我必须使用以下回溯描述来设计和点亮游戏。
游戏由5 x 5的网格灯组成；游戏开始时，其中的一组指示灯（随机或一组已存储的拼图图案中的一个）会打开。按下其中一个灯将打开和关闭它旁边的四个灯。（对角邻居不会受到影响。）该游戏提供了一个难题：给定一些初始配置，其中一些指示灯点亮，而另一些指示灯熄灭，目标是关闭所有指示灯，最好是尽可能少地按下按钮。
我的方法是从1转到25，并检查所有灯是否熄灭。如果没有，那么我将检查1到24，依此类推，直到达到1或找到解决方案。否，如果没有解决方案，那么我将从2开始到24，然后按照上述过程进行操作，直到达到2或找到解决方案为止。
但是通过这个我没有得到结果吗？例如（0,0）（1,1）（2,2）（3,3）（4,4）处的灯是否点亮？
如果有人需要代码，我可以将其发布。
有人能告诉我使用回溯解决此游戏的正确方法吗？
谢谢。
有一个基于GF（2）的高斯消除的标准算法可以解决此问题。这个想法是建立一个代表按钮的矩阵，该矩阵按下代表灯的列向量，然后使用标准矩阵简化技术确定要按下的按钮。它以多项式时间运行，不需要任何回溯。
我有一个执行这个算法，包括它是如何工作可在我的个人网站的数学描述。希望对你有帮助！
编辑 ：如果您被迫使用回溯，则可以使用以下事实来做到这一点：
使用这种方法，您可以使用简单的递归算法通过回溯来解决此问题，该算法可以跟踪电路板的当前状态以及您已经做出以下决定的按钮：
这将探索大小为2 25的搜索空间，大约为3200万。那很大，但并非无法克服。
希望这可以帮助！
