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

Question

我正在尝试使用 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（基于幻方上的行）。

你有什么想法吗？谢谢。

Answer 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 元组中的前两个条目必须具有 sum == -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)]

Answer 2

MagicSquare 在 NuCS 中建模（https://github.com/yangeorget/nucs/blob/main/nucs/examples/magic_square/magic_square_problem.py），如果这可以帮助的话。