熄灭游戏算法

Question

这是一个功课.我必须使用回溯描述设计并点亮游戏,如下所示.

游戏包括一个5乘5的网格灯; 当游戏开始时,一组这些灯(随机的,或一组存储的拼图模式中的一个)被打开.按下其中一个灯将打开和关闭它旁边的四个灯.(对角线邻居不会受到影响.)游戏提供了一个难题:给定一些初始配置,其中一些灯亮,一些灯关闭,目标是关闭所有灯,最好按尽可能少的按钮.

我的方法是1到25,检查所有灯是否都关闭.如果没有,那么我将检查1到24,依此类推,直到我达到1或找到解决方案.不,如果没有解决方案,那么我将从2到24开始并按照上述过程直到我达到2或找到解决方案.

但通过这个我没有得到结果？例如,(0,0)(1,1)(2,2)(3,3)(4,4)的光是ON？

如果任何人需要代码,我可以发布它.

任何人都能告诉我使用回溯来解决这个游戏的正确方法吗？

谢谢.

Answer 1

有一种解决这个问题的标准算法,它基于GF(2)上的高斯消元法.我们的想法是设置一个表示按钮的矩阵按下代表灯光的列向量,然后使用标准矩阵简化技术来确定要按哪些按钮.它以多项式时间运行,不需要任何回溯.

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

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

• 任何解决方案永远不会按两次相同的按钮,因为这样做会取消之前的移动.
• 任何解决方案要么按下第一个按钮,要么不按.

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

• 如果您已决定每个按钮,则返回是否已解决该板.
• 除此以外:
  • 尝试按下下一个按钮,看看该板是否可以从那里递归解决.
  • 如果是这样,返回成功.
  • 否则,请不要按下下一个按钮,看看是否可以从那里递归地解决电路板.
  • 如果是这样,返回成功.如果没有,则返回失败.

这将探索大小为2 ²⁵的搜索空间,大约为3200万.这很重要,但并非难以置信的大.

希望这可以帮助!