0

我正在尝试使用 Python 中的约束编程来做一个自定义幻方求解器。为此，我使用 python-constraint ( http://labix.org/python-constraint )。

对于这个问题，幻方的定义将是：“幻方是整数（正数或负数）在 nxn 矩阵中的排列，并且使得任何行、任何列或任何主对角线的条目之和是一样的。”

我有一个这样的预填充幻方：

+----+----+----+----+
| 7  |    |    |  4 |
+----+----+----+----+
|    |    |    |    |
+----+----+----+----+
| 0  | -3 | -2 |  3 |
+----+----+----+----+
| -5 |  6 |    |    |
+----+----+----+----+

这是我使用的代码：

from constraint import *

problem = Problem()
problem.addVariables(range(0, 16), range(-20, 20))

problem.addConstraint(lambda a: a==7, [0])
problem.addConstraint(lambda a: a==4, [3])
problem.addConstraint(lambda a: a==0, [8])
problem.addConstraint(lambda a: a==-3, [9])
problem.addConstraint(lambda a: a==-2, [10])
problem.addConstraint(lambda a: a==3, [11])
problem.addConstraint(lambda a: a==-5, [12])
problem.addConstraint(lambda a: a==6, [13])

problem.addConstraint(ExactSumConstraint(-2), [0,5,10,15])
problem.addConstraint(ExactSumConstraint(-2), [3,6,9,12])
for row in range(4):
    problem.addConstraint(ExactSumConstraint(-2),
                          [row*4+i for i in range(4)])
for col in range(4):
    problem.addConstraint(ExactSumConstraint(-2),
                          [col+4*i for i in range(4)])
solutions = problem.getSolution()
print solutions

我找不到任何解决方案，但我认为我的限制是正确的。每行和每列以及两条对角线的总和必须等于-2（基于我们在幻方上的行）。

你有什么想法 ？谢谢。

4

1 回答 1

1

好的，让我们做一些数学（和 python）来解开你的谜团。

第一行的行约束告诉你，pos 处的值。4 是-4。非对角线的约束告诉你，pos 处的值。6 是 2。

因此我们已经使用了值 [-5, -4, -3, -2, 0, 2, 3, 4, 6, 7]。这些值的总和为 8。

因此，我们必须在没有已经选择的值的情况下选择超出范围（-20、20）的六个值。

在具有 4 乘以 4 个条目的幻方中，行/列/对角线总和必须是

1 / 4 * 总和（所有条目）

有了这个，我们可以准备一个蛮力解决方案。


from itertools import combinations
choosen = [-5, -4, -3, -2, 0, 2, 3, 4, 6, 7]  # len(choosen) == 10
s_choosen = sum(choosen)
free_values = [x for x in range(-20, 20) if x not in choosen]
to_test = []
# we have to choose 6 values out of free_values
for comb in combinations(free_values, 6):
  if (1 / 4. * (sum(comb) + s_choosen)) == -2:  # could form correct row/col/diag sum
    to_test.append(comb)

这段代码为我们提供了 7254 个可能的 6 元组来填充正方形中的空闲位置。它们都不会产生幻方。

如果您明确不想应用 AllDifferentConstraint() 那么您必须执行以下操作以通过暴力破解来验证 python-constraint 的解决方案。

您仍然必须选择 6 个值；但这一次超出了整个范围（-20、20）并进行了替换。

from itertools import combinations_with_replacement
to_test2 = []
for comb in combinations_with_replacement(range(-20, 20), 6):
     if (1 / 4. * (sum(comb) + s_choosen)) == -2:  # could form correct row/col/diag sum
            to_test2.append(comb)
len (to_test2)


97063

该函数combinations_with_replacements仅返回已排序的组合。现在我们必须添加满足行和约束的所有排列。

已设置的值（7 和 4）的总和为 11。因此 6 元组中的前两个条目的总和 == -13。对于第二行，推导的条目（-4 和 2）的总和为 -2。因此，该行的剩余条目必须加起来为 0。在最后一行中，已设置条目的总和为 1。因此，最后两个条目的总和必须为 -3：

from itertools import permutations
sum_rows = []
for comb in to_test2:
    for entry in permutations(comb):
        if entry[0] + entry[1] == -13 and entry[2] + entry[3] == 0 and entry[4] + entry[5] == -3:
            sum_rows.append(entry)
len(sum_rows)




56672

现在我们必须检查列总和。第二列有（-3 和 6）总和 3。所以条目 0 和 2 的总和必须为 -5。第三列的 (2 和 -2) 总和为 0。因此条目 1 和 4 的总和必须为 -2。第四列的（4 和 3）总和为 7。因此条目 3 和 5 的总和必须为 -9。

col_sums = []
for entry in sum_rows:
    if entry[0] + entry[2] == -5 and entry[1] + entry[4] == -2 and entry[3] + entry[5] == -9:
        col_sums.append(entry)
len(col_sums)




32

最后，我们必须检查对角线的总和。对角线（7 和 -2）之和为 5。因此条目 2 和 5 之和必须为 -7。

diag_sums = []
for entry in col_sums:
    if entry[2]+ entry[5] == -7:
        diag_sums.append(entry)
len(diag_sums)




1




print diag_sums

[(-6, -7, 1, -1, 5, -8)]
于 2015-03-24T17:39:53.423 回答