无否定布尔Sum of Products全解算法：解谜游戏可解操作集合查找

问题本质 #

你要解决的是典型的单调布尔函数极小元求解问题：你的solve函数符合集合单调性：

• 若子集可行，则其所有超集必可行
• 若超集不可行，则其所有子集必不可行
  因此不需要遍历全部256种集合，只需要找到所有极小可行集合（即去掉任意一个元素就会变为不可行的可行集合），就可以推导所有集合的通关状态：极小可行集合的所有超集都是可通关集合，其余均不可通关。

整合两类剪枝的核心思路 #

我们只需要维护两个全局缓存集合，就能同时实现两类剪枝：

• known_good：已经验证可行的集合，其所有超集无需再调用solve即可判定为可行
• known_bad：已经验证不可行的集合，其所有子集无需再调用solve即可判定为不可行

每次要测试目标集合S前，先做两步预校验：

1. 遍历known_good，如果存在任意g ∈ known_good满足g ⊆ S，直接判定S可行
2. 遍历known_bad，如果存在任意b ∈ known_bad满足S ⊆ b，直接判定S不可行

测试完成后更新缓存：

• 若solve(L, S) == True：检查S是否为极小可行集合（即S没有任何真子集在known_good中），如果是则加入极小解集合，同时将S加入known_good
• 若solve(L, S) == False：直接将S加入known_bad

最优执行流程（最少调用次数） #

优先测试能带来最大剪枝收益的集合，总共仅需最多几十次solve调用即可完成全部计算：

第一步：前置快速剪枝（仅16次调用） #

1. 先遍历测试全部8个单元素集合：
   • 只要单元素集合{x}返回True，它就是极小可行解，所有包含x的集合后续都无需测试
2. 再遍历测试全部8个大小为7的集合（即仅缺一个元素的集合）：
   • 只要缺x的集合返回False，所有不包含x的集合后续都无需测试

第二步：按集合大小从小到大搜索剩余集合 #

剩余需要测试的集合，仅需满足：

• 不包含任何已经找到的单元素可行操作
• 包含所有缺集不可行对应的必填操作

按集合大小从小到大测试（小集合的可行结果能剪掉更多超集）：

• 先测试所有符合条件的大小为2的集合
• 再测试大小为3的，以此类推
• 当所有剩余未测试集合都可以通过known_good/known_bad推导结果时，直接终止搜索

优化建议：用位运算表示集合 #

由于只有8个操作，可以用0-255的整数代表集合，每一位对应一个操作的有无，子集判断可以用位运算高效实现：

• 集合A是集合B的子集等价于 (A & B) == A
• 集合的大小可以用内置函数直接计算：Python中为bin(x).count('1')，C/C++中为__builtin_popcount(x)

参考伪代码 #

# 操作映射：a对应第0位，b对应第1位，...，h对应第7位
op_to_bit = {'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6, 'h':7}
full_set = 0b11111111  # 全部8个操作的集合

known_good = set()
known_bad = set()
minimal_solutions = set()

def is_skip(s):
    # 检查是否可以通过缓存跳过测试
    for g in known_good:
        if (g & s) == g:
            return True, True
    for b in known_bad:
        if (s & b) == s:
            return True, False
    return False, None

# 第一步：测试单元素集合
for op in op_to_bit.values():
    s = 1 << op
    skip, res = is_skip(s)
    if skip:
        continue
    res = solve(L, s)
    if res:
        minimal_solutions.add(s)
        known_good.add(s)
    else:
        known_bad.add(s)

# 第二步：测试大小为7的集合
for op in op_to_bit.values():
    s = full_set ^ (1 << op)
    skip, res = is_skip(s)
    if skip:
        continue
    res = solve(L, s)
    if res:
        known_good.add(s)
    else:
        known_bad.add(s)

# 第三步：从小到大测试剩余集合
for size in range(2, 7):
    # 枚举所有大小为size的集合
    for s in range(full_set + 1):
        if bin(s).count('1') != size:
            continue
        skip, res = is_skip(s)
        if skip:
            continue
        res = solve(L, s)
        if res:
            # 检查是否是极小解
            is_minimal = True
            for g in known_good:
                if (g & s) == g and g != s:
                    is_minimal = False
                    break
            if is_minimal:
                minimal_solutions.add(s)
            known_good.add(s)
        else:
            known_bad.add(s)

内容的提问来源于stack exchange，提问作者dln385