我的4*4 Kakuro Puzzle代码的怪异表现

Question

我试图使用优化概念编写执行4*4 Kakuro谜题的代码。基本上，它要求每行和每列中的空单元格之和等于该行或列的第一个条目。例如，如果给定的谜题是

np.array([[ 0., 21., 20.,  10.],
[23.,  0.,  0.,  0.],
[ 19.,  0.,  0.,  0.],
[ 9.,  0.,  0.,  0.]]), 
then the output should be 
np.array([[ 0., 21., 20.,  10.],
[23.,  9.,  8.,  6.],
[ 19.,  7.,  9.,  3.],
[ 9.,  5.,  3.,  1.]]).

我的代码可以运行，但是输出看起来很奇怪，我根本找不到它的执行模式。这是我的代码。

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')
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([X[i][j][k] for j in cols for k in vals]) == M[i,0]
for j in cols:
prob += sum([X[i][j][k] for i in rows for k in vals]) == M[0,j]

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

上面例子的输出是

array([[ 0., 21., 20., 10.],
[23.,  2.,  6.,  3.],
[19.,  5.,  4.,  0.],
[ 9.,  0.,  0.,  0.]])

我不知道这些随意的数字是从哪里来的。任何帮助将非常感激!

---

如果你不明白我的约束，请随时问我。谢谢你！

Answer 1

请参阅下面的解决方案。我用过Google-ortool的CP-SAT求解器。

import numpy as np
from ortools.sat.python import cp_model as cp
input_data_matrix = np.array([[ 0, 21, 20,  10],
[23,  0,  0,  0],
[ 19,  0,  0,  0],
[ 9,  0,  0,  0]])
num_rows = len(input_data_matrix)
num_columns = [len(i) for i in input_data_matrix][0]
max_value_matrix = max([input_data_matrix[row][col] for row in range(num_rows) for col in range(num_columns)])
model = cp.CpModel()
dv_zero = {}
for row in range(num_rows):
for col in range(num_columns):
if col > 0 and input_data_matrix[row][col] == 0:
dv_zero[row, col] = model.NewIntVar(1, 9, str(row) + "_" + str(col))

for row in np.unique([k[0] for k in dv_zero]):
dvs = [v for k,v in dv_zero.items() if k[0] == row]
model.AddAllDifferent(dvs)
value = sum([input_data_matrix[row][col] for col in range(num_columns) if col not in [k[1] for k,v in dv_zero.items() if k[0] == row]])
model.Add(sum(dvs) == value)

for col in np.unique([k[1] for k in dv_zero]):
dvs = [v for k,v in dv_zero.items() if k[1] == col]
model.AddAllDifferent(dvs)
value = sum([input_data_matrix[row][col] for row in range(num_rows) if row not in [k[0] for k,v in dv_zero.items() if k[1] == col]])
model.Add(sum(dvs) == value)

solver = cp.CpSolver()
solver.Solve(model)

# inspect the solution :
for row in range(num_rows):
for col in range(num_columns):
if col > 0 and input_data_matrix[row][col] == 0:
print("row: " + str(row) + " ; col: " + str(col) + " = " + str(solver.Value(dv_zero[row, col])))
else:
print("row: " + str(row) + " ; col: " + str(col) + " = " + str(input_data_matrix[row][col]))