Попытка решить судоку с помощью cvxpy

Question

Я пытаюсь решить судоку с помощью cvxpy пакета оптимизации.Я действительно плохо знаком с оптимизацией и cvxpy.

Ограничения:

1. все значения находятся в диапазоне от 1 до 9
2. сумма всех строк = 45
3. сумма всех столбцов =45
4. сумма всех квадратов = 45
5. заданных чисел (я пытаюсь разгадать судоку с 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'

Это, безусловно, действующий судоку, и япроверил цифры миллион раз.

Почему я не получаю ответ?

Буду признателен за любую помощь!

Answer 1

Это проблема ECOS_BB, которую вы используете по умолчанию.Это не надежный решатель целочисленного программирования, и я предлагаю не использовать его.

Другие рекомендации: не используйте import *.Гораздо лучше использовать import cvxpy as cp, чтобы избежать путаницы с другими функциями с таким же именем.Кроме того, numpy здесь, кстати, не нужен.

Следующий скрипт возвращает выполнимое решение с GUROBI (вы также можете использовать GLPK, если у вас нет лицензии GUROBI):

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.]]

Answer 2

Sum == 45 не является хорошим ограничением, поскольку оно не предотвращает дублирование значений.Вам не нужно ни numpy, ни cvxpy, чтобы решить эту проблему, поскольку простой алгоритм возврата может решить эту проблему.

count=0

def findnext():
    global x
    for row in range(0,9):
        for col in range(0, 9):
            if x[row][col] == 0:
                return (row, col)
    return (-1,-1)

def colok(row, col):
    global x
    for c in range(0,9):
        if c != col and x[row][c] == x[row][col]:
            # print "x[%d][%d] == x[%d][%d]" % (row,c,row,col)
            return False
    return True

def rowok(row, col):
    global x
    for r in range(0,9):
        if r != row and x[r][col] == x[row][col]:
            return False
    return True

def sqok(row, col):
    global x
    sqy = int(row/3)*3
    sqx = int(col/3)*3
    for r in range(0,3):
        for c in range(0, 3):
            if (sqx+c != col or sqy+r != row) and x[sqy+r][sqx+c] == x[row][col]:
                print "x[%d][%d] == x[%d][%d] = %d" % (row,c,row,col,x[row][col])
                return False

    return True

def backtrack():
    global x
    global count
    (row, col) = findnext()
    if row < 0:
        return True
    for v in range(1,10):
        x[row][col] = v
        if rowok(row, col) and colok(row,col) and sqok(row,col):
            count += 1
            if backtrack():
                return True
    x[row][col] = 0
    return False

Результат:

ending after calling backtrack 98248 times
2 8 3 6 5 4 9 7 1  
5 6 1 9 3 7 4 2 8  
9 7 4 8 2 1 5 6 3  
7 5 8 2 6 9 3 1 4  
4 3 6 5 1 8 2 9 7  
1 9 2 4 7 3 8 5 6  
3 1 9 7 4 5 6 8 2  
8 2 7 3 9 6 1 4 5  
6 4 5 1 8 2 7 3 9  

Answer 3

Документация (http://cvxr.com/cvx/doc/solver.html) предполагает, что основной причиной может быть практически осуществимое решение, которое выглядит недостижимым из-за погрешности с плавающей запятой выше допуска, которая возводится в квадрат со всеми ограничениями равенства.

Шагназад, однако, этого набора ограничений недостаточно, чтобы указать правильное решение Судоку. Лучшей формулировкой было бы иметь индексированные переменные 0-1 (строка, столбец, большой квадрат, цифра) и ограничения, которые для каждой строки /столбец / квадрат, строка / цифра, столбец / цифра, комбинация квадрат / цифра, сумма совпадающих переменных равна 1.