如何在Python Pulp中正确表达双重求和约束？

你当前代码的核心问题是行/列和约束的逻辑错误——你现在是对每个数值k单独统计行内等于k的单元格数量，而数谜的要求是行内所有单元格的数值之和等于目标值，需要用数值k乘以对应的二进制变量X[i][j][k]后再求和。

修正思路 #

• 行约束：对每一行i，遍历所有列j和所有可能数值k，计算k * X[i][j][k]的总和，让这个总和等于该行的目标值M[i][0]
• 列约束：对每一列j，遍历所有行i和所有可能数值k，计算k * X[i][j][k]的总和，让这个总和等于该列的目标值M[0][j]

完整修正代码 #

import pulp
import numpy as np

def Kakuro(M):
    prob = pulp.LpProblem() 
    rows = range(1,4)
    cols = range(1,4)
    vals = range(1,10)

    X = pulp.LpVariable.dicts("X",(rows,cols,vals),cat='Binary')

    # 约束1：每个单元格恰好选择一个数值
    for i in rows:
        for j in cols:
            prob += sum([X[i][j][k] for k in vals]) == 1
            
    # 约束2：每行的数值之和等于该行的目标值M[i][0]
    for i in rows:
        prob += sum(k * X[i][j][k] for j in cols for k in vals) == M[i][0]

    # 约束3：每列的数值之和等于该列的目标值M[0][j]
    for j in cols:
        prob += sum(k * X[i][j][k] for i in rows for k in vals) == M[0][j]

    prob.solve() # 可添加msg=0关闭日志：prob.solve(pulp.PULP_CBC_CMD(msg=0))

    solution = np.zeros((4,4))
    # 填充目标和
    for i in rows:
      solution[i][0] = M[i][0]
    for j in cols:
      solution[0][j]=M[0][j]

    # 填充求解得到的数值
    for i in rows:
        for j in cols:
            for k in vals:
                if X[i][j][k].value() == 1:
                    solution[i,j] = k
    
    return solution

关键修改说明 #

• 去掉了原代码中对k的嵌套循环，直接在求和表达式中同时遍历列/行和数值k
• 用k * X[i][j][k]实现“选中数值k时，该单元格贡献k到总和”的逻辑，完全符合数谜的和约束要求

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