Pulp Killer sudoku - выбор вариантов проверки для выбора переменных

Question

Я пытаюсь решить убийцу судоку, используя Python библиотеку линейной оптимизации, Pulp.

https://en.wikipedia.org/wiki/Killer_sudoku

Вот моя попытка до сих пор, добавление ограничение, что каждая строка должна добавить до 45.

import pulp
prob = pulp.LpProblem("Sudoku Problem")
prob += 0, "Arbitrary Objective Function"

# 9 by 9 grid of 'choices', integers between 1-9
choices = pulp.LpVariable.dicts(
"Choice", (range(9), range(9)), cat="Integer", lowBound=1, upBound=9)

# identify puzzle rows that must have only 1 of every value 
row_groups = [[(i, j) for i in range(9)] for j in range(9)]

# Seems to work, make every row add up 45
for distinct_group in row_groups:
    for i, j in distinct_group:
        distinct_group_constraint = [choices[i][j] for i, j in distinct_group]
    prob += pulp.lpSum(distinct_group_constraint) == 45


# ... Code to add additional constraints for columns, boxes and 'cages'. Excluded for brevity.

prob.solve()

Проблема в том, что я пытаюсь добавить более строгое ограничение, что каждое значение в строке должно быть различным. Например, если строка имеет эти значения

[1,9,1,9,1,9,1,9,5]

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

Ниже приведена моя попытка добавить более строгое ограничение, оно, похоже, не работает, поскольку проблема не решается

for n in range(1, 10):
    for distinct_group in row_groups:
        for i, j in distinct_group:
            distinct_group_constraint = [choices[i][j] == n for i, j in distinct_group]
        prob += pulp.lpSum(distinct_group_constraint) == 1

I видел несколько примеров в Интернете, решая эту проблему, перефразируя эту оптимизацию как выбор двоичных флагов 9x9x9, а не оптимизацию выбора целых чисел 1-9 9x9. Проблема в том, что мне трудно понять, как легко проверить суммы «клеток» в случае 9x9x9, хотя в случае 9x9 это довольно просто.

Вот пример установки 9x9x9 для "не убийца" судоку. https://github.com/coin-or/pulp/blob/master/examples/Sudoku1.py

# cells (0,0) and (0,1) must sum to 8
cage_constraints = [(8, [[0, 0], [0, 1]])]

for target, cells in cage_constraints:
    cage_cells_constraint = [choices[i][j] for i, j in cells]
    prob += pulp.lpSum(cage_cells_constraint) == target

Я хочу (а) найти способ добавить это более строгое ограничение, чтобы ни один из вариантов не мог дублироваться в настройке 9x9, или (б) способ легко добавить ограничения на «сумму» клеток в случае 9x9x9. Если вы хотите, чтобы тестировался весь список ограничений клетки, вот список ограничений клетки из этой головоломки.

CAGE_CONSTRAINTS = [
(8, [[0, 0], [0, 1]]),
(9, [[0, 6], [0, 7]]),
(8, [[0, 2], [1, 2]]),
(12, [[0, 3], [0, 4], [1, 3]]),
(15, [[0, 5], [1, 5], [2, 5]]),
(19, [[1, 6], [1, 7], [2, 7]]),
(16, [[0, 8], [1, 8], [2, 8]]),
(14, [[1, 0], [1, 1], [2, 0]]),
(15, [[2, 1], [2, 2]]),
(10, [[2, 3], [3, 3]]),
(12, [[1, 4], [2, 4]]),
(7, [[2, 6], [3, 6]]),
(24, [[3, 0], [3, 1], [4, 1]]),
(17, [[3, 7], [3, 8], [4, 8]]),
(8, [[3, 2], [4, 2]]),
(12, [[4, 3], [5, 3]]),
(19, [[3, 4], [4, 4], [5, 4]]),
(4, [[3, 5], [4, 5]]),
(15, [[4, 6], [5, 6]]),
(12, [[4, 0], [5, 0], [5, 1]]),
(7, [[4, 7], [5, 7], [5, 8]]),
(8, [[5, 2], [6, 2]]),
(10, [[6, 4], [7, 4]]),
(14, [[5, 5], [6, 5]]),
(12, [[6, 6], [6, 7]]),
(18, [[6, 8], [7, 7], [7, 8]]),
(15, [[6, 0], [7, 0], [8, 0]]),
(13, [[6, 1], [7, 1], [7, 2]]),
(12, [[6, 3], [7, 3], [8, 3]]),
(15, [[7, 5], [8, 4], [8, 5]]),
(7, [[7, 6], [8, 6]]),
(10, [[8, 1], [8, 2]]),
(8, [[8, 7], [8, 8]]),
]

https://www.dailykillersudoku.com/search?dt=2020-02-15

и вот решение https://www.dailykillersudoku.com/pdfs/19664.solution.pdf

РЕДАКТИРОВАТЬ - если я пытаюсь перейти к задаче 9x9x9 с двоичным выбором, я получаю результаты, которые не соответствуют моим желаемым ограничениям клетки. Вот фрагмент кода.

choices = pulp.LpVariable.dicts(
    "Choice", (range(9), range(9), range(1, 10),), cat="Binary"
)

# add constraints that only one choice for each 'distinct_group'
for n in range(1, 10):
    for distinct_group in distinct_groups:
        for i, j in distinct_group:
        distinct_group_constraint = [choices[i][j][n] for i, j in 
distinct_group]
        prob += pulp.lpSum(distinct_group_constraint) == 1

# add constraints that cells in cages must equal 'cage_total'
for target, cells in CAGE_CONSTRAINTS:
    cage_cells_constraint = [
        choices[i][j][n] * n for i, j in cells for n in range(1, 10)
    ]
    prob += pulp.lpSum(cage_cells_constraint) == target

и вот полный пример https://gist.github.com/olicairns/d8e222526b87a62b2e175837b452c24a

Answer 1

Я бы рекомендовал использовать бинарные переменные - в соответствии с примерами, которые вы нашли. Это может показаться большим количеством переменных, но, насколько мне известно, использование меньшего числа целочисленных переменных совсем не поможет времени решения - то, как алгоритм «ветвления и ограничения» для решения проблемы с целочисленными переменными будет означать, что столь же неэффективно, как наличие большего количества двоичных переменных (кто-то, кто более знаком с этим, может исправить меня).

Итак, чтобы ответить на вторую половину вашего вопроса:

(b) способ легко добавить ограничения на «сумму» клеток в случае 9x9x9.

Это довольно просто - вы просто суммируете двоичные переменные для ячейки на индекс, который каждая переменная представляет.

Если вы уже разработали весь код, предполагающий выбор переменных (целочисленные переменные 9x9), вы можете добавить двоичные переменные 9x9x9, а затем ограничить целочисленные переменные 9x9 (которые теперь будут вспомогательные переменные) следующим образом:

for i in range(1, 10):
    for j in range(1, 10):
        pulp += choices[i][j] == pulp.lpSum([binary_choices[i][j][k]*k for k in range(1,10)])

Теперь у вас есть оба набора переменных - одна партия двоичных переменных ES, и одна серия целочисленных переменных, которые связаны с ограничениями равенства, чтобы вести себя как требуется. Если вы хотите избежать всех вспомогательных переменных, то вам просто нужно заменить сумму-произведение на значение индекса, как указано выше, везде, где вы в настоящее время используете целочисленные переменные.

Полный рабочий код для полноты:

import pulp

prob = pulp.LpProblem("Sudoku_Problem_KA")
prob += 0, "Arbitrary Objective Function"

CAGE_CONSTRAINTS = [
    (8., [[0, 0], [0, 1]]),
    (9., [[0, 6], [0, 7]]),
    (8., [[0, 2], [1, 2]]),
    (12., [[0, 3], [0, 4], [1, 3]]),
    (15., [[0, 5], [1, 5], [2, 5]]),
    (19., [[1, 6], [1, 7], [2, 7]]),
    (16., [[0, 8], [1, 8], [2, 8]]),
    (14., [[1, 0], [1, 1], [2, 0]]),
    (15., [[2, 1], [2, 2]]),
    (10., [[2, 3], [3, 3]]),
    (12., [[1, 4], [2, 4]]),
    (7., [[2, 6], [3, 6]]),
    (24., [[3, 0], [3, 1], [4, 1]]),
    (17., [[3, 7], [3, 8], [4, 8]]),
    (8., [[3, 2], [4, 2]]),
    (12., [[4, 3], [5, 3]]),
    (19., [[3, 4], [4, 4], [5, 4]]),
    (4., [[3, 5], [4, 5]]),
    (15., [[4, 6], [5, 6]]),
    (12., [[4, 0], [5, 0], [5, 1]]),
    (7., [[4, 7], [5, 7], [5, 8]]),
    (8., [[5, 2], [6, 2]]),
    (10., [[6, 4], [7, 4]]),
    (14., [[5, 5], [6, 5]]),
    (12., [[6, 6], [6, 7]]),
    (18., [[6, 8], [7, 7], [7, 8]]),
    (15., [[6, 0], [7, 0], [8, 0]]),
    (13., [[6, 1], [7, 1], [7, 2]]),
    (12., [[6, 3], [7, 3], [8, 3]]),
    (15., [[7, 5], [8, 4], [8, 5]]),
    (7., [[7, 6], [8, 6]]),
    (10., [[8, 1], [8, 2]]),
    (8., [[8, 7], [8, 8]]),
]

# groups that should only have 1 of each number 1-9
row_groups = [[(i, j) for i in range(9)] for j in range(9)]
col_groups = [[(j, i) for i in range(9)] for j in range(9)]
box_groups = [
    [(3 * i + k, 3 * j + l) for k in range(3) for l in range(3)]
    for i in range(3)
    for j in range(3)
]
distinct_groups = row_groups + col_groups + box_groups

# binary choices: rows, columns and values 1-9
choices = pulp.LpVariable.dicts(
    "choices", (range(9), range(9), range(1, 10)), cat="Binary"
)

# add constraints that only one choice for each 'distinct_group'
for n in range(1, 10):
    for distinct_group in distinct_groups:
        prob += pulp.lpSum([choices[i][j][n] for i, j in distinct_group]) <= 1

# add constraints that cells in cages must equal 'cage_total'
for target, cells in CAGE_CONSTRAINTS:
    prob += pulp.lpSum([choices[i][j][n] * n for i, j in cells for n in range(1, 10)]) >= target

# only pick one binary value per cell:
for i in range(9):
    for j in range(9):
        prob += pulp.lpSum([choices[i][j][n] for n in range(1, 10)]) <= 1

prob.solve()

print('Status:',pulp.LpStatus[prob.status])

# Extract results
res = [[sum([choices[i][j][n].varValue*n for n in range(1,10)]) for j in range(9)] for i in range(9)]

# checking a few constraints match
assert res[8][7] + res[8][8] == 8
assert res[0][0] + res[0][1] == 8

print(res)