幻方：任何行、列或对角线的长度之和总是等于相同的数字所有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幻方呢？
最佳答案
这里有一个非常简单的实现，使用状态空间搜索和基本剪枝来生成给定维度的所有可能的幻方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
虽然我必须说它在运行时间方面的表现比预期的要差一些，但我想它仍然是一个好的开始将尝试在一段时间内进一步优化它。