基于约束编程的幻方解算器

Question

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

对于这个问题，幻方的定义是：“幻方是n×n矩阵中的整数(正或负)的排列，并且使得任何行、任何列或任何主对角线的项的和是相同的。”

我有一个预填充的魔术方块，如下所示：

+----+----+----+----+
| 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 (基于我们在幻方上的行)。

你有什么想法吗？谢谢。

Answer 1

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

第一行上的行约束告诉您，pos处的值。4是-4。离对角线的约束告诉你，位置处的值。6等于2。

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

因此，我们必须选择范围(-20，20)之外的六个值，而不是已经选择的值。

在一个有4乘4项的魔方中，行/列/对角线和必须是

1/4* sum(all_entries)

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

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)的sum为-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) sum 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)]