代码之家 › 专栏 › 技术社区 › Tjtorin

我如何生成一个3x3矩阵的解决方案,其中数字为1-9,所有行和列加起来为1?

matrix math python

-2

Tjtorin · 技术社区 · 5 年前

我正试图找到一种方法来获得尽可能多的解决方案,使3x3矩阵的所有行和列加起来都是相同的数字。它必须使用数字1-9。我发现我需要在每行使用一个大的、中的和小的数字。 前任:

2  4  9 = 15
6  8  1 = 15
7  3  5 = 15
=  =  =
15 15

nums = {
    "small" : [1, 2, 3],
    "med" : [4, 5, 6],
    "big" : [7, 8, 9]
}

m = [
    [0, 0, 9],
    [0, 8, 0],
    [7, 0, 0]
]

找到所有可能的解决方案的最佳方法是什么?

2 回复 | 直到 5 年前

Eric Grunzke 5 年前

有两个问题需要解决:

生成新的可能解决方案

第一步很简单;python包含 permutation

from itertools import permutations


def compare(perm, other_sum, a, b, c):
    new_sum = perm[a] + perm[b] + perm[c]
    return new_sum == other_sum


def all_sums():
    r = range(1, 10)
    for p in permutations(r):
        # Calculate the sum of the first row
        sum = p[0] + p[1] + p[2]

        # Check the other rows and columns to see if they match
        if compare(p, sum, 3, 4, 5) and \
                compare(p, sum, 6, 7, 8) and \
                compare(p, sum, 0, 3, 6) and \
                compare(p, sum, 1, 4, 7) and \
                compare(p, sum, 2, 5, 8):
            print(p)

JohanC 5 年前

首先,注意每一行/列的和必须是15,因为3行的和必须等于从1到9的数字的和,所以是45。

下面是使用 Z3 ,一个开放源代码 SAT/SMT 求解器。请注意,Z3是解决此类组合问题的一个强大的解决方案,对于这个特定的问题可能有点过分了。但它可以作为一个例子,说明如何处理这样的组合问题,也可以是更棘手的问题。参见例如。 this

from z3 import *

# get 9 integer variables for the matrix elements
M = [[Int(f"m{i}{j}") for j in range(3)] for i in range(3)]
# create a Z3 solver instance
s = Solver()
# all numbers must be between 1 and 9
s.add([And(M[i][j] >= 1, M[i][j] <= 9) for i in range(3) for j in range(3)])
# all the rows must sum to 15
s.add([And([Sum([M[i][j] for j in range(3)]) == 15]) for i in range(3)])
# all the columns must sum to 15
s.add([And([Sum([M[i][j] for i in range(3)]) == 15]) for j in range(3)])
# all 9 numbers must be distinct
s.add(Distinct([M[i][j] for i in range(3) for j in range(3)]))
res = s.check()
num_solutions = 0
while res == sat:
    num_solutions += 1
    m = s.model()
    print(num_solutions, ":", [[m[M[i][j]] for j in range(3)] for i in range(3)])
    # add a new condition that at least one of the elements must be different to the current solution
    s.add(Or([m[M[i][j]].as_long() != M[i][j] for i in range(3) for j in range(3)]))
    res = s.check()

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

所有的解都是等价的。您可以排列解决方案的行和列以获取另一个解决方案。你可以镜像一个解决方案。三!排置换乘以3!列排列乘以镜像的2,总共72。