奇數階魔方陣構建演算法與C語言完整實作

什麼是魔方陣？

魔方陣（Magic Square）又稱「縱橫圖」，是一個 n×n 矩陣，填入 1 到 n² 的自然數，每個數字唯一出現一次，且每行、每列、主對角線、副對角線的和皆相等。此常數稱為魔術常數：M = n(n²+1)/2。

奇數階魔方陣構建規律（Siamese Method / 羅馬法）

1. 將 1 放在第一行中間列
2. 後續數字：行減 1、列加 1（右上方向移動）
3. 若行超出上邊界（行 < 0），環繞到最後一行
4. 若列超出右邊界（列 ≥ n），環繞到第 0 列
5. 若目標位置已有數字，或上一數字在右上角（第 0 行、第 n-1 列），則下一數字放在上一數字正下方（行加 1，列不變）

程式設計關鍵點

• 動態二維陣列：使用 malloc 分配指標陣列，再為每行分配空間
• 初始化：memset 將所有元素歸零
• 邊界處理：模運算或條件判斷實現環繞
• 記憶體釋放：先釋放各行，再釋放指標陣列，避免洩漏

完整C語言實作

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void generate_magic_square(int n) {
    // 1. 分配動態二維陣列
    int **square = (int**)malloc(n * sizeof(int*));
    for(int i = 0; i < n; i++) {
        square[i] = (int*)malloc(n * sizeof(int));
        memset(square[i], 0, n * sizeof(int));
    }

    // 2. Siamese Method 填充
    int row = 0;
    int col = n / 2;
    square[row][col] = 1;

    for(int num = 2; num <= n * n; num++) {
        int next_row = (row - 1 + n) % n;  // 向上環繞
        int next_col = (col + 1) % n;      // 向右環繞

        // 衝突檢測：目標位置已佔用，或來自右上角
        if(square[next_row][next_col] != 0) {
            next_row = (row + 1) % n;  // 正下方
            next_col = col;
        }

        row = next_row;
        col = next_col;
        square[row][col] = num;
    }

    // 3. 格式化輸出
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("%5d", square[i][j]);
        }
        printf("\n");
    }

    // 4. 釋放記憶體
    for(int i = 0; i < n; i++) {
        free(square[i]);
        square[i] = NULL;
    }
    free(square);
    square = NULL;
}

int main() {
    int n;
    printf("請輸入奇數階數 (n): ");
    if(scanf("%d", &n) != 1 || n % 2 == 0 || n < 1) {
        printf("錯誤：請輸入正奇數！\n");
        return 1;
    }
    generate_magic_square(n);
    return 0;
}

執行範例：n = 5

   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

驗證：每行/列/對角線和 = 5×(25+1)/2 = 65 ✓

擴展思考

• 雙偶數階 (4k)：可用對稱交換法
• 單偶數階 (4k+2)：較複雜，需分區塊處理
• 廣義魔方陣：允許非連續整數、不同起始值
• 高維魔方陣：魔術立方體、超立方體

總結

奇數階魔方陣構建是經典演算法教學案例，展示了「簡單規則產生複雜結構」的之美。C語言實作中，動態記憶體管理、邊界條件處理、資源釋放規範是關鍵工程實踐點。