我正在尝试找到一个幻方，其元素是自然数的不同平方。
对于魔方的每一行或每一列，我有 200 个 4 个数字的解。但是我如何将它们组合成总和为 8515 的 16 个数字，魔方中可能的和之一？
我们如何制作一个适用于任何给定数字和 n x n 的通用程序。
import math
import time
from collections import Counter
def find_solutions(N):
solutions = set()
sqrt_N = int(math.isqrt(N)) # Calculate the square root of N
for a in range(sqrt_N + 1):
a_squared = a**2
for b in range(sqrt_N + 1): # Start from 0
b_squared = b**2
for c in range(sqrt_N + 1): # Start from 0
c_squared = c**2
remaining = N - a_squared - b_squared - c_squared
if remaining < 0:
break # Stop if remaining is negative
d = int(math.isqrt(remaining))
d_squared = d**2
if a_squared + b_squared + c_squared + d_squared == N and len({a, b, c, d}) == 4:
solutions.add(tuple(sorted([a, b, c, d])))
return solutions
# Specify your value of N
N = 8515 # Change this to your desired value
# Print the result and execution time
solution_count = len(solutions)
if solution_count == 0:
print(f"No solutions found for a^2 + b^2 + c^2 + d^2 = {N}")
else:
print(f"Number of unique solutions for a^2 + b^2 + c^2 + d^2 = {N}: {solution_count}")
# Calculate total occurrences for each number in the list of solutions
total_counts = Counter([num for sublist in solutions for num in sublist])
# Calculate percentages for each number
total_solutions = sum(total_counts.values())
number_percentages = {num: (count / total_solutions) * 100 for num, count in total_counts.items()}
# Sort solutions by total percentage in descending order
sorted_solutions = sorted(solutions, key=lambda solution: sum(number_percentages[num] for num in solution), reverse=True)
# Print the results
print("\nSolutions in Descending Order of Total Percentage:")
print("{:<30} {:<10}".format("[a, b, c, d]", "Total Percentage"))
for solution in sorted_solutions:
total_percentage = sum(number_percentages[num] for num in solution)
print("{:<30} {:<10.5f}%".format(str(solution), total_percentage))
好吧，我一直在尝试暴力，我一直在尝试不同的搜索算法，但没有任何对我有用，我只需要克服它。我一直在尝试图论，但需要太多时间。我什至将幻方中的每个值想象为函数，因为它就像二次函数 f(x) = a^2 + k 。然后以某种方式优化它。但是，它对我不起作用。我请求社区的帮助！谢谢。
首先，在求 4 个数字（a、b、c、d）的解时，可以引入约束 a < b < c < d into the search by adjusting the ranges. You don't need to check if some of the numbers are equal; you don't need to sort them, and you can arrange the solutions as a
listsetlistdef find_solutions(N):
solutions = []
sqrt_N = int(math.isqrt(N)) # Calculate the square root of N
for a in range(0, sqrt_N):
a_squared = a**2
for b in range(a+1, sqrt_N): # Start from a+1, not from 0
b_squared = b**2
for c in range(b+1, sqrt_N): # Start from b+1, not from 0
c_squared = c**2
remaining = N - a_squared - b_squared - c_squared
if remaining <= c_squared:
break # Stop if remaining is too small
d = int(math.isqrt(remaining))
d_squared = d**2
if a_squared + b_squared + c_squared + d_squared == N:
solutions.append((a, b, c, d))
return solutions
要找到幻方，您应该组合 4 行解决方案，并检查列是否违反幻方条件。暴力搜索可能是这样的：
for a, b, c, d in solutions:
for e, f, g, h in solutions:
for i, j, k, l in solutions:
for m, n, o, p in solutions:
if (whatever):
# print the solution
为了提高搜索性能，您可以以不同的顺序进行迭代。幻方中的数字有很多限制；准则是检查尽可能靠近外环的约束。更改迭代顺序可以尽早应用约束。
我注意到，对于幻方的一行中的每一对相邻数字，其余数字的选择非常有限。例如，如果一列或一行中有 80 和 25，则其他数字要么是 11 和 37，要么是 23 和 31 — 只有 4 种可能性（考虑顺序）！
要利用这一点，请制作一本字典，说明每对数字存在哪些可能性。
poss = {}
for s in solutions:
for a, b, c, d in itertools.permutations(s):
if (a, b) not in poss:
poss[(a, b)] = []
poss[(a, b)].append((c, d))
开始搜索左上角的 4 个数字。它们的限制是它们应该不同，并且应该出现在列解决方案列表中。
# a b * *
# c d * *
# * * * *
# * * * *
for a, b in poss:
for e, f in poss:
if a == e or a == f or b == e or b == f:
continue
if (a, e) not in poss or (b, f) not in poss:
continue
接下来，迭代右上角 4 个数字的可能值。对它们的限制是它们应该全部不同，并且应该出现在列解决方案列表中。
# a b c d
# e f g h
# * * * *
# * * * *
for a, b in poss:
for e, f in poss:
if a == e or a == f or b == e or b == f:
continue
if (a, e) not in poss or (b, f) not in poss:
continue
for c, d in poss[(a, b)]:
for g, h in poss[(e, f)]:
if len(set((a, b, c, d, e, f, g, h))) != 8:
continue
if (c, g) not in poss or (d, h) not in poss:
continue
接下来，迭代左下 4 个数字的可能值。对它们的限制是它们应该全部不同，并且应该出现在行解决方案列表中。
# a b c d
# e f g h
# i j * *
# m n * *
for a, b in poss:
for e, f in poss:
if a == e or a == f or b == e or b == f:
continue
if (a, e) not in poss or (b, f) not in poss:
continue
for c, d in poss[(a, b)]:
for g, h in poss[(e, f)]:
if len(set((a, b, c, d, e, f, g, h))) != 8:
continue
if (c, g) not in poss or (d, h) not in poss:
continue
for i, m in poss[(a, e)]:
for j, n in poss[(b, f)]:
if len(set((a, b, e, f, i, j, m, n))) != 8:
continue
if (i, j) not in poss or (m, n) not in poss:
continue
最后，迭代其余的数字。检查它们的所有限制。
# a b c d
# e f g h
# i j k l
# m n o p
for a, b in poss:
for e, f in poss:
if a == e or a == f or b == e or b == f:
continue
if (a, e) not in poss or (b, f) not in poss:
continue
for c, d in poss[(a, b)]:
for g, h in poss[(e, f)]:
if len(set((a, b, c, d, e, f, g, h))) != 8:
continue
if (c, g) not in poss or (d, h) not in poss:
continue
for i, m in poss[(a, e)]:
for j, n in poss[(b, f)]:
if len(set((a, b, e, f, i, j, m, n))) != 8:
continue
if (i, j) not in poss or (m, n) not in poss:
continue
for k, o in poss[(c, g)]:
for l, p in poss[(d, h)]:
solution = (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
if len(set(solution)) != 16:
continue
if (k, l) not in poss[(i, j)] or (o, p) not in poss[(m, n)]:
continue
# print the solution
至于更大尺寸的幻方——我认为这个想法在那里也适用，但也许你可以找到更好的。