我正在尝试在 lisp 中实现扫雷求解器。我知道这不是罕见的问题，但我没有找到任何可以帮助我的文章。一开始我有一个雷区作为输入，在未覆盖的字段上带有数字。当找到所有地雷时，算法应该完成。因此，在每一步中，我都必须检查哪些字段可以放入我的已开采领域列表中，并从我的未开采领域列表中选择一个领域并打开它。稍后我会检查我的地雷列表是否已完成，如果是，算法是否已完成。我将不胜感激任何帮助。我不要求源代码，但我需要好的想法。我没有遇到过这种问题。
我必须使用 A* 算法。而且我不需要打开所有未打开的字段...我需要找到所有雷区的位置。当然，它必须是做到这一点的最短路径。当我找到所有雷区的位置时，算法就完成了。所以，再一次，我需要找到所有具有最佳开放字段数量的矿区。当然，我的算法需要一个启发式算法，这将有助于选择所有安全的未打开字段之一。并且需要在每次打开后确定安全未打开字段的列表。所以我需要调用 main 函数，该函数将检查我是否找到了所有挖掘的字段，如果没有，则需要将所有安全的相邻未打开字段添加到路径列表中。并且将选择具有最佳启发式的路径
我在大学的第一年确实实现了扫雷求解器，所以我可以给你一些提示。（这不是使用 A* 算法）
重要 - 并非所有职位都是可解决的。
对于高级难度，回溯整个雷场有点复杂（复杂=需要一些时间，考虑在 30x30 场中放置 100 个地雷的所有可能性）。
您可以在本地解决所有问题，就像人类解决扫雷一样。这样做的潜力是向用户提示如何继续，而不是解决所有问题。
例子：
我希望我没记错，我做了一些证明为什么 5x5 区域足以检查但它几乎是 10 年前。
您不需要 A* 算法；它的目的是找到图中的最短路径（例如地图中两个地方之间的最短路径，或者解决谜题的最小移动量）。您可能想要使用一种称为回溯的技术。
只要有未开垦的田地，就在空地旁边挑出一块未开垦的田地，试探性地将其标记为地雷。然后，查看与前一个字段以及已打开字段相邻的未打开字段，并将该字段也标记为地雷，如果这与相邻数字不矛盾 - 如果确实如此，则将其标记为安全. 继续。最终，您将查看当前区域周围所有未打开的字段，并找到一种将字段标记为安全或不安全的可能方法。然而，这是基于几个猜测，所以现在你需要回到你猜测的最后一个字段，然后进行相反的猜测，然后再次向前移动以获得另一个可能的标志组合。然后，再往前走，修改你的猜测，等等。这可以通过递归非常巧妙地实现。最终，您将拥有一组可能的标志组合。如果您可以在所有可能的标志组合中找到一个安全的字段，请打开该字段。否则，请在尽可能多的标志组合中选择一个安全的字段。