改进我的扫雷艇求解算法

Question

我用Python实现了一个算法来解决游戏“扫雷者”。该程序的工作原理如下：

假设解算器单击一个名为“a”的正方形。为了举例说明，让这个数等于2。广场的邻接部分（同样作为例子）被命名为“b”和“c”。然后程序将这个正方形与表达式[2，{b'，'c'}]相关联，并从所有其他表达式中剥离“a”。在两种情况下，通过对这些表达式的成对简化，推导出哪些正方形是地雷，哪些不是地雷。在

• 如果一个表达式中的平方是另一个表达式的平方的子集：

  [2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}]
  

• 如果一个表达式中的所有正方形都是地雷：

  [2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}]
  

然后，对于某些表达式X，如果X[0] == 0，我们可以随意单击X[1]中命名的所有方块，如果X[0] == len(X[1])，那么我们可以标记它们。在

然而，我正在努力确定哪对表达式试图简化。我当前的方法是维护一个正方形的堆栈；每当单击一个正方形，或者成功地简化了它的表达式，它就会被添加到堆栈中（如果它还不存在的话）。当从堆栈中弹出一个正方形时，将尝试在其表达式（X）和任何其他表达式Y之间进行简化，以便X[1] & Y[1] != set()。当堆栈耗尽时，算法终止。然而，目前，虽然这工作得很好，但它不能正确地解决所有明确的配置，如果我用一个队列替换堆栈，或者使用某种算法来确定弹出哪个方块，那么它在给定板上的性能会发生很大变化！在

我将非常感谢任何先例，我的方法，或潜在的探索途径的先例。在

Answer 1

几年前我写了一个扫雷器解算器，但遗憾的是，从那以后我似乎就失去了代码。我记得的是，这是一种蛮力方法，它汇编了一组潜在的地雷，而不是像你现在这样把这些组合打包起来。在

我相信它比你现在使用的算法更有效。你的方法可以“解决”一个条件，如果它完全是满的或空的地雷，或者如果它是另一个条件的子集。然而，有一些扣除是不能处理的。例如，考虑这个7x2的小板，其中a到{}块是未知的：

a 2 1 2 1 2 i
b c d e f g h 

你的条件是：

^{pr2}$

如果我理解正确的话，你的算法就不能对这一点做任何推断。但是，如果你是一个经验丰富的扫雷玩家，你会发现中间的1 2 1模式只有一个解决方案，在1s下方有地雷：

a 2 1 2 1 2 i
b 2 * 2 * 2 h

还有一些未知数，在a或b下有一个地雷，h或{}下有一个地雷，但如果这是一个更大的谜题的一部分，你也许可以在以后找到这些谜题（或者你可能不得不猜测）。在

我相信我的“地雷”方法是这样工作的：

对于每一个扩展的瓦片，收集一组所有未展开的相邻区域（“区域”），以及一个包含该区域内可能出现的所有地雷集的列表。例如，上面示例中的5个已知分片将生成（从左到右）：

 ({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}])
 ({c, d, e}, [{c}, {d}, {e}])
 ({d, e, f}, [{d, e}, {d, f}, {e, f}])
 ({e, f, g}, [{e}, {f}, {g}])
 ({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}])

总之，要组合两个条件，我首先要检查它们是否重叠，方法是使面积集相交。如果没有重叠，就不能有效地组合这些条件。在

如果有一个重叠，新的条件将跨越他们区域的联合。至于地雷的集合，我会用外部集合的笛卡尔积得到成对的内部集合，然后检查是否存在矛盾。矛盾的是，如果在两个区域的交叉点内，两组的地雷并不完全相同。如果不存在矛盾，则由矿址联合形成新的组合集。下面是上面两行的组合方式：

 Intersection of areas: {a, b, c, d} & {c, d, e} = {c, d}
 New combined area: {a, b, c, d} | {c, d, e} = {a, b, c, d, e}
 Cartesian product of mine sets (with X marking contradictions):
    |   {a, b}  {a, c}  {a, d}  {b, c}  {b, d}  {c, d}
  -+                        -
 {c}|     X     {a, c}    X     {b, c}    X       X
 {d}|     X       X     {a, d}    X     {b, d}    X
 {e}| {a, b, e}   X       X       X       X       X

 New condition: ({a, b, c, d, e}, [{a, b, e}, {a, c}, {b, c}, {a, d}, {b, d}])

您可以通过简单地计算条件区域内的任何瓷砖是地雷的一部分（相对于总共有多少个集）来计算其成为地雷的几率。因此，考虑到上面的组合条件，您可以认为a是五分之三的时间是地雷，而{}只占时间的五分之一。当程序需要猜测要扩展的位置时，此信息非常重要，因为没有任何保证安全的磁贴。我想我也做了一些复杂的组合运算来解释使用的地雷的数量（这样，上面的{a，b，e}的情况与其他情况的权重会有点不同，因为它使用了三个地雷而不是两个地雷），但我恐怕记不清细节了。在

扫雷是一个相当有挑战性的游戏。我相信我的程序在50%到60%的时间内能够解决相当于“困难”问题的板，大多数损失要么发生在接近开始的时候（当你必须用很少的信息进行猜测时），要么就在最后（当经常有一些无法解决的领域需要猜测时）。它通常是相当快，虽然偶尔会有一个瓦片的模式，使它陷入10或15秒，然后再采取下一步行动。（Minesweeper is NP-complete，所以有些输入不能很快解决就不足为奇了！）在

Answer 2

这就是我突然想到的，我无法完全想象你的方法是什么。
我希望以图形的形式展示我的作品将有助于节省您的精力。在

图像按“阅读顺序”进行。在

这似乎与我在发布这篇文章后所做的工作相吻合，即在给定给一个未知磁贴的值的同时，它从中获得的已知磁贴数量可能会进一步增加正确建模风险的可能性。
（使用此方法，温度值为16（或第一种方法为8）是重要的，因为它是第一个矿井可以自行实现的）

---

我没有早点看到这件事，我觉得有点盲目。

在所有的情况下，任何一个值都能正常化为100%的东西都是我的。在