3

我正在尝试使用 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 的情况下很难看出如何轻松检查“笼子”的总和，而这在 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

4

1 回答 1

2

我建议使用二进制变量 - 根据您找到的示例。它可能看起来像更多变量，但据我所知，使用较少数量的整数变量根本无助于解决时间 - 用于解决整数变量问题的“分支定界”算法将意味着它就像拥有更多的二进制变量一样低效（对此更熟悉的人可能会纠正我）。

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

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

您现在拥有两组变量 - 一组二进制变量和一组整数变量，它们与等式约束链接以按要求运行。如果您想避免所有辅助变量，那么您只需要在当前使用整数变量的任何地方将 sum-product 替换为上述索引值即可。

完整的完整工作代码：

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)
于 2020-02-16T13:13:36.107 回答