纸浆杀手数独检查选择是不同的变量选择

Question

我正在尝试使用Python线性优化库纸浆来解决杀手级数独

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,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

我在网上看到了几个例子，通过将此优化重新定义为二进制标志的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

我希望（a）找到一种方法来添加这种更严格的约束，即在9x9设置中不能重复任何选择，或者（b）找到一种方法来轻松添加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) a way to easily add constraints of the 'sum' of cages in the 9x9x9 case.

这是非常简单的-您只需将一个单元格的二进制变量与每个变量表示的索引求和乘积即可

如果您已经开发了假设您选择变量（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)])

现在，您有两组变量-一组二进制变量和一组整数变量，它们通过等式约束链接，以按要求运行。如果要避免所有辅助变量，则只需在当前使用整数变量的任何位置使用上述索引值替换和积即可阿贝尔斯

完整性的完整工作代码：

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)