解决这个矩阵难题的更有效的解决方案？

Question

求行数、列数和对角线之和为15的3x3矩阵M。条件：1-9的每个数都必须用到。

我不是很聪明，所以我尝试了这个暴力方法：

def solve_999():
    for a in range(1, 10):
        for b in range(1, 10):
            for c in range(1, 10):
                for d in range(1, 10):
                    for e in range(1, 10):
                        for f in range(1, 10):
                            for g in range(1, 10):
                                for h in range(1, 10):
                                    for i in range(1, 10):
                                        if (a+b+c == d+e+f == g+h+i == a+d+g == b+e+h == c+f+i == a+e+i == c+e+g == 15):                                           
                                            if check_unique([a, b, c, d, e, f, g, h, i]):
                                                print(a, b, c)
                                                print(d, e, f)
                                                print(g, h, i)
                                                return


def check_unique(L):
    d = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0}
    for letter in L:
        d[letter] += 1
        if d[letter] > 1:
            return False
    return True

它有效，但效率不高。谁能帮我找到更有效的解决方案？

Answer 1

您将获得的最大加速将来自生成您的正方形，以便它们已经是独一无二的。最简单的方法是 itertools.permutations。这将使您减少到检查 9！ == 362880 块板而不是 387420489 块板（大约工作量的 1/1000）并且您不必检查以确保它们是唯一的。

from itertools import permutations
t1=time()
for board in permutations(list(range(1,10)),9):
    if sum(board[0:3]) == 15:
        if sum(board[3:6])== 15:
            if board[0]+board[3]+board[6]==15:
                if board[1]+board[4]+board[7]==15:
                    if board[0]+board[4]+board[8]==15:
                        if board[2]+board[4]+board[6]==15:
                            print(board[0:3])
                            print(board[3:6])
                            print(board[6:9])
                            break

此解决方案的一个主要问题是我们仍在检查比我们需要的更多的案例。需要注意的是，对于每个 (a,b,d,e)，c、f、g、h 和 i 中的每一个都存在最多 1 个值。这意味着我们只需检查 9P4 == 3024 种可能性。这样做的缺点是我们无法保证所有值都是唯一的。但即使我们添加了这个检查，我们仍然看到比我们更简单的代码再加速 10 倍。

def solve_999():
    for a,b,d,e in permutations(range(1,10),4):
        c = 15 - (a + b)
        f = 15 - (d + e)
        g = 15 - (a + d)
        h = 15 - (b + e)
        i = 15 - (a + e)
        if 15 == g+h+i == c+f+i == c+e+g:
            if len(set([a,b,c,d,e,f,g,h,i]))==9:
                 print(a, b, c)
                 print(d, e, f)
                 print(g, h, i)
                 print()
                 break

给代码计时：

from timeit import timeitrom itertools import permutations
def solve_999():
    for a,b,d,e in permutations(range(1,10),4):
        c = 15 - (a + b)
        f = 15 - (d + e)
        g = 15 - (a + d)
        h = 15 - (b + e)
        i = 15 - (a + e)
        if 15 == g+h+i == c+f+i == c+e+g:
            if len(set([a,b,c,d,e,f,g,h,i]))==9:
                return
print(timeit(solve_999, number=1000))

产生 2.9 的时间 seconds/10000 尝试 == .00029 sec/try

Answer 2

您可以使用 itertools.permutations 库遍历所有可能性来检查您需要的总和。

虽然您的代码适用于固定大小的输入数组（在本例中为 3x3 = 9），但我已将其概括为检查通过使用某些 python 提供的任何范围内的任何给定总和辅助拼接。请注意，输入的长度必须是一个完美的正方形才能起作用。

from itertools import permutations
from math import sqrt

def check_magic_square(rangeallowed,sumMS):
    sidelenght = int(sqrt(len(rangeallowed)))
    for i in permutations(rangeallowed):
        # initialize all conditions to be satisfied
        MSConditionsSatisfied = True
        # Check for forward diagonal sum
        if (MSConditionsSatisfied and sum(i[::sidelenght+1]) != sumMS): MSConditionsSatisfied = False
        # Check for reverse diagonal sum
        if (MSConditionsSatisfied and sum(i[sidelenght-1:-1:sidelenght-1]) != sumMS): MSConditionsSatisfied = False
        for j in range(sidelenght):
            # Check for each column
            if (MSConditionsSatisfied and sum(i[j::sidelenght]) != sumMS): MSConditionsSatisfied = False
            # Check for each row
            if (MSConditionsSatisfied and sum(i[j*sidelenght:(j+1)*sidelenght]) != sumMS): MSConditionsSatisfied = False
        # if all conditions are satisfied, return the splice reshaped to be a square matrix
        if MSConditionsSatisfied: return [[i[k*sidelenght + j] for j in range(sidelenght)] for k in range(sidelenght)]
    return False

if __name__ == "__main__":
    print(check_magic_square(range(1,10),15))

returns

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

我的 i5 机器用时 0.1 秒

Answer 3

比其他的短一点：

>>> from itertools import permutations
>>> for a, b, c, d, e, f, g, h, i in permutations(range(1, 10)):
        if 15 == a+b+c == d+e+f == a+d+g == b+e+h == a+e+i == c+e+g:
            print(a, b, c)
            print(d, e, f)
            print(g, h, i)
            break

2 7 6
9 5 1
4 3 8

在我的电脑上搜索大约需要 0.009 秒。如下测算，做1000次大概需要9秒：

from itertools import permutations
from timeit import timeit

def solve_999():
    for a, b, c, d, e, f, g, h, i in permutations(range(1, 10)):
        if 15 == a+b+c == d+e+f == a+d+g == b+e+h == a+e+i == c+e+g:
            return

print(timeit(solve_999, number=1000))

Answer 4

很简单。试想一下，有多少种方法可以从三个数字的总和中得出 15。

1+5+9, 1+6+8, 2+4+9, 2+5+8, 2+6+7, 3+4+8, 3+5+7, 4+5+6

因为只有 8 种方式，所以每个和都会出现在您的方块中。 5 必须在中间，因为它出现了 4 次。 2,4,6,8 一定在角落，因为它们出现了 3 次。

继续下去，你会找到解决方案。

解决这个矩阵难题的更有效的解决方案？

A more efficient solution for solving this matrix puzzle?

python

matrix

puzzle