排列魔方阵

Question

我在写一个递归的排列函数，用来解决魔方阵的问题时遇到了一些麻烦。这个函数不能使用二维数组，只能用列表。下面是我目前写的代码：

def permute(size):
    magicSquare = []
    for value in permute(size**2):
        for pos in range(size**2 + 1):
            magicSquare.append(value)
    return magicSquare

size 是用户通过命令行参数定义的。

我有点困惑，上面的函数是否真的能完成值的排列这个任务。

Answer 1

这里有一个简单的方法来检查一个方阵是否是魔方阵。

注意：请先尝试使用3*3的格子。

def magic():
    print "maximam 9 values"
    a=[]
    for i in range(3):
        a.append([])
        for j in range(3):
            a[i].append(input('Enter the values'))
    print a
    l1= a[0][0]+a[1][0]+a[2][0]
    l2=a[0][1]+a[1][1]+a[2][1]
    l3=a[0][2]+a[1][2]+a[2][2]
    r1=sum(a[0])
    r2=sum(a[1])
    r3=sum(a[2])
    if l1 == l2 == l3 == r1 == r2 == r3:
        print a,"Its magic square"
    else:
        print a,"not magic square"
magic()

Answer 2

目前的写法基本上不会终止，实际上也不应该这样终止。

想要理解这个问题，可以把魔方阵想象成一个大小为 n**2 的列表，比如一个3x3的魔方阵可以用一个长度为9的列表来表示。因为这是一个魔方阵，所以你需要对 range(1,n+1) 的值进行排列组合，比如对于3x3的情况：

1 2 3
4 5 6
7 8 9

检查这个是否是一个魔方阵（其实不是，因为行的和不相等），如果是，就把它加入你的魔方阵列表。不管结果如何，继续尝试下一个排列组合：

1 2 3
4 5 6
7 9 8

…直到没有更多的排列组合为止。当然，这种方法并不是最优的，因为问题行（1, 2, 3）的和仍然不会等于15，所以这里还有优化的空间，可以轻松地排除那些不可能的组合。

一个简单的工具可以帮助你检查工作或为你处理排列组合的部分，那就是itertools.permutations。这个工具会创建一个生成器，它会逐个产生每个排列组合，直到没有更多为止。

需要注意的是，如果方阵的大小超过简单的情况，使用这种方法每次递归调用时，你会超过最大递归限制。一旦 size=3，你需要找到一种方法来处理这种情况。根据你想要做的事情，有几种不同复杂度的处理方法。