小编典典

熄灭游戏算法

algorithm

这是一项作业。我必须使用以下回溯描述来设计和点亮游戏。

游戏由5 x
5的网格灯组成;游戏开始时,其中的一组指示灯(随机或一组已存储的拼图图案中的一个)会打开。按下其中一个灯将打开和关闭它旁边的四个灯。(对角邻居不会受到影响。)该游戏提供了一个难题:给定一些初始配置,其中一些指示灯点亮,而另一些指示灯熄灭,目标是关闭所有指示灯,最好是尽可能少地按下按钮。

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

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

如果有人需要代码,我可以将其发布。

有人能告诉我使用回溯解决此游戏的正确方法吗?

谢谢。


阅读 248

收藏
2020-07-28

共1个答案

小编典典

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

我有一个执行这个算法,包括它是如何工作可在我的个人网站的数学描述。希望对你有帮助!

编辑 :如果您被迫使用回溯,则可以使用以下事实来做到这一点:

  • 任何解决方案都永远不会按两次相同的按钮,因为这样做会取消先前的动作。
  • 任何解决方案都可以按第一个按钮,也可以不按。

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

  • 如果您已经决定了每个按钮,则返回是否解决了电路板。
  • 除此以外:
    • 尝试按下一个按钮,查看板子是否可以从那里递归求解。
    • 如果是这样,则返回成功。
    • 否则,请尝试 不要 按下一个按钮,并从那里看板是否可以递归求解。
    • 如果是这样,则返回成功。如果不是,则返回失败。

这将探索大小为2 25的搜索空间,大约为3200万。那很大,但并非无法克服。

希望这可以帮助!

2020-07-28