algorithm - 熄灯游戏算法

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) 上的高斯消元法。这个想法是建立一个表示按钮按下的矩阵，一个表示灯的列向量，然后使用标准矩阵简化技术来确定要按下的按钮。它以多项式时间运行，不需要任何回溯。

我有一个 implementation该算法的详细信息，包括其工作原理的数学描述，可在我的个人网站上找到。我希望你觉得它有用!

编辑:如果您被迫使用回溯，您可以使用以下事实:

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

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

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

这将探索大小为 2²⁵ 的搜索空间，即大约 3200 万。这很大，但并非无法克服。

希望这对您有所帮助!