A*算法与小游戏

Question

我正在尝试用lisp语言实现扫雷舰解算器。我知道这不是罕见的问题，但我没有找到任何能帮助我的文章。开始时，我有一个雷场作为输入，在未发现的区域上有数字。当发现所有的地雷时，应该完成算法。因此，在每一步，我必须检查哪些字段可以放在我的雷区列表中，并从我的非雷区列表中选择一个字段并打开它。稍后，我将检查完成的雷区列表，如果是的话，算法已经完成。我很感谢你的帮助。我不需要源代码，但我需要好的想法。我对这种问题没有经验。

我必须使用A*算法。我不需要打开所有未开垦的区域.我需要找到所有雷区的位置。当然，要做到这一点，必须是最短的路径。当我找到所有雷场的位置时，算法就完成了。所以，再一次，我需要找到所有的雷区，有最优的开放面积。当然，我需要一个启发式的算法来帮助选择一个安全的未打开的字段。安全未打开字段的列表需要在每次打开后确定。所以我需要调用main函数，这个函数会检查是否找到了所有的雷区，如果没有，那么所有安全的相邻未打开的字段都需要添加到路径列表中。将选择一条具有最佳启发式的路径。

Answer 1

我在大学的第一年就实现了一个扫雷器，所以我可以给你一些提示。(这不是使用A*算法)

1. 重要的是-并不是所有的位置都是可解决的。
2. 对整个雷场的回溯是有点复杂的先进的困难(complicated=takes一段时间，考虑所有的可能性将100个地雷放置在一个30x30的领域)。
3. 你可以在当地解决一切问题，就像人类解决扫雷船一样。这样做的潜力在于给用户一个提示，告诉他们如何继续，而不是解决所有问题。

示例：

1. 有一个单独的矿场，在那里你可以解决问题
2. 找到所有未解决的单元，有一个已解的(数/已知的地雷)单元足够近(两个细胞距离)。
3. 对于每一个这样的单元，以5x5为中心，找出所有的可能性(回溯)，并检查是否有共同之处(地雷/非地雷)，如果是，你可以检查地雷和发现非地雷。
4. 重复一遍，而你可以发现一些东西。
5. 当你无法发现任何东西，而剩余的地雷数量足够少时，你可以试着在整个战场上回溯。

我希望我记得是正确的，我做了一些证明为什么5x5区域足够检查，但它是近10年前。

Answer 2

您不需要A*算法；它的目的是在图中找到最短路径(例如地图中两处之间的最短路径，或解决谜题的最小移动量)。您可能希望使用一种称为回溯的技术。

只要有未打开的字段，选择一个未打开的字段，旁边是一个开放的领域，并暂时标记为地雷。然后，查看一个未打开的字段，该字段与前一个字段以及打开的字段相邻，如果这与相邻的数字不矛盾，则将该字段标记为矿场--如果它与相邻的数字相矛盾，则将其标记为安全。继续。最终，您将查看围绕当前区域的所有未打开的字段，并找到一种将字段标记为安全或不安全的可能方法。然而，这是基于几个猜测，所以现在您需要返回到最后一个字段，在那里您进行了猜测，然后进行相反的猜测，然后再向前移动以获得另一个可能的标志组合。然后，回到更远的地方，修正你的猜测，等等。这可以很好地用递归来实现。最终，您将拥有一组可能的标志组合。如果可以在所有可能的标志组合中找到安全字段，请打开该字段。否则，选择一个在尽可能多的标志组合中安全的字段。