-5

我有一些代码可以确定 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]] 等等等等。

4

3 回答 3

0

我明白了——你想生成幻方的所有排列。您需要涵盖从 1 到N ^2 范围内的所有排列,返回为N个列表,每个列表包含N个元素。

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)]

这会产生一系列候选方格;依次将每一个输入到您的检查程序中,并打印出现的True。我希望你能处理好那部分。

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

[(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
于 2016-12-29T00:32:38.037 回答
0

给定停止点的算法

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

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

更快的代码

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

另一种方法是选择前两行,然后从列总和中得出第三行。然后您只需进行四项检查:两条对角线之和为 15,生成的底行是否合法(只有数字 1-9),以及没有重复的数字。

更有效地查找 8 行

您无需翻阅 720 个三元组即可找到 8 行。相反,生成 90 个起始对;对于每个,推导出第三个元素(15 减去前两个)。如果第三个元素是 7 个缺失数字之一(1-9,但前两个都不是),那么它就是您想要的行之一。

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

于 2017-01-03T17:49:29.463 回答
0

这是一个准单线的解决方案(有利于在找到答案时产生答案)。它将长度 N*N 的排列映射到 numpy reshape,然后确定矩阵是否是魔法。

import numpy
import functools
import itertools

N = 3
for item in filter(lambda o: len(set(numpy.sum(o, axis=0))
                                 .union(numpy.sum(o, axis=1))
                                 .union({o.diagonal().sum()})
                                 .union({numpy.fliplr(o).diagonal().sum()})
                                 ) == 1,
                   map(functools.partial(numpy.reshape, newshape=(N, N)), 
                       itertools.permutations(range(N*N)))):
    print(item)
于 2018-07-12T23:57:30.977 回答