幻方

幻方，有時又稱魔術方陣（其簡稱「魔方」現一般指立方體的魔術方塊）或縱橫圖，由一組排放在正方形中的整數組成，其每行、每列以及每一條主對角線的和均相等。通常幻方由從$1$到$N^2$的連續整數組成，其中$N$為正方形的行或列的數目。因此$N$階幻方有$N$行$N$列，並且所填充的數為從$1$到$N^2$。

幻方可以使用$N$階方陣來表示，方陣的每行、每列以及兩條對角線的和都等於常數$M_2(N)$，如果填充數為$1,2,\dots,N^2$，那麼有

$$M_2(N) = \frac{N(N^2+1)}{2}$$

## 幻方簡史

《繫辭》云：「河出圖，洛出書，聖人則之。」在宋朝之前，洛書的記述只有文字。

九宮圖實物最早發現於西漢，1977年中國考古學家在安徽阜陽縣雙古堆西漢古墓中發現漢文帝七年（前173年）的太乙九宮占盤，乃是中國漢代幻方的實物。東漢《數術記遺》也有記載。

後來陳摶以降認為河圖洛書的洛書代表九宮圖，為$1,\dots,9$這$9$個數，而$3$行、$3$列以及兩對角線上各自的數之和均為15。

## 楊輝縱橫圖

南宋數學家楊輝著《續古摘奇演算法》把類似於九宮圖的圖形命名為縱橫圖，書中列舉3、4、5、6、7、8、9、10階幻方。其中所述三階幻方構造法：「九子斜排，上下對易，左右相更，四維挺出，戴九履一，左三右七，二四為肩，六八為足」，比法國數學家Claude Gaspar Bachet提出的方法早三百餘年。

## 構造法

根據構造方法的不同，幻方可以分成三類：奇數階幻方、$4k$階幻方和$4k+2$階幻方，其中$M$為自然數，$2$階幻方不存在。幻方構造法主要有：連續擺數法、階梯法（樓梯法）、奇偶數分開的菱形法、對稱法、對角線法、比例放大法、斯特雷奇法、LUX法、拉伊爾法（基方、根方合成法）、鑲邊法、相乘法、幻方模式等。

### 奇數階幻方構造法

#### 右斜角降位法1

假設要建構$n$階幻方，$n$為奇數。

- 先在第一橫列中央的方格填入$1$。
- 向右上方的格子推進，依次填入$2$、$3$、$4$、…、$n^2$，若超過方陣框外，則將數字填入到該橫列或該直行的相對位置。
- 若右上方的格子已有數字，則將數字填入下面的格子中。

以下圖$5$階幻方為例，$1$填寫在$(1,3)$（第一行第三列）的位置上；$2$應當填寫在其右上方格即$(0,4)$中，由於$(0,4)$超出頂邊界，所以從最底行進入，即$(5,4)$；$3$填寫在$(5,4)$的右上方格$(4,5)$中；$4$填寫在$(4,5)$的右上方格$(3,6)$中，由於$(3,6)$超出右邊界，所以從最左列進入，即$(3,1)$；$5$填寫在$(3,1)$的右上方格$(2,2)$中；$6$應該填寫的方格$(1,3)$已經被$1$所占據，因此填寫在$(2,2)$的正下方格$(3,2)$中；按照上面的步驟直到所有數填入。

$\begin{bmatrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \\ \end{bmatrix}$｜$\begin{bmatrix} 17 & 24 & 1 & 8 & 15 \\ 23 & 5 & 7 & 14 & 16 \\ 4 & 6 & 13 & 20 & 22 \\ 10 & 12 & 19 & 21 & 3 \\ 11 & 18 & 25 & 2 & 9 \end{bmatrix}$｜$\begin{bmatrix} 47 & 58 & 69 & 80 & 1 & 12 & 23 & 34 & 45 \\ 57 & 68 & 79 & 9 & 11 & 22 & 33 & 44 & 46 \\ 67 & 78 & 8 & 10 & 21 & 32 & 43 & 54 & 56 \\ 77 & 7 & 18 & 20 & 31 & 42 & 53 & 55 & 66 \\ 6 & 17 & 19 & 30 & 41 & 52 & 63 & 65 & 76 \\ 16 & 27 & 29 & 40 & 51 & 62 & 64 & 75 & 5 \\ 26 & 28 & 39 & 50 & 61 & 72 & 74 & 4 & 15 \\ 36 & 38 & 49 & 60 & 71 & 73 & 3 & 14 & 25 \\ 37 & 48 & 59 & 70 & 81 & 2 & 13 & 24 & 35 \end{bmatrix}$

$3$階｜$5$階｜$9$階

魔方陣不是唯一的，比如5階魔方陣還可以是：

$$\begin{bmatrix} 15 & 6 & 19 & 2 & 23 \\ 16 & 12 & 25 & 8 & 4 \\ 9 & 5 & 13 & 21 & 17 \\ 22 & 18 & 1 & 14 & 10 \\ 3 & 24 & 7 & 20 & 11 \end{bmatrix}$$ $5$階

#### 右斜角降位法2

假設要建構$n$階幻方，$n$為奇數。

- 先在第一橫列中央的方格填入1。
- 向「右$\frac{n-1}{2}$格、上$\frac{n-1}{2}$格」的格子推進，依次填入$2,3,4,\dots,n^2$，若超過方陣框外，則將數字填入到該橫列或該直行的相對位置。
- 若右上方的格子已有數字，則將數字填入下面的格子中。

#### 右斜角升位法

假設要建構$n$階幻方，$n$為奇數。

- 先在中央格的正上方一格的方格填入1。
- 向右上方的格子推進，依次填入$2,3,4,\dots,n^2$，若超過方陣框外，則將數字填入到該橫列或該直行的相對位置。
- 若右上方的格子已有數字，則將數字填入上面兩格的格子中。

#### 菱形法

假設要建構$n$階幻方，$n$為奇數。

- 先以對角線為兩邊，做一個包含$n$階方陣的菱形方陣，此方陣總共有$2n^2-2n+1$（第$n$個中心正方形數）個格子。
- 從這個菱形方陣中的最上方的尖端格子，由左上往右下，再由右上往左下，依次填入$1,2,3,4,\dots,n^2$。
- 將原先方陣上側外的格子向下平行移動$n$格，填入原方陣的空格處，相同的步驟，若格子是在下側，往上移，若格子是在左側，往右移，若格子是在右側，往左移。

### 偶數階幻方構造法

#### 4k階幻方構造法

##### 消去對角線法

- 將1、2、3、4、…、n2由上到下、再由左到右，依次填入。
- 將方陣以四階方陣為單位分割（可分割成n2個四階方陣），然後在每個四階方陣中，對角線上的數字擦掉。
- 把擦掉的數字由大的數開始，由上到下、再由左到右，依次填入。

##### 保留對角線法

假設要建構n階幻方，n為4的倍數。

- 將1、2、3、4、…、n2由上到下、再由左到右，依次填入。
- 將方陣以四階方陣為單位分割（可分割成n2個四階方陣），然後在每個四階方陣中，不在對角線上的數字擦掉。
- 把擦掉的數字由大的數開始，由上到下、再由左到右，依次填入。

如4階幻方的排列法：

$\begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}$ 按如上圖排列好，再將非主副對角線上的各個數關於中心對調，即成下圖：

$\begin{bmatrix} 1 & 15 & 14 & 4 \\ 12 & 6 & 7 & 9 \\ 8 & 10 & 11 & 5 \\ 13 & 3 & 2 & 16 \end{bmatrix}$ 八階幻方構造如下$\left[ \begin{array}{cccc|cccc} <pre> \diagdown & \bigstar & \bigstar & \diagup & \diagdown & \bigstar & \bigstar & \diagup \\ \bigstar & \diagdown & \diagup & \bigstar & \bigstar & \diagdown & \diagup & \bigstar \\ \bigstar & \diagup & \diagdown & \bigstar & \bigstar & \diagup & \diagdown & \bigstar \\ \diagup & \bigstar & \bigstar & \diagdown & \diagup & \bigstar & \bigstar & \diagdown \\ \hline \diagdown & \bigstar & \bigstar & \diagup & \diagdown & \bigstar & \bigstar & \diagup \\ \bigstar & \diagdown & \diagup & \bigstar & \bigstar & \diagdown & \diagup & \bigstar \\ \bigstar & \diagup & \diagdown & \bigstar & \bigstar & \diagup & \diagdown & \bigstar \\ \diagup & \bigstar & \bigstar & \diagdown & \diagup & \bigstar & \bigstar & \diagdown \\ </pre> \end{array} \right]$ 即：

$$\begin{bmatrix} <pre> 1 & 63 & 62 & 4 & 5 & 59 & 58 & 8\\ </pre> 56 & 10 & 11 & 53 & 52 & 14 & 15 & 49\\ 48 & 18 & 19 & 45 & 44 & 22 & 23 & 41\\ 25 & 39 & 38 & 28 & 29 & 35 & 34 & 32\\ 33 & 31 & 30 & 36 & 37 & 27 & 26 & 40\\ 24 & 42 & 43 & 21 & 20 & 46 & 47 & 17\\ 16 & 50 & 51 & 13 & 12 & 54 & 55 & 9\\ 57 & 7 & 6 & 60 & 61 & 3 & 2 & 64 \end{bmatrix}$$

#### 4k+2階幻方構造法

##### LUX法

在(4M+2)×(4M+2）個方格的適當格點上，先排出2M+1階的幻方。在前M+1行的格點，全部標上「L」；在第M+1行的中間格點標上「U」，其餘格點標上「L」；在第M+2行的中間格點標上「L」，其餘格點標上「U」；在餘下的M-1行的格點全部標上「X」。將格點上的數乘以4再減4，再按下面的規則加上1至4其中一個數，填入對應的格上：

```
 4 1    1 4    1 4
  L      U      X
 2 3    2 3    3 2
```

例子：

```
[ 68  65  96  93   4   1  32  29  60  57 ]
   17L     24L      1L      8L     15L
[ 66  67  94  95   2   3  30  31  58  59 ]

[ 92  89  20  17  28  25  56  53  64  61 ]
   23L      5L      7L     14L     16L
[ 90  91  18  19  26  27  54  55  62  63 ]

[ 16  13  24  21  49  52  80  77  88  85 ]
    4L      6L     13U     20L     22L
[ 14  15  22  23  50  51  78  79  86  87 ]

[ 37  40  45  48  76  73  81  84  9   12 ]
   10U     12U     19L     21U      3U
[ 38  39  46  47  74  75  82  83  10  11 ]

[ 41  44  69  72  97  100  5  8   33  36 ]
   11X     18X     25X      2X      9X
[ 43  42  71  70  99  98   7  6   35  34 ]
```

### 任何階數的幻方都適用的構造法

#### 艾歆緹雅法

此方法可用來建構任何階數的幻方，當要建構$n$階幻方時，使用兩個方陣，一個填入正整數$1$到$n$各$n$次，另一個則填入$0,n,2n,3n,\dots,(n-1)n$各$n$次，儘管奇數階幻方與偶數階幻方的填入方式有所不同。

對於奇數階幻方：

第一個方陣：在第一橫列中央的方格填入$1$，並且往左下角不斷填入$1$，若超出方陣外，則向右平移$n$格，直到每一橫列都有一個方格填入$1$為止，再把所有填入$1$的方格右邊的格子填入$2$（若超出方陣外，則向左平移$n$格），再把所有填入$2$的方格右邊的格子填入$3$，一直到填入$n$為止。

第二個方陣：在第一直行中央的方格填入$0$，並且往右下角不斷填入$0$，若超出方陣外，則向上平移$n$格，直到每一直行都有一個方格填入$0$為止，再把所有填入$0$的方格右邊的格子填入$n$（若超出方陣外，則向上平移$n$格），再把所有填入$n$的方格右邊的格子填入$2n$，一直到填入$(n-1)n$為止。

再把兩個方陣中的數相加。

事實上，你可以將這兩個方陣中的每一個相同數字都替換為另一個數字，只要這兩個方陣中原本有出現的$n$個數字都仍然各出現$n$次即可，唯一的條件是第一個方陣中$\frac{n+1}{2}$這個數字，以及第二個方陣中$\frac{(n-1)n}{2}$這個數字，不能被替換。

對於偶數階幻方：

第一個方陣：第一直行由上到下依次填入$1$到$n$，第二直行由下到上依次填入$1$到$n$，第三直行與第二直行相同，第四直行與第一直行相同，若超過四直行，則重複第一到第四直行的步驟。

第二個方陣：第一橫列由上到下依次填入$0$到$n(n-1)$，第二橫列由下到上依次填入$0$到$n(n-1)$，第三橫列與第二橫列相同，第四橫列與第一橫列相同，若超過四橫列，則重複第一到第四橫列的步驟。

此方法暫時只適用於$4k$階的幻方。

事實上，你可以將這兩個方陣中的每一個相同數字都替換為另一個數字，只要這兩個方陣中原本有出現的$n$個數字都仍然各出現$n$次即可，唯一的條件是第一個方陣中每個直行相對的兩個數字之和必須是$n+1$，以及第二個方陣中每個橫列相對的兩個數字之和必須是$n(n-1)$。

如果是$4k+2$階的幻方，就必須在第二個方陣中，檢查每個直行相對的兩個數字之和為$n(n-1)$的格子，對於這些格子，第一個方陣的對應格子。

#### 加邊法

當n為大於等於5的正整數時，此方法可由n-2階幻方外圍加上一圈來構造n階幻方。

以$6$階為例子，先排出$4$階的幻方，如上圖，再將圖中每一個數都加上$8m+2=10$，有下圖：

$\begin{bmatrix} 11 & 25 & 24 & 14 \\ 22 & 16 & 17 & 19 \\ 18 & 20 & 21 & 15 \\ 23 & 13 & 12 & 26 \end{bmatrix}$

在外圍加上一圈格子，把$1,2,3,\dots,8m+2$和$16m^2+8m+3,16m^2+8m+4,\dots,(4m+2)^2$這些數安排在外圈格子內，但要使相對兩數之和等於$16m(m+1)+5$。對於$m=1$這些數是：$1,2,3,4,5,6,7,8,9,10$；$27,28,29,30,31,32,33,34,35,36$。結果如下：

$$\begin{bmatrix} 1 & 9 & 34 & 33 & 32 & 2 \\ 6 & 11 & 25 & 24 & 14 & 31 \\ 10 & 22 & 16 & 17 & 19 & 27 \\ 30 & 18 & 20 & 21 & 15 & 7 \\ 29 & 23 & 13 & 12 & 26 & 8 \\ 35 & 28 & 3 & 4 & 5 & 36 \end{bmatrix}$$

#### 方陣合成法

當n可以分解成兩個大於等於3的正整數a與b的乘積時，此方法可由a階幻方與b階幻方來構造n階幻方。

- 以a(k)表示a階幻方中的每一個數字加上k*a2的結果，則所有的a(k)都是幻方，且a(0)=原本的a階幻方。
- 將b階幻方中的數字k都用幻方a(k-1)取代。

### 編程語言參考實現

#### 四階幻方全解搜索(C/C++)

```C
#include<stdio.h>
int a[17],b[17],m;
void s(int i)
{  /*搜索全部四阶幻方，C代码,运行时间7秒*/
    int n=0,j=0;
    while(++j<17)
        if(!a[j])
        {
            a[b[i]=j]=1;
            switch(i)
            {
                case 1:case 2:case 3:case 5:case 6:case 7:case 9:case 10:s(i+1);break;
                case 11:if(b[6]+b[7]+b[10]+b[11]==34)s(12);break;
                case 4:case 8:case 12:if(b[i-3]+b[i-2]+b[i-1]+b[i]==34)s(i+1);break;
                case 13:if(b[1]+b[5]+b[9]+b[13]==34&&b[4]+b[7]+b[10]+b[13]==34)s(14);break;
                case 14:case 15:if(b[i-12]+b[i-8]+b[i-4]+b[i]==34)s(i+1);break;
                case 16:for(printf("\n"),++m;++n<17;n%4?0:printf("\n"))printf("%2d ",b[n]);
             }
             a[j]=0;
        }
}
int main(void)
{
    s(1);
    printf("四阶幻方总数量:%d(含旋转反射相同)",m);
    return 0;
}
```

#### 奇數階幻方演算法的Java語言實現

```java
/**
* @author: contribute to wikipedia according GNU
* @description:用于创建奇数阶的幻方
*/

public class magic_squre_odd {
       static int[][]  matrix;
       static int   n;
       public static void magic_squre_odd_generate()
       { matrix = new int[n][n];
         //所有的数初始化为0

         matrix[0][(n-1)/2] = 1;
         int x = 0,y = (n-1)/2;

         //count:记住已经插入过的数
          for(int count = 2; count<=n*n;count++)
          while(true)
          {
          //先x-1 y+1
        	  x--;
        	  y++;

        	  //判断是否可以插入
          	  while(true)
                 {//循环判断是否越界，直到一个地方不越界为止
                    //判断是否越界：
                    //越上界x<0，则移到最下方x=x+n，y不变; continue
                   if(x<0)
                   {
                   	x += n;
                   	continue;
                   }

                   //越右界y>=n，则y=y-n，x不变;continue
                   if(y>=n)
                   {
                   	y -= n;
                   	continue;
                   }

        	    //循环判断是否该位置已经有数据，直到找到一个空位
                      //如果有数据，则移到x = x + 2;y = y - 1; continue
                   if (y<0){y+=n;continue;}
                   if(matrix[x][y] != 0 )
                   {
                   	x += 2;y -= 1;
                   	if (x>=n){x-=n;continue;}
                   	if (y<0){y+=n;continue;}
                   	continue;
                   }
                   break;
                 }

                 //将当前的count值赋给选出的空位
                      matrix[x][y]= count;
                      break;
         }
       }

       public static void print()
       {
        	for(int i = 0; i < n; i++)
        	{
        		for(int j = 0; j < n; j++)
        	    {
        			//System.out.println(matrix[i][j]);
        			System.out.print(matrix[i][j]);
        			System.out.print("_");
        	    }
        		System.out.println();
        	}
       }

       public  static void main(String[] args)
       {   //手工输入n的值，并确保为奇数
             n = 11;
           magic_squre_odd_generate();
           print();
       }
}
```

以下是本演算法將n設置為11時得出的11階幻方的構造結果：

```
68 81 94 107 120 1 14 27 40 53 66
80 93 106 119 11 13 26 39 52 65 67
92 105 118 10 12 25 38 51 64 77 79
104 117 9 22 24 37 50 63 76 78 91
116 8 21 23 36 49 62 75 88 90 103
7 20 33 35 48 61 74 87 89 102 115
19 32 34 47 60 73 86 99 101 114 6
31 44 46 59 72 85 98 100 113 5 18
43 45 58 71 84 97 110 112 4 17 30
55 57 70 83 96 109 111 3 16 29 42
56 69 82 95 108 121 2 15 28 41 54
```

#### 4階幻方演算法的Java語言實現

```java
 /**
 * @author: contribute to wikipedia according GNU
 * @description:用于创建4阶的幻方
 *
 */

 public class magic_square_4m {

 	/**
 	 * @param args
 	 */
 	static int  matrix[][];
 	static int   n;

 	static void magic_squre_4m_generate()
 	{
 	  //初始化matrix
 		matrix = new int[n][n];

 	  //将matrix里的位置用数顺序排列
 	  int ini = 0;
 	  for(int i = 0; i < n; i++)
 		  for(int j = 0; j < n; j++)
 			  matrix[i][j] = ++ini;

 	  //输出对调前的样子
 	  System.out.println("对调之前的样子：");
 	  print();

 	  //然后对调（仅对右上方的数进行遍历）
 	  for(int i = 0; i < n; i++)
 	      for(int j = i + 1; j < n; j++)
 	      {
 	    	  if(( i != j) && (i + j) != (n -1) )
 	    	  {   //对不在主付对角线上的数关于中心对调
 	    		  int temp;
 	    		  temp = matrix[i][j];
 	    		  matrix[i][j] = matrix[n -1 - i][n - 1 - j];
 	    		  matrix[n -1 - i][n - 1 - j] = temp;
 	    	  }
 		  }
 	}

 	public static void print()
 	{
 		for(int i = 0; i < n; i++)
 		{
 			for(int j = 0; j < n; j++)
 		    {
 				System.out.print(matrix[i][j]);
 				System.out.print("_");
 		    }
 			System.out.print("\n");
 		}
 	}

 	public static void main(String[] args) {
         //这里手动设置n的数值为4，这里只能设置为4，因为只求4阶幻方
 		n = 4;
 		magic_squre_4m_generate();
 		System.out.println("对调之后的样子：");
 		print();
 	}
 }

```

以下是本演算法輸出的結果：

```
对调之前的样子：
1_2_3_4_
5_6_7_8_
9_10_11_12_
13_14_15_16_
对调之后的样子：
1_15_14_4_
12_6_7_9_
8_10_11_5_
13_3_2_16_
```

## 研究價值

知名華人數學家陳省身曾在數學演講中說幻方只是一個奇蹟，它在數學中沒有引起更普遍深刻的影響，不屬於「好的數學」。

對幻方的學習和研究一直局限於趣味數學本身，更接近數字遊戲或文字遊戲，缺乏與主流數學的聯繫(和璇璣圖在中國詩歌中的地位有一些相似)。數學和物理中也有具有更多學術價值的特殊數字方陣，如推動了試驗設計研究的拉丁方陣和已有應用的阿達瑪矩陣，還有在量子力學中有重要價值的泡利矩陣及其推廣版本蓋爾曼矩陣。魔術方塊則可以與群論建立聯繫(見魔方群)，可以作為抽象代數的入門教具，也是計算群論的研究案例之一，並非單純的幾何玩具。高性能的電腦誕生後，幻方、幻星、素數環(prime ring problem)等很多這類需要滿足特殊規律的填數問題，只要所需的數字規模不大，都可以考慮通過深度優先搜索算法暴力求解和枚舉。

## 藝術與流行文化

- 德國畫家與雕刻家阿爾布雷希特·丟勒曾在一幅名作《憂鬱》(Melencolia I)的角落中畫下一個幻方。這個著名的幻方圖也被知名工程數學軟體MATLAB加入自己的幫助文檔中。