论文部分内容阅读
幻方起源于中国,且一直被人们所喜爱。自1890年法国数学家发现了第一个多重幻方—8阶2重幻方,幻方世界变得更加的绚丽多彩。然而,构造多重幻方是个很棘手的难题,特别是低阶多重幻方。计算机的快速发展为幻方的研究注入了新的生命力,高速运行的计算机可以为人类完成繁琐的重复作业,从而使得幻方的构造可以不再只依赖于数学方法。至今为止发现,最小的奇数阶3重幻方是81阶3重幻方,而12阶以下没有3重幻方。可以看出,利用回溯法求解低阶3重幻方拥有很高的难度。 多重幻方的求解空间是非常庞大的,直接暴力搜索难以得到预期的效果,因此需要缩减搜索空间。本文采用改进的回溯算法来求解奇数阶3重幻方,以及利用奇数阶多重幻方关于中心点对称这个特性来构造幻方,此外还提出使用上下界函数与奇偶数限制函数对树形空间进行剪枝优化。我们以构建一个15阶3重幻方为实践案例,并应用论文所提出的三处优化。实验结果表明这些改进与拓展可以有效地减少搜索空间、减少回溯,从而达到缩短搜索时间的目标。这种方案阐述了计算机搜索多重幻方解空间的一种思想框架。本文所使用的算法对于求解多重幻方有一定的参考意义。