我将如何生成解决方案以填充数字为 1-9 的 3x3 矩阵，所有行和列加起来最多为 1 个数字?

Question

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

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

我有一个字典，其中可用数字按大小分组，还有一个矩阵，其中包含 3 个最大的数字，每个数字都在单独的行中，因为如果它们在同一行中，则不会加起来。

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

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

Answer 1

有两个问题需要解决：

1. 生成新的可能解决方案
2. 验证解决方案是否有效

第一步很简单;python包含一个permutation函数，它将为你生成每一个数字排列。 然后，您需要验证总和是否一致。我们可以通过使用 @JohanC 的观察来简化它，即每一行和列的总和必须为 15。

from itertools import permutations

def all_sums():
# Generate all possible grids
r = range(1, 10)
grids = permutations(r)
# Only keep grids that are valid solutions
solutions = [g for g in grids if _all_sums_are_15(g)]
return solutions

def _all_sums_are_15(grid):
"""Check that each row and column of the grid sums to 15"""
return (_sum_is_15(grid, 0, 1, 2) and
_sum_is_15(grid, 3, 4, 5) and
_sum_is_15(grid, 6, 7, 8) and
_sum_is_15(grid, 0, 3, 6) and
_sum_is_15(grid, 1, 4, 7) and
_sum_is_15(grid, 2, 5, 8))

def _sum_is_15(grid, a, b, c):
"""Determine if the given 3 cells in the grid sum up to 15"""
sum_ = grid[a] + grid[b] + grid[c]
return sum_ == 15

if __name__ == '__main__':
for s in all_sums():
print(s)

Answer 2

首先，请注意，每行/列的总和必须为 15，因为 3 行的总和必须等于从 1 到 9 的数字之和，因此为 45。

这是一种使用 Z3(开源 SAT/SMT 求解器(生成所有 72 个解决方案的方法。请注意，Z3 是这类组合问题的强大求解器，对于这个特定的问题来说可能有点矫枉过正。但它可以用作如何处理此类组合问题的一个例子，也可以用作更棘手的问题。例如，请参阅这一长串示例。

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!行排列乘以 3！镜像的列排列乘以 2，总共 72

。