魔术广场与python,使用itertools

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (56)

我有一些代码将确定N * N整数列表是否形成一个魔术方块:

import itertools

#Function square magic
def magic_square(matrix):
    dimension = len(matrix[0])
    sum_list = []

    #Horizontal code:
    sum_list.extend([sum (lines) for lines in matrix])   

    #Vertical code:
    for col in range(dimension):
        sum_list.append(sum(row[col] for row in matrix))

    #Diagonals code
    diagonal1 = 0
    for i in range(0,dimension):
        diagonal1 +=matrix[i][i]
    sum_list.append(diagonal1)  

    diagonal2 = 0
    for i in range(dimension-1,-1,-1):
        diagonal2 +=matrix[i][i]
    sum_list.append(diagonal2)

    if len(set(sum_list))>1:
        return False
    return True

m=[[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]] 
print(magic_square(m))

m=[[2, 7, 6], [9, 5, 1], [4, 3, 8]]
print(magic_square(m))

m=[[2, 7, 6], [9, 5, 1], [4, 3, 7]]
print(magic_square(m))

print("**************************")

#Now, i use itertools like this:
for i in itertools.combinations(range(1,10), 3):
    if sum(i) == 15:
        print (i)
# I get the combinations each of three numbers with sum 15

我的问题是最后一部分:我想生成整数1到N ^ 2的所有排列,将每个排列成一个正方形 - 一个N行和N列的二维列表 - 并使用我的函数找到所有魔法广场。我编写的itertools代码找到了3个数字的组合来完成这项工作,但我无法弄清楚组合形成方块。

谢谢@Prune的帮助。

如果我有: [1 5 9] [1 6 8] [2 4 9] [2 5 8] [2 6 7] [3 4 8] [3 5 7] [4 5 6] 我如何生成一个正方形魔术,知道它是真的假的,一次使用三个矩阵的元素? 示例: [[1 5 9],[1 6 8],[2 4 9]] 或 [[1 5 9],[1 6 8],[2 5 8]] 或 [[1 5 9],[ 1 6 8],[2 6 9]]等等,等等。

提问于
用户回答回答于

给定停止点的算法

您目前拥有三个不同整数1-9的所有八种可能组合,总和为15.要以您所要求的直接方式解决魔方,我建议采取以下步骤:

  • 生成每个组合的所有排列:每个组合六个,总共48个。一种方法是在当前代码中生成所有排列(而不是组合)。
  • 一次3个排列中考虑这些行。对于每个排列,检查以生成的顺序堆叠行是否形成正方形。你可以查看:
    • 这三列中的每一列总和为15吗?
    • 每个对角线总和为15吗?
    • 这9个号码是唯一的吗?

更快的代码

有多种方法来攻击排列以提高效率。例如,将行按最低元素(1,2,3或4)分为四组。在生成方块时,从每个组中选择不超过一行。这将大大减少您检查的总方块,因为它减少了元素的重复。

另一种方法是选择前两行,然后从列总和中派生第三行。然后你只有四个检查:两个对角线总和为15,生成的底行合法(只有数字1-9),并且没有重复的数字。

更有效地查找8行

您不必通过720三元组来找到8行。相反,生成90个起始对; 对于每一个,导出第三个元素(15减去前两个)。如果第三个元素是7个缺失数字中的一个(1-9,但前两个都没有),那么它就是你想要的行之一。

我希望这能引导您找到解决方案。

用户回答回答于

我明白了 - 你想生成魔术方块的所有排列。您需要覆盖范围从1到N ^ 2的所有排列,每个排列为NN元素列表。

import itertools

N = 3
for seq in itertools.permutations(range(1, N*N+1)):
    # Split the sequence into a candidate magic square,
    #   N rows of N elements each.
    cand = [seq[i:i+N] for i in range(0, N*N, N)]

这产生了一系列候选正方形; 饲料每一个,反过来,你的日常检查,并打印所出现的那些。我希望你能处理那个部分。

以下是一代早期的一些候选样本:

[(1, 3, 5), (6, 2, 8), (4, 7, 9)]
[(1, 3, 5), (6, 2, 8), (4, 9, 7)]
[(1, 3, 5), (6, 2, 8), (7, 4, 9)]
[(1, 3, 5), (6, 2, 8), (7, 9, 4)]
[(1, 3, 5), (6, 2, 8), (9, 4, 7)]
[(1, 3, 5), (6, 2, 8), (9, 7, 4)]
[(1, 3, 5), (6, 2, 9), (4, 7, 8)]
[(1, 3, 5), (6, 2, 9), (4, 8, 7)]
[(1, 3, 5), (6, 2, 9), (7, 4, 8)]
[(1, 3, 5), (6, 2, 9), (7, 8, 4)]
[(1, 3, 5), (6, 2, 9), (8, 4, 7)]
[(1, 3, 5), (6, 2, 9), (8, 7, 4)]

改变方法

请注意,这不是您的原始算法:这会生成整个正方形,而不仅仅是3行。独立生成具有逻辑缺陷,因为它将生成不包括所有9个数字的魔术方块,同时复制其他数字。例如:

7 2 6
4 5 6
4 8 3

扫码关注云+社区

领取腾讯云代金券