A *算法和游戏

Question

我正试图在lisp中实施扫雷解决程序。我知道这不是罕见的问题，但我没有找到任何可以帮助我的文章。在开始时，我有一个雷区作为输入数字在未被覆盖的领域。算法应该在找到所有地雷后完成。因此，在每一步我都要检查我可以放入我的矿区列表中的哪些字段，并从我的未开采字段列表中选择一个字段并将其打开。稍后我会检查是否已完成开采字段的列表，如果是，则算法已完成。我将不胜感激任何帮助。我不要求提供源代码，但我需要好的想法。我没有遇到过这类问题。

---

我必须使用A *算法。而且我不需要打开所有未打开的区域......我需要找到所有开采区域的位置。当然，它必须是最简单的路径。当我找到所有采矿场的位置算法完成。所以，再一次，我需要找到所有打开字段数量最多的开采字段。当然，我需要一个启发式算法，这将有助于选择所有安全未拆封区域之一。 并且在每次开放之后需要确定安全未打开域的列表。所以我需要调用main函数，该函数将检查我是否找到所有挖掘的字段，如果没有，那么所有安全相邻的未打开的字段都需要添加到路径列表中。并且将选择具有最佳启发式的路径

Answer 1

您不需要A *算法;其目的是在图中找到最短路径（例如地图中两个地方之间的最短路径，或者解决难题的最小路径）。您可能会想要使用一种称为回溯的技术。

只要有未打开的字段，选择一个未打开的字段旁边的一个打开的字段，并暂时将其标记为一个地雷。然后，查看与前一个相邻的未打开的字段以及打开的字段，并将该标记标记为矿山，如果这不与相邻的数字相抵触 - 如果是，则将其标记为安全的。继续。最后，你会看到所有未开封的田地，包围当前的区域，并找到了一种可能的方式来标记田地安全或不安全。然而，这是基于几次猜测，所以现在你需要回到最后一个猜测的领域，然后做出相反的猜测，然后再次向前移动以获得另一个可能的标志组合。然后，更进一步，修改你的猜测，等等。这可以用递归非常整齐地实现。最终，你将会收集可能的旗帜组合。如果您可以在所有可能的标志组合中找到安全的字段，请打开该字段。否则，请选择尽可能多的标志组合中安全的字段。

Answer 2

我在大学第一年实施了扫雷解决方案，所以我可以给你一些提示。 （这不是使用A *算法）

1. 重要 - 并非所有位置都是可解的。

2. 对于先进困难（复杂=需要一些时间，考虑所有可能将100个地雷放置在30x30场中），整个矿场的回溯有点复杂。

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

例子：

1. 有一个单独的雷区地方，你的解决
2. 找到所有有一个解决的（数量/已知矿）细胞足够接近未解细胞（2小区的距离）
3. 对于每个这样的细胞，以中心细胞为5x5的邻域，找到每种可能性（回溯）并检查可能性是否有共同之处（矿/非矿），如果是，您可以检查地雷和揭露非地雷。
4. 重复，而你可以发现的东西。
5. 当你无法发现任何东西并且剩余地雷的数量足够小时，你可以尝试在整个领域进行回溯。

我希望我记得正确，我做了一些证明，为什么5x5的面积足以检查，但它已经快10年了。