Permuting Magic Squares

Question

我在编写用于求解Magic Squares的递归置换函数时遇到了一些麻烦.对于这个函数,我不允许使用二维数组,只能使用列表.以下是我目前的情况:

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

事实上它似乎并不应该基本上永远不会终止它当前编写的方式.

开始思考这个问题的一个简单方法是,魔术方块可以用大小列表示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.有两种方法可以处理不同程度的复杂程度,具体取决于您要做什么.