python - 使用约束包解决魔方问题

Question

我正在尝试使用 Python 实现魔方求解器。我正在使用约束包。与这里提出的问题不同，我没有任何预填充的幻方。我需要使用以下求解器来实现解决方案：BacktrackingSolver、RecursiveBacktrackingSolver 和 MinConflictsSolver。我已经实现了以下代码，并且能够获得 3x3 平方的解决方案（我正在使用以下公式计算平方和：num_squares*(num_squares**2+1)//2）。但是，此逻辑不适用于任何大于 3 的数字。除此之外，运行时间也在呈指数增长。有没有办法解决这个问题？

from constraint import *
N = 4
Sum = N*(N**2+1)//2
A = list(range(0,N**2))
lst = np.reshape(A, (-1, N))

p = Problem()
p.addVariables(range(N**2), range(1,(N**2)+1))
p.addConstraint(AllDifferentConstraint(), range(N**2))
p.addConstraint(ExactSumConstraint(Sum), [lst[i][i] for i in range(len(lst))])
p.addConstraint(ExactSumConstraint(Sum), [lst[i][len(lst)-1-i] for i in range(len(lst))])
for row in range(N):
    p.addConstraint(ExactSumConstraint(Sum),[row*N+i for i in range(N)])
for col in range(N):
    p.addConstraint(ExactSumConstraint(Sum), [col+N*i for i in range(N)])

标签： pythonconstraint-programminggame-theorymagic-square