我正在尝试用 lisp 实现扫雷求解器。我知道这并不是罕见的问题，但我没有找到任何文章可以帮助我解决这个问题。一开始，我有一个雷区作为输入，其中包含未覆盖区域上的数字。当发现所有地雷时，算法应该完成。因此，在每一步中，我都必须检查可以将哪些字段放入我的开采字段列表中，并从我的未开采字段列表中选择一个字段并将其打开。稍后我将检查我的雷区列表是否已完成，如果是，则算法已完成。我将不胜感激任何帮助。我不要求源代码，但我需要好主意。我对此类问题没有经验。
我必须使用A*算法。而且我不需要打开所有未打开的区域...我需要找到所有雷区的位置。当然，它必须是做到这一点的最短路径。当我找到所有雷区的位置时，算法就完成了。因此，我需要再次找到具有最佳开放区域数量的所有雷区。当然，我的算法需要一种启发式算法，这将有助于选择所有安全的未打开字段之一。 每次打开后都需要确定安全未打开字段的列表。所以我需要调用主函数，该函数将检查我是否找到所有挖掘的字段，如果没有，则需要将所有安全相邻的未打开字段添加到路径列表中。并且将选择具有最佳启发式的路径
最佳答案
我在大学的第一年确实实现了一个扫雷求解器，所以我可以给你一些提示。 (这不是使用A*算法)
重要提示 - 并非所有头寸都可以解决。
对于高级困难来说，回溯整个雷区有点复杂(复杂=需要一些时间，考虑在 30x30 区域放置 100 个地雷的所有可能性)。
您可以在本地解决所有问题，就像人类解决扫雷游戏一样。这样做的潜力是给用户一个如何继续的提示，而不是解决所有问题。
示例:
- 拥有一个单独的雷区，您可以在其中进行求解
- 查找所有 Unresolved 单元格，这些单元格具有足够近(2 个单元格距离)的已解决(数字/已知矿井)单元格
- 对于每个这样的单元格，取一个以该单元格为中心的 5x5 邻域，找到每种可能性(回溯)并检查这些可能性是否有共同点(地雷/非地雷)，如果有，则可以检查地雷并发现非地雷。
- 重复一遍，直到你能发现一些东西。
- 当你无法发现任何东西并且剩余地雷数量足够少时，你可以尝试在整个 field 上回溯。
我希望我没记错，我做了一些证明，为什么 5x5 的区域足以检查，但那是差不多 10 年前的事了。
关于graph - A* 算法和游戏，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15863658/