python - 试图用cvxpy解决数独

我正在尝试使用cvxpy优化包解决数独问题。
我对优化和cvxpy都是真正的新手。

约束是:

所有值都在1到9之间

所有行的总和= 45

所有列的总和= 45

所有正方形的总和= 45

给定的数字(我正在尝试解决17条线索数独)。

所以，这是我的代码:

from cvxpy import *
import numpy as np

x = Variable((9, 9), integer=True)
obj = Minimize(sum(x)) #whatever, if the constrains are fulfilled it will be fine
const = [x >= 1, #all values should be >= 1
         x <= 9, #all values should be <= 9
         sum(x, axis=0) == 45,  # sum of all rows should be 45
         sum(x, axis=1) == 45,  # sum of all cols should be 45
         sum(x[0:3, 0:3]) == 45, sum(x[0:3, 3:6]) == 45, #sum of all squares should be 45
         sum(x[0:3, 6:9]) == 45,
         sum(x[3:6, 0:3]) == 45, sum(x[3:6, 3:6]) == 45,
         sum(x[3:6, 6:9]) == 45,
         sum(x[6:9, 0:3]) == 45, sum(x[6:9, 3:6]) == 45,
         sum(x[6:9, 6:9]) == 45,
         x[0, 7] == 7, #the values themselves
         x[0, 8] == 1,
         x[1, 1] == 6,
         x[1, 4] == 3,
         x[2, 4] == 2,
         x[3, 0] == 7,
         x[3, 4] == 6,
         x[3, 6] == 3,
         x[4, 0] == 4,
         x[4, 6] == 2,
         x[5, 0] == 1,
         x[5, 3] == 4,
         x[6, 3] == 7,
         x[6, 5] == 5,
         x[6, 7] == 8,
         x[7, 1] == 2,
         x[8, 3] == 1]

prob = Problem(objective=obj, constraints=const)
prob.solve()

我从cvxpy得到的是

prob.status
Out[2]: 'infeasible_inaccurate'

这肯定是有效的数独，我检查了数百万次。

为什么我没有得到答案？

任何帮助，将不胜感激!

最佳答案

这是默认情况下使用的ECOS_BB问题。它不是一个可靠的整数编程求解器，建议不要使用它。

其他建议:请勿使用import *。最好使用import cvxpy as cp以避免与具有相同名称的其他函数混淆。另外，顺便说一句，这里不需要numpy。

以下脚本使用GUROBI返回可行的解决方案(如果您没有GUROBI许可证，也可以使用GLPK):

import cvxpy as cp

x = cp.Variable((9, 9), integer=True)

# whatever, if the constrains are fulfilled it will be fine
objective = cp.Minimize(cp.sum(x))
constraints = [x >= 1,  # all values should be >= 1
               x <= 9,  # all values should be <= 9
               cp.sum(x, axis=0) == 45,  # sum of all rows should be 45
               cp.sum(x, axis=1) == 45,  # sum of all cols should be 45
               # sum of all squares should be 45
               cp.sum(x[0:3, 0:3]) == 45, cp.sum(x[0:3, 3:6]) == 45,
               cp.sum(x[0:3, 6:9]) == 45,
               cp.sum(x[3:6, 0:3]) == 45, cp.sum(x[3:6, 3:6]) == 45,
               cp.sum(x[3:6, 6:9]) == 45,
               cp.sum(x[6:9, 0:3]) == 45, cp.sum(x[6:9, 3:6]) == 45,
               cp.sum(x[6:9, 6:9]) == 45,
               x[0, 7] == 7,  # the values themselves
               x[0, 8] == 1,
               x[1, 1] == 6,
               x[1, 4] == 3,
               x[2, 4] == 2,
               x[3, 0] == 7,
               x[3, 4] == 6,
               x[3, 6] == 3,
               x[4, 0] == 4,
               x[4, 6] == 2,
               x[5, 0] == 1,
               x[5, 3] == 4,
               x[6, 3] == 7,
               x[6, 5] == 5,
               x[6, 7] == 8,
               x[7, 1] == 2,
               x[8, 3] == 1]

prob = cp.Problem(objective, constraints)
prob.solve(solver=cp.GUROBI)

print(x.value)

那就是输出

In [2]: run sudoku.py
[[1. 6. 1. 4. 7. 9. 9. 7. 1.]
 [6. 6. 1. 1. 3. 9. 9. 9. 1.]
 [8. 7. 9. 1. 2. 9. 1. 7. 1.]
 [7. 7. 1. 9. 6. 1. 3. 2. 9.]
 [4. 9. 5. 9. 5. 1. 2. 1. 9.]
 [1. 2. 9. 4. 9. 1. 9. 1. 9.]
 [8. 1. 1. 7. 8. 5. 2. 8. 5.]
 [9. 2. 9. 9. 4. 1. 1. 1. 9.]
 [1. 5. 9. 1. 1. 9. 9. 9. 1.]]

关于python - 试图用cvxpy解决数独，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54679188/

CVXPY

python - 试图用cvxpy解决数独