Python实现带L/D/S约束的0-1方程组求解方案求助

问题背景 #

我有如下形式的0-1方程组：

"L3 + L4 + S5 + S12 + L1 + D4 + L8 + S3 + L7 + D8 + D5 + L5 == 1",
"L4 + D9 + S5 + L1 + D16 + L8 + L6 + S8 + L7 + D8 == 1",
"L4 + L1 + D16 + S60 + L2 == 1",
"L3 + D12 + L1 + S9 + S3 + D5 + S105 + L2 + L7 + D28 + L5 == 1",
"S11 + L3 + S72 + D10 + D72 + D9 + S5 + D16 + S9 + S60 + L6 + S105 + L2 + L8 + D5 == 1",
"L3 + S60 + L2 + L4 == 1",
"D72 + L6 + S105 + L7 + D28 + L5 == 1",
"S72 + D72 + L8 + L6 + L5 == 1",
"D4 + S12 + S11 + D10 == 1",
"D12 + D10 + S9 + S8 + D8 + S12 == 1",
"S11 + D12 + S72 + D9 + D4 + S3 + S8 + D28 == 1",
"S11 + D12 + D10 + D72 + D9 + D28 + S72 + S5 + S12 + D4 + D16 + S9 + S3 + S60 + S8 + S105 + D8 + D5 == 1"

需求是找到所有变量取值为0或1的解，且每个解需恰好包含一个L类变量、一个D类变量、一个S类变量（示例：S1 = [L3,D12, S9]、S2 = [L4, D72, S8]）。

我尝试过将方程组建模为矩阵形式 M_L*L + M_D*D + M_S*S = Ones，但不知道如何编码实现。循环遍历所有可能的组合难度太大，也用SymPy写了代码，但无法得到符合约束的解组合，需要帮助。

现有SymPy尝试代码 #

from sympy import symbols, Eq, solve

L1, L2, L3, L4, L5, L6, L7, L8, S3, S5, S8, S9, S11, S12, S60, S72, S105, D4, D5, D8, D9, D10, D12, D16, D28, D72 = symbols('L1 L2 L3 L4 L5 L6 L7 L8 S3 S5 S8 S9 S11 S12 S60 S72 S105 D4 D5 D8 D9 D10 D12 D16 D28 D72', boolean=True)


eq1 = Eq(L3 + L4 + S5 + S12 + L1 + D4 + L8 + S3 + L7 + D8 + D5 + L5, 1)
eq2 = Eq(L4 + D9 + S5 + L1 + D16 + L8 + L6 + S8 + L7 + D8, 1)
eq3 = Eq(L4 + L1 + D16 + S60 + L2, 1)
eq4 = Eq(L3 + D12 + L1 + S9 + S3 + D5 + S105 + L2 + L7 + D28 + L5, 1)
eq5 = Eq(S11 + L3 + S72 + D10 + D72 + D9 + S5 + D16 + S9 + S60 + L6 + S105 + L2 + L8 + D5, 1)
eq6 = Eq(L3 + S60 + L2 + L4, 1)
eq7 = Eq(D72 + L6 + S105 + L7 + D28 + L5, 1)
eq8 = Eq(S72 + D72 + L8 + L6 + L5, 1)
eq9 = Eq(D4 + S12 + S11 + D10, 1)
eq10 = Eq(D12 + D10 + S9 + S8 + D8 + S12, 1)
eq11 = Eq(S11 + D12 + S72 + D9 + D4 + S3 + S8 + D28, 1)
eq12 = Eq(S11 + D12 + D10 + D72 + D9 + D28 + S72 + S5 + S12 + D4 + D16 + S9 + S3 + S60 + S8 + S105 + D8 + D5, 1)

solution = solve((eq1, eq2, eq3, eq4, eq5, eq6, eq7, eq8, eq9, eq10, eq11, eq12))

print(solution)

解决方案思路 #

1. 核心优化：利用额外约束缩小解空间 #

原方程组是0-1线性方程组，但额外要求每个解必须满足恰好一个L、一个D、一个S变量为1，其余为0。这个约束可以将原本2^26≈6700万种的组合，缩小到899=648种三元组组合，计算量大幅降低。

2. 实现步骤 #

• 分类变量：将所有变量按L、D、S分组，方便枚举三元组
• 构建方程检查函数：把每个方程转换为可验证的逻辑，输入变量取值字典即可判断是否满足
• 枚举验证：遍历所有(L,D,S)三元组，生成对应的变量取值，检查是否满足所有方程

3. 完整代码实现 #

# 定义所有方程的检查函数，输入变量字典，返回是否满足所有方程
def check_all_equations(var_dict):
    eq1 = var_dict['L3'] + var_dict['L4'] + var_dict['S5'] + var_dict['S12'] + var_dict['L1'] + var_dict['D4'] + var_dict['L8'] + var_dict['S3'] + var_dict['L7'] + var_dict['D8'] + var_dict['D5'] + var_dict['L5'] == 1
    eq2 = var_dict['L4'] + var_dict['D9'] + var_dict['S5'] + var_dict['L1'] + var_dict['D16'] + var_dict['L8'] + var_dict['L6'] + var_dict['S8'] + var_dict['L7'] + var_dict['D8'] == 1
    eq3 = var_dict['L4'] + var_dict['L1'] + var_dict['D16'] + var_dict['S60'] + var_dict['L2'] == 1
    eq4 = var_dict['L3'] + var_dict['D12'] + var_dict['L1'] + var_dict['S9'] + var_dict['S3'] + var_dict['D5'] + var_dict['S105'] + var_dict['L2'] + var_dict['L7'] + var_dict['D28'] + var_dict['L5'] == 1
    eq5 = var_dict['S11'] + var_dict['L3'] + var_dict['S72'] + var_dict['D10'] + var_dict['D72'] + var_dict['D9'] + var_dict['S5'] + var_dict['D16'] + var_dict['S9'] + var_dict['S60'] + var_dict['L6'] + var_dict['S105'] + var_dict['L2'] + var_dict['L8'] + var_dict['D5'] == 1
    eq6 = var_dict['L3'] + var_dict['S60'] + var_dict['L2'] + var_dict['L4'] == 1
    eq7 = var_dict['D72'] + var_dict['L6'] + var_dict['S105'] + var_dict['L7'] + var_dict['D28'] + var_dict['L5'] == 1
    eq8 = var_dict['S72'] + var_dict['D72'] + var_dict['L8'] + var_dict['L6'] + var_dict['L5'] == 1
    eq9 = var_dict['D4'] + var_dict['S12'] + var_dict['S11'] + var_dict['D10'] == 1
    eq10 = var_dict['D12'] + var_dict['D10'] + var_dict['S9'] + var_dict['S8'] + var_dict['D8'] + var_dict['S12'] == 1
    eq11 = var_dict['S11'] + var_dict['D12'] + var_dict['S72'] + var_dict['D9'] + var_dict['D4'] + var_dict['S3'] + var_dict['S8'] + var_dict['D28'] == 1
    eq12 = var_dict['S11'] + var_dict['D12'] + var_dict['D10'] + var_dict['D72'] + var_dict['D9'] + var_dict['D28'] + var_dict['S72'] + var_dict['S5'] + var_dict['S12'] + var_dict['D4'] + var_dict['D16'] + var_dict['S9'] + var_dict['S3'] + var_dict['S60'] + var_dict['S8'] + var_dict['S105'] + var_dict['D8'] + var_dict['D5'] == 1
    
    return eq1 and eq2 and eq3 and eq4 and eq5 and eq6 and eq7 and eq8 and eq9 and eq10 and eq11 and eq12

# 分类变量
L_vars = ['L1', 'L2', 'L3', 'L4', 'L5', 'L6', 'L7', 'L8']
D_vars = ['D4', 'D5', 'D8', 'D9', 'D10', 'D12', 'D16', 'D28', 'D72']
S_vars = ['S3', 'S5', 'S8', 'S9', 'S11', 'S12', 'S60', 'S72', 'S105']

# 生成所有变量列表
all_vars = L_vars + D_vars + S_vars

# 枚举所有可能的三元组并验证
valid_solutions = []
for l in L_vars:
    for d in D_vars:
        for s in S_vars:
            # 初始化变量字典，全部为0
            var_dict = {var: 0 for var in all_vars}
            # 设置选中的变量为1
            var_dict[l] = 1
            var_dict[d] = 1
            var_dict[s] = 1
            # 检查是否满足所有方程
            if check_all_equations(var_dict):
                valid_solutions.append([l, d, s])

# 输出结果
print("符合条件的解：")
for idx, sol in enumerate(valid_solutions, 1):
    print(f"S{idx} = {sol}")

4. 代码说明 #

• 该方法通过额外约束将计算量从指数级降到线性级，运行效率极高
• 方程检查逻辑直观，和原方程组一一对应，便于核对和修改
• 最终输出的结果直接是满足要求的(L,D,S)三元组，符合需求格式

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