任意阶魔方阵（幻方）的算法及C语言实现

2022-04-28 04:56:06

写于2012.10:

本来这是谭浩强那本《C程序设计（第四版）》的一道课后习题，刚开始做得时候去网上找最优的算法，结果发现奇数和双偶数（4的倍数）的情况下算法都比较简单，但是单偶数（2的倍数但不是4的倍数）情况一直找不到明确的算法，就连百度百科对这一问题的解释也是“因非四的倍数作法相当复杂，在此只介绍四的倍数的作法”，而且连谭浩强那本书给的答案中竟然也变相的限定了n只能为奇数（题目并未说明）。在广泛查找资料后，发现了一篇由中南大学信息科学与工程学院某教授和研究生撰写的论文，介绍了任意阶幻方的算法，由于网上的资料残缺不全，也有不少打印错误，一直没弄懂那片论文所介绍的方法（论文地址附后，感兴趣的同学可以看看）。当时也就没编单偶数的情况直接交了作业。

今天又来重新做这道未完成的题，在网上图书馆查阅了资料，后来不经意间发现用“幻方”作为关键字搜出了不少算法（深刻说明某问题…….），详细阅读之后，发现单偶数情况的算法并不是很复杂，网上牛人还是很多的嘛，于是自己尝试着完成了这道题。

回到主题，任意阶魔方阵（幻方）的算法（这里每种情况只介绍比较常用的一种，其他算法文后附地址，感兴趣的同学可以看看）：

1、奇数情况：罗伯特法，也称楼梯法。

填写方法是这样：
把1(或最小的数)放在第一行正中；按以下规律排列剩下的n*n-1个数：
(1)、每一个数放在前一个数的右上一格；
(2)、如果这个数所要放的格已经超出了顶行那么就把它放在底行，仍然要放在右一列；
(3)、如果这个数所要放的格已经超出了最右列那么就把它放在最左列，仍然要放在上一行；
(4)、如果这个数所要放的格已经超出了顶行且超出了最右列，那么就把它放在前一个数的下一行同一列的格内；
(5)、如果这个数所要放的格已经有数填入，处理方法同(4)。
这种写法总是先向“右上”的方向，像是在爬楼梯。

2、双偶数情况：对角线互补法：
先说明一个定义：
互补：如果两个数字的和，等于幻方最大数和最小数的和，即 n*n+1，称为互补。

先看看4阶幻方的填法：将数字从左到右、从上到下按顺序填写：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

将对角线上（包括主对角线和次对角线）的数字，换成与它互补的数字。
这里，n*n+1 = 4*4+1 = 17；
把1换成17-1 = 16；把6换成17-6 = 11；把11换成17-11 = 6……换完后就是一个四阶幻方。
16 2 3 13
5 11 10 8
9 7 6 12
4 14 15 1
所以，对于n=4k阶幻方，我们先把数字按顺序填写。写好后，按4*4把它划分成k*k个方阵。因为n是4的倍数，一定能用4*4的小方阵分割。然后把每个小方阵的对角线，象制作4阶幻方的方法一样，对角线上的数字换成互补的数字，就构成幻方。下面是8阶幻方的作法：
(1) 先把数字按顺序填。然后，按4*4把它分割成2*2个小方阵
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
(2) 每个小方阵对角线上的数字，换成和它互补的数。
64 2 3 61 60 6 7 57
9 55 54 12 13 51 50 16
17 47 46 20 21 43 42 24
40 26 27 37 36 30 31 33
32 34 35 29 28 38 39 25
41 23 22 44 45 19 18 48
49 15 14 52 53 11 10 56
8 58 59 5 4 62 63 1