如何高效构建平方幻方：从四元组到N阶矩阵的搜索优化策略

import math
import time

def find_solutions(N):
    """
    高效查找满足 a^2 + b^2 + c^2 + d^2 = N 的四元组 (a, b, c, d)，
    其中 a, b, c, d 是互不相同的自然数。
    """
    solutions = []
    sqrt_N = int(math.isqrt(N))  # 计算N的平方根，作为搜索上限

    # 引入 a < b < c < d 约束来优化搜索
    for a in range(0, sqrt_N):
        a_squared = a**2
        for b in range(a + 1, sqrt_N):  # b从a+1开始，确保b > a
            b_squared = b**2
            for c in range(b + 1, sqrt_N):  # c从b+1开始，确保c > b
                c_squared = c**2
                remaining = N - a_squared - b_squared - c_squared

                # 提前剪枝：如果剩余值过小，不可能找到满足条件的d
                if remaining <= c_squared:
                    break

                d = int(math.isqrt(remaining))
                d_squared = d**2

                # 检查是否满足 a^2 + b^2 + c^2 + d^2 == N
                # 并且由于循环条件，d自然大于c，因此a, b, c, d是四个不同的数
                if a_squared + b_squared + c_squared + d_squared == N:
                    solutions.append((a, b, c, d))

    return solutions

# 示例：查找和为8515的四元组
N = 8515
start_time = time.time()
solutions_quadruplets = find_solutions(N)
end_time = time.time()
print(f"找到 {len(solutions_quadruplets)} 组和为 {N} 的四元组，耗时 {end_time - start_time:.4f} 秒。")
# print("部分四元组示例:", solutions_quadruplets[:10])

import itertools

def preprocess_pairs(solutions_quadruplets):
    """
    根据四元组列表，构建一个字典，映射 (a, b) 到所有可能的 (c, d) 组合，
    使得 a^2 + b^2 + c^2 + d^2 = N。
    """
    poss = {}
    for s in solutions_quadruplets:
        # 对每个四元组 s 进行所有排列
        for a, b, c, d in itertools.permutations(s):
            if (a, b) not in poss:
                poss[(a, b)] = []
            poss[(a, b)].append((c, d))
    return poss

# 假设 solutions_quadruplets 已通过 find_solutions(N) 获得
# poss_dict = preprocess_pairs(solutions_quadruplets)
# print(f"预处理得到 {len(poss_dict)} 组相邻对。")