python - 给定一个数字列表，找到所有矩阵，使得每列和每行的总和为 264

Question

假设我有一个包含 16 个数字的列表。有了这 16 个数字，我可以创建不同的 4x4 矩阵。我想找到所有 4x4 矩阵，其中列表中的每个元素都使用一次，并且每行和每列的总和等于 264。

首先，我找到列表中元素的所有组合，总和为 264

numbers = [11, 16, 18, 19, 61, 66, 68, 69, 81, 86, 88, 89, 91, 96, 98, 99]

candidates = []
result = [x for x in itertools.combinations(numbers, 4) if sum(x) == 264]

result成为一个列表，其中每个元素都是一个包含 4 个元素的列表，其中 4 个元素的总和 = 264。我认为这些是我的行。然后我想对我的行进行所有排列，因为加法是可交换的。

for i in range(0, len(result)):
    candidates.append(list(itertools.permutations(result[i])))

现在给出总和为 264 的所有可能行。我想选择 4 行的所有组合，这样每列的总和为 264。

test = []
for i in range(0, len(candidates)):
    test = test + candidates[i]
result2 = [x for x in itertools.combinations(test, 4) if list(map(add, x[0], list(map(add, x[1], list( map(add, x[2], x[3])))))) == [264, 264, 264, 264]]

有没有更快/更好的方法？最后一部分，查找 4 行的所有组合，需要大量时间和计算机能力。

Answer 1

这是一种constraint satisfaction problem ;有 16 个变量，每个变量都具有相同的域，八个关于它们和的约束，以及一个约束，它们都应该具有与域不同的值。

可能有大量的解决方案，因此任何生成更大的候选集然后检查哪些候选真正是解决方案的算法在很大程度上可能是低效的，因为真正的解决方案可能是您的候选解决方案的一小部分. backtracking search通常更好，因为它允许部分候选者在违反任何约束时被拒绝，可能会消除许多完整的候选者而不必首先生成它们。

您可以使用现有的约束求解器，例如 python-constraint library，而不是编写自己的回溯搜索算法。 .下面是一个例子:

numbers = [11, 16, 18, 19, 61, 66, 68, 69, 81, 86, 88, 89, 91, 96, 98, 99]
target = 264

from constraint import *

problem = Problem()
problem.addVariables(range(16), numbers)

for i in range(4):
    # column i
    v = [ i + 4*j for j in range(4) ]
    problem.addConstraint(ExactSumConstraint(target), v)
    # row i
    v = [ 4*i + j for j in range(4) ]
    problem.addConstraint(ExactSumConstraint(target), v)

problem.addConstraint(AllDifferentConstraint())

例子:

>>> problem.getSolution()
{0: 99, 1: 88, 2: 66, 3: 11, 4: 16, 5: 61, 6: 89, 7: 98, 8: 81, 9: 96, 10: 18, 11: 69, 12: 68, 13: 19, 14: 91, 15: 86}
>>> import itertools
>>> for s in itertools.islice(problem.getSolutionIter(), 10):
...     print(s)
... 
{0: 99, 1: 68, 2: 81, 3: 16, 4: 66, 5: 91, 6: 18, 7: 89, 8: 88, 9: 19, 10: 96, 11: 61, 12: 11, 13: 86, 14: 69, 15: 98}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 66, 5: 91, 6: 18, 7: 89, 8: 11, 9: 86, 10: 69, 11: 98, 12: 88, 13: 19, 14: 96, 15: 61}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 18, 5: 89, 6: 66, 7: 91, 8: 86, 9: 11, 10: 98, 11: 69, 12: 61, 13: 96, 14: 19, 15: 88}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 18, 5: 89, 6: 66, 7: 91, 8: 61, 9: 96, 10: 19, 11: 88, 12: 86, 13: 11, 14: 98, 15: 69}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 11, 5: 86, 6: 69, 7: 98, 8: 66, 9: 91, 10: 18, 11: 89, 12: 88, 13: 19, 14: 96, 15: 61}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 11, 5: 86, 6: 69, 7: 98, 8: 88, 9: 19, 10: 96, 11: 61, 12: 66, 13: 91, 14: 18, 15: 89}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 61, 5: 96, 6: 19, 7: 88, 8: 18, 9: 89, 10: 66, 11: 91, 12: 86, 13: 11, 14: 98, 15: 69}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 61, 5: 96, 6: 19, 7: 88, 8: 86, 9: 11, 10: 98, 11: 69, 12: 18, 13: 89, 14: 66, 15: 91}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 88, 5: 19, 6: 96, 7: 61, 8: 11, 9: 86, 10: 69, 11: 98, 12: 66, 13: 91, 14: 18, 15: 89}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 88, 5: 19, 6: 96, 7: 61, 8: 66, 9: 91, 10: 18, 11: 89, 12: 11, 13: 86, 14: 69, 15: 98}

这是前十个解决方案。 problem.getSolutions()方法返回一个包含所有这些的列表，但这需要相当多的时间来运行(在我的机器上大约需要 2 分钟)，因为要找到 6,912 个。

一个问题是每个解决方案都有许多对称的解决方案；您可以排列行，排列列，并进行转置。可以通过添加更多约束来消除对称性，这样您就可以从每个对称类中获得一个解决方案。这使得搜索更可行:

# permute rows/cols so that lowest element is in top-left corner
m = min(numbers)
problem.addConstraint(InSetConstraint([m]), [0])

from operator import lt as less_than

for i in range(3):
    # permute columns so first row is in order
    problem.addConstraint(less_than, [i, i+1])
    # permute rows so first column is in order
    problem.addConstraint(less_than, [4*i, 4*i + 4])

# break transpose symmetry by requiring grid[0,1] < grid[1,0]
problem.addConstraint(less_than, [1, 4])

这打破了所有的对称性，所以现在它在大约 0.2 秒内返回 6,912/(4! * 4! * 2) = 6 个解。