Как бы я сгенерировал решения, чтобы заполнить матрицу 3х3 числами 1-9 и всеми строками и столбцами, добавляющими до 1 числа?

Question

Я пытаюсь найти способ получить как можно больше решений для матрицы 3х3, чтобы все строки и столбцы складывались в одно число. Он должен использовать цифры 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, которая будет генерировать для вас каждую последовательность чисел. Затем нужно убедиться, что суммы все согласны. Мы можем упростить это, используя наблюдение @ Johan C, что каждая строка и столбец должны в сумме составлять 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, потому что сумма трех строк вместе должна быть равна сумме чисел от 1 до 9, то есть 45.

Вот способ создания всех 72 решений с использованием Z3 , решения с открытым исходным кодом SAT / SMT . Обратите внимание, что Z3 является мощным решением для такого рода комбинаторных задач и, вероятно, немного излишним для этой конкретной c. Но это может быть использовано в качестве примера того, как такие комбинаторные проблемы могут быть решены, также гораздо более хитрые. См., Например, этот длинный список примеров.

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.