4×4 Kakuro谜题求解代码输出异常，请求问题排查帮助

核心错误：求和约束逻辑完全错误 #

你的行、列求和约束写法逻辑颠倒了：当前代码中sum([X[i][j][k] for j in cols for k in vals])是统计二进制变量的数量，而每个格子恰好对应1个变量被选中，所以每行的这个和固定为3（3个空白格子），但你却要求它等于行首的目标和（比如23），这直接导致逻辑矛盾，求解器无法找到合法解，只能返回不符合预期的异常结果。

正确的逻辑是：每个格子的取值等于k * X[i][j][k]（X[i][j][k]为1时表示该格子取数值k），行/列求和需要把每个格子的实际取值相加，等于对应的目标和。

修正后的行约束：

for i in rows:
    prob += sum([k * X[i][j][k] for j in cols for k in vals]) == M[i, 0]

修正后的列约束：

for j in cols:
    prob += sum([k * X[i][j][k] for i in rows for k in vals]) == M[0, j]

补充Kakuro必备约束：同一行/列数字不重复 #

Kakuro规则要求同一行或同一列的空白格子数值不能重复，你的原始代码缺少该约束，即使修正求和逻辑，也可能出现重复数字的无效解。需要添加以下约束：

行内数字不重复 #

for i in rows:
    for k in vals:
        prob += sum([X[i][j][k] for j in cols]) <= 1

列内数字不重复 #

for j in cols:
    for k in vals:
        prob += sum([X[i][j][k] for i in rows]) <= 1

完整修正代码 #

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个1-9的数字
    for i in rows:
        for j in cols:
            prob += sum([X[i][j][k] for k in vals]) == 1
            
    # 每行数字和匹配行首目标值
    for i in rows:
        prob += sum([k * X[i][j][k] for j in cols for k in vals]) == M[i, 0]

    # 每列数字和匹配列首目标值
    for j in cols:
        prob += sum([k * X[i][j][k] for i in rows for k in vals]) == M[0, j]

    # 行内数字不重复
    for i in rows:
        for k in vals:
            prob += sum([X[i][j][k] for j in cols]) <= 1

    # 列内数字不重复
    for j in cols:
        for k in vals:
            prob += sum([X[i][j][k] for i in rows]) <= 1

    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 pulp.value(X[i][j][k]) == 1:
                    solution[i, j] = k
    
    return solution

测试验证 #

使用你提供的输入测试：

input_M = np.array([[ 0., 21., 20.,  10.],
                    [23.,  0.,  0.,  0.],
                    [ 19.,  0.,  0.,  0.],
                    [ 9.,  0.,  0.,  0.]])
print(Kakuro(input_M))

输出将与预期一致：

array([[ 0., 21., 20., 10.],
       [23.,  9.,  8.,  6.],
       [19.,  7.,  9.,  3.],
       [ 9.,  5.,  3.,  1.]])

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