在不否定的情况下找到布尔值乘积和的所有解的算法

问：

我正在开发一个益智游戏，每个关卡都可以通过一系列动作来完成。有八个不同的动作标记为 a-h。我开发了一个求解函数，可以传递一个级别 L 和一组可用的移动 S，它将返回该级别是否可以仅使用 S 的移动来求解。

例如，如果我调用，那么函数可能会发现一系列移动解决了难题，因此它返回 .solve(L, {a,b})aaabbaabaTrue

我有兴趣编写一个算法来找到足以解决一个关卡的所有可用动作集。由于有八个不同的动作，因此有 2⁸ = 256 组可能的动作。我可以全部检查，但这似乎相当浪费。求解器相对较慢，因此目标是使用逻辑来减少我需要运行求解器的次数。

如果仅移动 c 就足以求解一个水平（即 ），那么该水平也可以用移动 c 和 d 来解决（其中移动 d 可用但不需要）。同样，如果一个关卡除了 c 之外的每一步都无法求解（即 ），那么除了 c 和 d 之外，该关卡也将在每一步都无法求解。solve(L, {c}) == Truesolve(L, {a,b,d,e,f,g,h}) == False

更一般地说：

• 如果和 S⊆T，则solve(L, S) == Truesolve(L, T) == True
• 如果和 T⊆S，则solve(L, S) == Falsesolve(L, T) == False

我相信这意味着该水平可以表示为不否定的产品总和。例如，一个级别可以表示为 。（在这种情况下，该级别可以用集合 {a}、{c，d，e}、{d，e，f} 以及这些集合的任何超集求解。a ∨ c∧d∧e ∨ d∧e∧f

我怀疑一个好的算法可能首先检查只包含一个动作的集合和那些只包含一个动作的集合，以便可以修剪大量的可能性。我试图提出一种递归算法，但我很难将这两种类型的修剪结合起来。