幻方（魔方阵）

大家好，欢迎来到IT知识分享网。

幻方（魔方阵）

一、幻方简介

幻方（Magic Square）：将数字安排在正方形格子中，使每行、列和两条对角线上的数字之和都相等的方阵。

二、幻方种类及构造原理

为了方便起见，以下表述中，Magic 代表幻方；N 代表幻方的阶数；(x, y) 代表幻方的行、列编号（注：此编号是针对C语言），例如(1, 3) 表示为幻方的第0行、第2列；(i, j) 为当前已填入的位置。

1.奇数阶幻方

即 N 为奇数。
本例使用罗（萝）伯（卜）法生成奇数幻方：

1. 将 1 放在第一行、中间列，即 (0, N / 2)。
2. 从 2 开始依次按下列规则填入，直至填至 N * N：
   按45°方向（右上）填充，即每一个数存放的行比前一个数的行数减 1 ，列数加 1 。
   • 如果当前位置不在第一行、不在最后一列，则下一个要填入的位置为当前行减一、列加一。
   • 如果当前位置在第一行、在最后一列，则下一个要填入的位置为当前行加一。
   • 如果当前位置在第一行，则下一个要填入的位置的行置为最后一行、列进行加一。
   • 如果当前位置在最后一列，则下一个要填入的位置为当前行减一、列置为第一行。
     （注：上述的每一个条件都依赖上一个条件，例如当条件一、二都不成立时，才会考虑条件三）
     根据以上条件更新当前位置之后，若该当前位置为先前已填入的位置，则需将当前位置的行加二（由于根据上述条件已更新过）、列减一。举例说明：假设进行判断上述条件之前，当前位置为第三行、第一列（位置1），判断完之后，当前位置为第二行、第二列（位置2），但由于该位置（位置2）已填入过元素，则当前位置（位置2）应更新为位置1的行加一、列不变（或者位置2的行加二、列减一）。
     
     

   
   

代码如下：

/ * cols 和 start 是为了针对单偶数阶幻方而额外设置的。 * 1）在该情况下，order 并不为真正的 order（而是 order / 2）； * 2）cols 不一定与 order 相等； * 3）start 也不一定为 1 * * cols: 二维数组 arr 的列数 * start: 填入的起始值 * order: 阶数（不一定为真正的阶数） */ void static _odd_magic_square(int * arr, int cols, int start, int order) { 
      int k = 0; // 已填入的个数 int i, j; // 要填入的二维数组的位置 int idx; // 实际位置（相对于arr的偏移量） i = 0, j = order / 2; // 起始位置 while (1) { 
      idx = two2one(i, j, cols); // if (idx >= order * order) // { 
      // return; // } dref_array(arr, idx) = start + (k++); // start + k, ++k if (k >= order * order) // 填完即退出 { 
      break; } // 计算下一个要填入的位置 if (i != 0 && j != order - 1) // 不在第一行、不在最后一列 { 
      i -= 1, j += 1; } else if (i == 0 && j == order - 1) // 在第一行、在最后一列（也即右上角） { 
      i += 1; } else if (i == 0) // 在第一行 { 
      i = order - 1, j += 1; } else if (j == order - 1) // 在最后一列 { 
      i -= 1, j = 0; } idx = two2one(i, j, cols); #ifdef INIT_VALUE if (dref_array(arr, idx) != INIT_VALUE) // 该位置被填入过 #else if (dref_array(arr, idx) != 0) // 该位置被填入过 #endif { 
      i += 2, j -= 1; } } } / * 奇数阶幻方，即满足 order = 2 * k + 1 * arr: 待处理的二维数组 * order: 幻方阶数 */ void odd_magic_square(int * arr, int order) { 
      _odd_magic_square(arr, order, 1, order); } 

2.双偶数阶幻方

即 N 为 4 的倍数。
本例使用 Spring 法生成双偶幻方：

1. 将 1 至 N * N 的数字按照从左至右、从上至下的顺序依次填入
2. 将幻方分解为一个一个的幻方阶数为4的方阵。
3. 对每一个 4 阶幻方进行中心对称交换。即将两条对角线上的元素按照中心对称的规则，与相应位置的元素交换。此对称中心为原幻方（被分解的幻方）的正中心，并不一定是代表该 4 阶幻方的中心。举例说明：假设幻方阶数为 8 ，当前即要交换的位置为第二行、第三列，则对称位置为第七行、第六列。

代码如下：

/ * 填充4阶幻方 * arr: 待处理的二维数组 * order: arr的幻方阶数，不一定为4 * i: 左上角，相对于在 arr 中的行号 * j: 左上角，相对于在 arr 中的列号 */ static void _magic4(int *arr, int order, int i, int j) { 
      int _i, _j, m; const int diagonal_pos[4][2] = { 
      { 
     0, 0}, { 
     0, 3}, { 
     1, 1}, { 
     1, 2} }; // 4阶幻方的两条对角线的其中四个位置（上半部分） // 根据幻方阵arr的中心，进行对称交换 for (m = 0; m < 4; ++m) { 
      _i = diagonal_pos[m][0] + i; _j = diagonal_pos[m][1] + j; swap_int(arr + two2one(_i, _j, order), arr + two2one(order - 1 - _i, order - 1 - _j, order)); } } / * 双偶数阶幻方，即满足 order = 4 * k * arr: 待处理的二维数组 * order: 幻方阶数 */ void doubly_even_magic_square(int *arr, int order) { 
      int i, j; // 代表每一个 4X4 的二维数组相对于arr的左上角的位置 // 1. 从左至右、从上至下填入 1 ~ order * order for (i = 0; i < order * order; ++i) { 
      dref_array(arr, i) = i + 1; } // 2. 将 orderXorder 分割成一个一个的 4X4 二维数组 for (i = 0; i < order; i += 4) { 
      for (j = 0; j < order; j += 4) { 
      // 3. 处理每一个 4X4 的二维数组 _magic4(arr, order, i, j); } } } 

3.单偶数阶幻方

即 N 为 4 * k + 2（是2的倍数，但不是4的倍数）。因此可以将方阵分成四个区域，每个区域的形状均为 (2 * k + 1) x (2 * k + 1)，即：

本例使用 Strachey 法生成单偶幻方（基于奇数阶幻方）：

1. 将 1 至 N * N 的数字，按照奇数阶幻方的方式，依次填入方阵 A、B、C、D（当前方阵填满则填充下一个方阵）。填充完后，奇数阶幻方 A 包含的数字为 1 至 (2 * m + 1)²，B 包含的数字为 (2 * m + 1)² + 1 至 2 * (2 * m + 1)² ，方阵 C、D 类推。
2. 对于方阵 A、D，将以下位置与 D 中的相对应位置进行交换。
   • 从 A 的正中心位置（包含）开始，从左至右依次选取 k 位置；
   • 方阵 A 的左半部分（不包括中间列），除了中间行之外。
3. 对于方阵 B、C，从 B 的中间列（包括）开始，从右至左依次选取 k – 1 列，与 C 中的相对应位置进行交换。

代码如下：

/ * 单偶数阶幻方，即满足 order = 4 * k + 2 * arr: 待处理的二维数组 * order: 幻方阶数 */ void singly_even_magic_square(int *arr, int order) { 
      int i, j; const int k = order / 4; const int n = order / 2; // 每一个方阵的阶数 const int four_parts_pos[4][2] = { 
      { 
     0, 0}, { 
     n, n}, { 
     0, n}, { 
     n, 0} }; // 分别为方阵A, B, C, D左上角的位置 // 1. 将每一个方阵 按照奇数阶幻方 进行填充 for (i = 0; i < 4; ++i) { 
      // 注意填入的起始值，即 1 + i * n * n _odd_magic_square(arr + two2one(four_parts_pos[i][0], four_parts_pos[i][1], order), order, 1 + i * n * n, n); } // 2. 对称交换 for (i = 0; i < n; ++i) { 
      // 2.1 处理 方阵A 与 方阵D for (j = 0; j < k; ++j) { 
      swap_int(arr + two2one(i, (i != k ? j : j + k), order), arr + two2one(i + n, (i != k ? j : j + k), order)); } // 2.2 处理 方阵B 与 方阵C for (j = k - 1; j > 0; --j) { 
      swap_int(arr + two2one(i, j + n + k - 1, order), arr + two2one(i + n, j + n + k - 1, order)); } } } 

三、完整代码

#include <stdio.h> #include <stdlib.h> #include <string.h> #define PRINT_MAGIC // 幻方阶数 #ifndef ORDER #define ORDER 3 #endif // 幻方初始值 #ifndef INIT_VALUE #define INIT_VALUE -1 #endif // 将二维数组映射为一维数组，例 arr[_row][_col] <-> arr[_row * _ncol + _col] #define two2one(_row, _col, _ncol) ((_row) * (_ncol) + (_col)) // 解引用，例 arr[_offset] <-> *(_arr + _offset) #define dref_array(_arr, _offset) (*((_arr) + (_offset))) void magic(int *arr, int order); void odd_magic_square(int *arr, int order); void doubly_even_magic_square(int *arr, int order); void singly_even_magic_square(int *arr, int order); void print_magic_square(int *arr, int order); int validate_magic_square(int *arr, int order); void swap_int(int *x, int *y); int main(int argc, char *argv[]) { 
       int arr[ORDER][ORDER] = { 
      0}; magic((int *)arr, ORDER); #ifdef PRINT_MAGIC if (!validate_magic_square((int *)arr, ORDER)) { 
       printf("failure!\n\n"); } else { 
       printf("success!\n\n"); } print_magic_square((int *)arr, ORDER); #endif // system("pause"); return 0; } / * 根据 order 动态选择 arr 是哪种类型的幻方 * arr: 待处理的二维数组 * order: 幻方阶数 */ void magic(int *arr, int order) { 
       if (!arr || order < 1) { 
       return; } #ifdef INIT_VALUE memset(arr, INIT_VALUE, sizeof(*arr) * (order * order)); #else memset(arr, 0, sizeof(*arr) * (order * order)); #endif if (order % 2) { 
       odd_magic_square(arr, order); } else if (order % 4) { 
       singly_even_magic_square(arr, order); } else { 
       doubly_even_magic_square(arr, order); } } / * cols 和 start 是为了针对单偶数阶幻方而额外设置的。 * 1）在该情况下，order 并不为真正的 order（而是 order / 2）； * 2）cols 不一定与 order 相等； * 3）start 也不一定为 1 * * cols: 二维数组 arr 的列数 * start: 填入的起始值 * order: 阶数（不一定为真正的阶数） */ void static _odd_magic_square(int * arr, int cols, int start, int order) { 
       int k = 0; // 已填入的个数 int i, j; // 要填入的二维数组的位置 int idx; // 实际位置（相对于arr的偏移量） i = 0, j = order / 2; // 起始位置 while (1) { 
       idx = two2one(i, j, cols); // if (idx >= order * order) // { 
       // return; // } dref_array(arr, idx) = start + (k++); // start + k, ++k if (k >= order * order) // 填完即退出 { 
       break; } // 计算下一个要填入的位置 if (i != 0 && j != order - 1) // 不在第一行、不在最后一列 { 
       i -= 1, j += 1; } else if (i == 0 && j == order - 1) // 在第一行、在最后一列（也即右上角） { 
       i += 1; } else if (i == 0) // 在第一行 { 
       i = order - 1, j += 1; } else if (j == order - 1) // 在最后一列 { 
       i -= 1, j = 0; } idx = two2one(i, j, cols); #ifdef INIT_VALUE if (dref_array(arr, idx) != INIT_VALUE) // 该位置被填入过 #else if (dref_array(arr, idx) != 0) // 该位置被填入过 #endif { 
       i += 2, j -= 1; } } } / * 奇数阶幻方，即满足 order = 2 * k + 1 * arr: 待处理的二维数组 * order: 幻方阶数 */ void odd_magic_square(int * arr, int order) { 
       _odd_magic_square(arr, order, 1, order); } / * 填充4阶幻方 * arr: 待处理的二维数组 * order: arr的幻方阶数，不一定为4 * i: 左上角，相对于在 arr 中的行号 * j: 左上角，相对于在 arr 中的列号 */ static void _magic4(int *arr, int order, int i, int j) { 
       int _i, _j, m; const int diagonal_pos[4][2] = { 
       { 
      0, 0}, { 
      0, 3}, { 
      1, 1}, { 
      1, 2} }; // 4阶幻方的两条对角线的其中四个位置（上半部分） // 根据幻方阵arr的中心，进行对称交换 for (m = 0; m < 4; ++m) { 
       _i = diagonal_pos[m][0] + i; _j = diagonal_pos[m][1] + j; swap_int(arr + two2one(_i, _j, order), arr + two2one(order - 1 - _i, order - 1 - _j, order)); } } / * 双偶数阶幻方，即满足 order = 4 * k * arr: 待处理的二维数组 * order: 幻方阶数 */ void doubly_even_magic_square(int *arr, int order) { 
       int i, j; // 代表每一个 4X4 的二维数组相对于arr的左上角的位置 // 1. 从左至右、从上至下填入 1 ~ order * order for (i = 0; i < order * order; ++i) { 
       dref_array(arr, i) = i + 1; } // 2. 将 orderXorder 分割成一个一个的 4X4 二维数组 for (i = 0; i < order; i += 4) { 
       for (j = 0; j < order; j += 4) { 
       // 3. 处理每一个 4X4 的二维数组 _magic4(arr, order, i, j); } } } / * 单偶数阶幻方，即满足 order = 4 * k + 2 * arr: 待处理的二维数组 * order: 幻方阶数 */ void singly_even_magic_square(int *arr, int order) { 
       int i, j; const int k = order / 4; const int n = order / 2; // 每一个方阵的阶数 const int four_parts_pos[4][2] = { 
       { 
      0, 0}, { 
      n, n}, { 
      0, n}, { 
      n, 0} }; // 分别为方阵A, B, C, D左上角的位置 // 1. 将每一个方阵 按照奇数阶幻方 进行填充 for (i = 0; i < 4; ++i) { 
       // 注意填入的起始值，即 1 + i * n * n _odd_magic_square(arr + two2one(four_parts_pos[i][0], four_parts_pos[i][1], order), order, 1 + i * n * n, n); } // 2. 对称交换 for (i = 0; i < n; ++i) { 
       // 2.1 处理 方阵A 与 方阵D for (j = 0; j < k; ++j) { 
       swap_int(arr + two2one(i, (i != k ? j : j + k), order), arr + two2one(i + n, (i != k ? j : j + k), order)); } // 2.2 处理 方阵B 与 方阵C for (j = k - 1; j > 0; --j) { 
       swap_int(arr + two2one(i, j + n + k - 1, order), arr + two2one(i + n, j + n + k - 1, order)); } } } static int number_of_digits(unsigned int n) { 
       int counts = 0; if (n == 0) { 
       return 1; } while (n > 0) { 
       ++counts; n /= 10; } return counts; } / * 打印arr幻方 */ void print_magic_square(int *arr, int order) { 
       // int i, j; // printf("magic(%d):\n", order); // for (i = 0; i < order; ++i) // { 
       // for (j = 0; j < order; ++j) // { 
       // printf("%3d ", *(arr + two2one(i, j, order))); // } // printf("\n"); // } int i; int counts = number_of_digits(order * order); printf("magic(%d):\n", order); for (i = 0; i < order * order; ++i) { 
       printf(" %-*d ", counts, *(arr + i)); if ((i + 1) % order == 0) { 
       printf("\n"); } } } static void calculate_sum(int *result, int *arr, int rows, int cols, int dim) { 
       int i, j; if (dim == 0) { 
       for (i = 0; i < rows; ++i) { 
       for (j = 0; j < cols; ++j) { 
       dref_array(result, i) = dref_array(arr, two2one(i, j, cols)); } } } else if (dim == 1) { 
       for (i = 0; i < cols; ++i) { 
       for (j = 0; j < rows; ++j) { 
       dref_array(result, i) = dref_array(arr, two2one(j, i, cols)); } } } } / * 验证arr是否为幻方 * arr: 幻方矩阵 * order: 幻方阶数 */ int validate_magic_square(int *arr, int order) { 
       const int M = order * (order * order + 1) / 2; int i, j; int tmp; int sum_of_row, sum_of_col, sum_of_diagonal, sum_of_back_diagonal; int *tmp_arr = NULL; if (!arr || order < 1) { 
       return 0; } tmp_arr = (int *) calloc(order * order, sizeof(*arr)); if (tmp_arr == NULL) { 
       return 0; } sum_of_diagonal = 0; sum_of_back_diagonal = 0; for (i = 0; i < order; ++i) { 
       sum_of_row = 0; sum_of_col = 0; for (j = 0; j < order; ++j) { 
       tmp = dref_array(arr, two2one(i, j, order)); if (dref_array(tmp_arr, tmp)) { 
       goto false_flag; } else { 
       dref_array(tmp_arr, tmp) = 1; } sum_of_row += dref_array(arr, two2one(i, j, order)); sum_of_col += dref_array(arr, two2one(j, i, order)); } if (sum_of_row != M || sum_of_col != M) { 
       goto false_flag; } sum_of_diagonal += dref_array(arr, two2one(i, i, order)); sum_of_back_diagonal += dref_array(arr, two2one(i, order - 1 - i, order)); } if (sum_of_diagonal != M || sum_of_back_diagonal != M) { 
       goto false_flag; } free(tmp_arr); tmp_arr = NULL; return 1; false_flag: free(tmp_arr); tmp_arr = NULL; return 0; } void swap_int(int *x, int *y) { 
       int tmp; tmp = *x; *x = *y; *y = tmp; } 

参考

幻方常规解法汇总