Pulp Killer 数独 - 检查选项对于变量的选择是不同的

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

我在网上看到了几个示例，通过将此优化重新定义为二进制标志的 9x9x9 选择而不是整数 1-9 选择的 9x9 优化来解决此问题。问题是，我发现很难看出如何在 9x9x9 的情况下轻松检查 'cages' 的总和，而这在 9x9 的情况下非常简单。

这里是 'non-killer' 数独的 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) 一种轻松添加 'sum' 笼子约束的方法在 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

我建议使用二进制变量 - 根据您找到的示例。它可能看起来像更多的变量，但据我所知，使用较少数量的整数变量根本不会帮助解决问题 - 'branch-and-bound' 算法解决整数变量问题的方式意味着它就像由于具有更多的二进制变量而效率低下（对此更熟悉的人可能会纠正我）。

所以回答你问题的后半部分：

(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)

Pulp Killer 数独 - 检查选项对于变量的选择是不同的

Pulp Killer sudoku - check choices are distinct for choice of variables

python

linear-programming

sudoku

pulp

constraint-satisfaction