使用约束编程的幻方解算器

Question

我试着用一个魔方编程。为此，我使用python约束（http://labix.org/python-constraint）。在

对于这个问题，幻方的定义是：“幻方是nxn矩阵中整数（正或负）的排列，使得任何行、任何列或任何主对角线的项之和都是相同的。”

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

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

下面是我使用的代码：

^{pr2}$

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

你有什么想法吗？谢谢。在

Answer 1

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

第一行的行约束告诉您，位置4的值是-4。 非对角线的约束告诉您，位置6处的值为2。在

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

因此，我们必须选择6个超出范围的值（-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元组来填充正方形中的空闲位置。没有一个结果是一个魔方。在

如果您明确不想应用alldifferenceconstraint（），那么您必须执行以下操作，通过强制执行python约束来验证它的解决方案。在

您仍然需要选择6个值；但这次超出了替换的整个范围（-20，20）。在

^{pr2}$

函数combinations_with_replacements只返回经过排序的组合。现在我们必须添加满足行和约束的所有置换。在

已经设置的值（7和4）的和为11。因此，6元组中的前两个条目必须具有sum==-13。对于第二行，推导出的条目（-4和2）的和为-2。所以这一行的剩余to项必须加起来等于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)]