Каков оптимальный способ генерации всех возможных магических квадратов 3X3?

Question

Магический квадрат: сумма любой строки, столбца или диагонали длины всегда равна одному и тому же числу.Все 9 чисел являются различными положительными целыми числами.

Я делаю это таким образом в JavaScript, но каков оптимальный способ генерации их всех?

function getMagicSquare() {

let myArray = [
    [4, 9, 2],
    [3, 5, 7],
    [8, 1, 5]
];

for (let index1 = 1; index1 < 10; index1++) {
    for (let index2 = 1; index2 < 10; index2++) {
        for (let index3 = 1; index3 < 10; index3++) {
            for (let index4 = 1; index4 < 10; index4++) {
                for (let index5 = 1; index5 < 10; index5++) {
                    for (let index6 = 1; index6 < 10; index6++) {
                        for (let index7 = 1; index7 < 10; index7++) {
                            for (let index8 = 1; index8 < 10; index8++) {
                                for (let index9 = 1; index9 < 10; index9++)
                                // if numbers are not distinct for each loop, I can break the loop and make it a bit faster
                                {
                                    const mySet = new Set();
                                    mySet.add(index1).add(index2).add(index3).add(index4).add(index5).add(index6).add(index7).add(index8).add(index9)
                                    if ((mySet.size === 9))
                                        if (
                                            (index1 + index2 + index3 === index4 + index5 + index6) &&
                                            (index4 + index5 + index6 === index7 + index8 + index9) &&
                                            (index7 + index8 + index9 === index1 + index4 + index7) &&
                                            (index1 + index4 + index7 === index2 + index5 + index8) &&
                                            (index2 + index5 + index8 === index3 + index6 + index9) &&
                                            (index3 + index6 + index9 === index1 + index5 + index9) &&
                                            (index1 + index5 + index9 === index3 + index5 + index7)
                                        ) {
                                            myArray[0][0] = index1;
                                            myArray[0][1] = index2;
                                            myArray[0][2] = index3;
                                            myArray[1][0] = index4;
                                            myArray[1][1] = index5;
                                            myArray[1][2] = index6;
                                            myArray[2][0] = index7;
                                            myArray[2][1] = index8;
                                            myArray[2][2] = index9;

                                            console.log(myArray);

                                        }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

}

Второй вопрос: что если я хочу сгенерировать NxN магических квадратов?

Answer 1

Вот довольно наивная реализация, использующая поиск в пространстве состояний с базовым сокращением для генерации всех возможных магических квадратов данного измерения n: https://ideone.com/0aewnJ

from collections import defaultdict, deque
from copy import copy, deepcopy
import time

def magicSum(n):
    return int((n*n * (n*n + 1)) / 6)

def validate(sumDict, n):
    for k, v in sumDict.items():
        if v > magicSum(n):
            return False
    return True

def check(sumDict, n):
    for k, v in sumDict.items():
        if v != magicSum(n):
            return False
    return True

def isValid(m, n):
    rowSum = defaultdict(int)
    colSum = defaultdict(int)
    diagSum = defaultdict(int)

    isLeft = False

    for i in range(n):
        for j in range(n):
            if m[i][j] == 0: isLeft = True
            rowSum[i] += m[i][j]
            colSum[j] += m[i][j]
            if i == j: diagSum[0] += m[i][j]
            if i + j == n - 1: diagSum[n - 1] += m[i][j]

    if isLeft:
        return (validate(rowSum, n) and validate(colSum, n) and validate(diagSum, n))       
    return (check(rowSum, n) and check(colSum, n) and check(diagSum, n))        

def next(cur, m, n):
    possible = []
    for i in range(n): 
        for j in range(n):
            if m[i][j] == 0:
                nextM = deepcopy(m)
                nextM[i][j] = cur
                if isValid(nextM, n):
                    possible.append(nextM)
    return possible

def printM(m):
    for i in range(len(m)):
            print(m[i])
    print("\n")

def gen(n):
    startM = [[0 for x in range(n)] for y in range(n)]
    magic = []
    Q = deque([(1, startM)])
    while len(Q):
        state = Q.popleft()
        cur = state[0]
        m = state[1]
        if cur == n * n + 1:
            magic.append(m)
            printM(m)
            continue
        for w in next(cur, m, n):
            Q.append((cur + 1, w))
    return magic

start_time = time.time()
magic = gen(3)
elapsed_time = time.time() - start_time
print("Elapsed time: ", elapsed_time)

Вывод:

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


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


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


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


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


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


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


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


Elapsed time:  13.479725122451782

Хотя я должен сказать, что он работает немного хуже с точки зрения времени выполнения, чем ожидалось, но я думаю, что это все еще хорошо для начала.Попробую оптимизировать его в ближайшее время.