Проблемы с оптимизацией генерации магического квадрата

Question

Я все еще довольно новичок в программировании и в настоящее время пытаюсь сгенерировать магический квадрат на основе пользовательского ввода. Мне удалось создать какую-то мерзость, которая отлично работает для квадрата 3х3. Проблема, с которой я столкнулся, заключается в том, что, поскольку я генерирую квадрат случайным образом, не проверяя, использовалась ли ранее комбинация, для вычисления чего-либо большего, чем 3x3, требуется огромное количество времени. Могу ли я внести какие-либо изменения, чтобы ускорить процесс? Извиняюсь, если я неправильно отформатировал.

Заранее спасибо!

import random
import math

'''Checks if the diagonals add up to the magic sum (calculated below).'''
def diagonal_check(bList, point):
    reversedDiagonalCount = 0
    diagonalCount = 0
    if point == 0:
        for diagonal in range(magicSquareSize):
            diagonalCount += bList[diagonal][diagonal]
    else:
        for reversedDiagonal in range(magicSquareSize):
            reversedDiagonalCount += bList[-(reversedDiagonal+1)] 
   [reversedDiagonal]

    if diagonalCount == magicNumber or reversedDiagonalCount == magicNumber:
        return True
    else:
        return False


'''Iterates through column and row number "x" to see if both add up to the 
magic sum.'''
def check_magic_sum(aList, x):
    columnCount = 0
    rowCount = 0
    for columnNumber in range(magicSquareSize):
        columnCount += aList[columnNumber][x]
        if columnCount == magicNumber:
            for rowNumber in range(magicSquareSize):
                rowCount += aList[x][rowNumber]
    print(columnCount, rowCount)
    if columnCount == magicNumber and rowCount == magicNumber:
        return True
    else:
        return False


'''Once initiated, created a randomly generated n x n matrix of numbers.'''
def create_square():
    for number in range(1, magicSquareSize**2 + 1):
        numberList.append(number)
    for row in range(magicSquareSize):
        currentList = []
        magicNumberCount = magicNumber
        magicSquareSizeCount = magicSquareSize
        while len(currentList) < magicSquareSizeCount:
            rowEntry = random.choice(numberList)
            numberList.remove(rowEntry)
            currentList.append(rowEntry)
            magicNumberCount -= rowEntry
        magicSquare.append(currentList)


'''User inputs the grid size they would like, a magic number is then 
calculated for this value.'''
magicSquareSize = int(input('Please enter a number, "n" to generate an "n x 
n" magic square: '))
magicNumber = int((magicSquareSize/2) * (2+(magicSquareSize**2 - 1)))

'''Initiates an empty list to hold the magic square and the numbers used in 
it.'''
numberList = []
magicSquare = []
create_square()

'''Checks magic square to see if it is valid, if not, creates another 
randomly generated square and checks again.'''
while True:
    validSquare = 0
    for checkNumber in range(magicSquareSize):
        numberCheck = check_magic_sum(magicSquare, checkNumber)
        if numberCheck == True:
            validSquare += 1
        if checkNumber == 0 or checkNumber == magicSquareSize-1:
            isDiagonalGood = diagonal_check(magicSquare, checkNumber)
            if isDiagonalGood == True:
                validSquare += 1
    if validSquare == magicSquareSize + 2:
        break
    else:
        magicSquare = []
        create_square()

'''Prints each element in the magicSquare list one by one to display a 
roughly square shape.'''
for line in range(magicSquareSize):
    print(magicSquare[line])

Answer 1

Задача о магическом квадрате является NP-сложной, поэтому для решения N> = 4 потребуется много времени. Эта проблема может быть сформулирована как CSP (проблема удовлетворения ограничений), и с помощью пакета constraint мы можем попытаться решить ее для общего N, как показано ниже, вы можете попытаться выяснить, быстрее ли этот подход:

N = 4 #5 # number of rows / columns
n = N**2 # number of cells
s = n*(n+1)//6 # sum of each row
from constraint import *
p = Problem()
p.addVariables(range(n), range(1, n+1))
p.addConstraint(AllDifferentConstraint(), range(n))
p.addConstraint(ExactSumConstraint(s), [k*(N+1) for k in range(N)])
p.addConstraint(ExactSumConstraint(s), [(k+1)*(N-1) for k in range(N)])
for row in range(N):
 p.addConstraint(ExactSumConstraint(s),
 [row*N+i for i in range(N)])
for col in range(N):
 p.addConstraint(ExactSumConstraint(s),
 [col+N*i for i in range(N)]) 

sols = p.getSolutions()
for s in sols:
  for row in range(N):
    for col in range(N):
        print s[row*N+col],
    print
  print

Для N=3 это очень быстро и сразу печатает все возможные решения:

6 7 2
1 5 9
8 3 4

6 1 8
7 5 3
2 9 4

8 1 6
3 5 7
4 9 2

8 3 4
1 5 9
6 7 2

4 3 8
9 5 1
2 7 6

4 9 2
3 5 7
8 1 6

2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8