我用Python实现了一个求解扫雷游戏的算法。程序的工作方式如下:
假设求解器点击了一个名为“a”的方格。例如,所揭示数字为2。该方格周围未点击的邻居方格(同样以示例说明)命名为“b”和“c”。然后程序将该方格与表达式[2,{'b','c'}]相关联,并从所有其他表达式中删除“a”。通过两种情况下的这种表达式成对简化来推断哪些方格是地雷,哪些不是地雷。
但是,我在努力确定要尝试简化哪些表达式。我的当前方法是维护一个方块堆栈;每当单击一个方块或其表达式成功简化时,将其添加到堆栈中(如果它还没有在那里)。从堆栈中弹出方块时,会尝试简化其表达式(
非常感谢您提供任何类似于我的方法的先例或潜在探索途径。
假设求解器点击了一个名为“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()
。算法在堆栈耗尽时终止。然而,目前虽然这种方法运行良好,但无法正确解决所有明确的配置,而且如果我用队列替换堆栈,或使用某种算法确定弹出哪个方块,则其在给定棋盘上的性能变化显著!非常感谢您提供任何类似于我的方法的先例或潜在探索途径。