python - 优化幻方生成时出现问题

Question

我对编程还很陌生，目前正在尝试根据用户输入生成幻方。我已经成功地创建了某种适用于 3x3 正方形的令人厌恶的东西。我遇到的问题是，因为我随机生成一个正方形，而不检查该组合以前是否使用过，所以任何大于 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