graph - A* 算法和游戏

Question

我正在尝试在 lisp 中实现扫雷求解器。我知道这不是罕见的问题，但我没有找到任何可以帮助我解决的文章。一开始我有一个雷区作为输入，在未覆盖的字段上有数字。当找到所有地雷时，算法应该完成。因此，在每一步中，我都必须检查哪些字段可以放入我的已开采字段列表中，并从我的未开采字段列表中选择一个字段并将其打开。稍后我将检查我的已挖掘字段列表是否已完成，如果是，则算法已完成。我将不胜感激任何帮助。我不要求源代码，但我需要好主意。我对这类问题没有经验。

我必须使用 A* 算法。而且我不需要打开所有未打开的字段......我需要找到所有已开采字段的位置。当然，它必须是做到这一点的最短路径。当我找到所有已挖掘字段的位置时，算法就完成了。所以，再一次，我需要找到具有最佳打开字段数的所有开采字段。当然，我的算法需要一种启发式方法，这将有助于选择所有安全的未打开字段之一。
每次打开后都需要确定未打开的安全字段列表。所以我需要调用 main 函数，该函数将检查我是否找到了所有挖掘的字段，如果没有，则需要将所有安全的相邻未打开字段添加到路径列表中。将选择具有最佳启发式的路径

Answer 1

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

重要 - 并非所有职位都可以解决。

对于高级难度，回溯整个雷区有点复杂(复杂 = 需要一些时间，考虑在 30x30 的区域中放置 100 个地雷的所有可能性)。

您可以在本地解决所有问题，就像人类解决扫雷艇一样。这样做的潜力是向用户提示如何继续而不是解决所有问题。

示例:

有一个单独的雷区，您可以在其中进行求解

找到所有具有已解决(数量/已知我的)单元格足够近(2 个单元格距离)的未解决单元格

对于每个这样的单元格，取一个以单元格为中心的 5x5 邻域，找到所有可能性(回溯)并检查可能性是否有共同点(地雷/非地雷)，如果是，您可以检查地雷并发现非地雷。

当你可以发现一些东西时重复。

当你找不到任何东西并且剩余地雷数量足够少时，你可以尝试在整个领域回溯。

我希望我没记错，我做了一些证明为什么 5x5 区域足以检查但几乎是 10 年前。