每日算法 — 使用java实现魔方阵：奇阶幻方构造与双偶阶幻方对角线算法

魔方阵（Magic Square）是一种将连续自然数填入正方形格子中，使每行、每列及两条对角线之和均相等的经典数学结构。本文用Java实现奇阶幻方的Siamese方法与双偶阶幻方的对角线交换法，讲解两种构造算法的数学原理与代码实现。

数学原理

奇阶幻方：Siamese方法（暹罗法）

对于n×n的奇阶幻方（n为奇数），将数字1放在第一行中间列。后续数字按”右上”方向填充：
– 若超出上边界，则移动到最下行；
– 若超出右边界，则移动到最左列；
– 若目标位置已有数字，或同时超出上右边界，则向下移动一格。

双偶阶幻方：对角线交换法

对于n=4k的幻方（如4阶、8阶），先按顺序填入1到n²的数字，然后对主对角线和副对角线上的数字，用n²+1−当前数进行替换。

完整Java实现

import java.util.Arrays;

/**
 * 魔方阵生成器
 * 支持：奇阶幻方(Siamese法)、双偶阶幻方(对角线交换法)
 */
public class MagicSquare {

    private final int n;
    private final int[][] grid;
    private final int magicSum; // 幻和 = n*(n*n+1)/2

    public MagicSquare(int n) {
        if (n < 3) {
            throw new IllegalArgumentException("幻方阶数必须大于等于3");
        }
        this.n = n;
        this.grid = new int[n][n];
        this.magicSum = n * (n * n + 1) / 2;
    }

    // ==================== 奇阶幻方：Siamese方法 ====================
    public void generateOdd() {
        if (n % 2 == 0) {
            throw new IllegalStateException("Siamese方法仅适用于奇阶");
        }

        int row = 0;
        int col = n / 2; // 第一行中间列

        for (int num = 1; num <= n * n; num++) {
            grid[row][col] = num;

            // 计算下一个位置：右上
            int nextRow = (row - 1 + n) % n; // 上边界环绕
            int nextCol = (col + 1) % n;     // 右边界环绕

            // 如果右上已有数字，则向下
            if (grid[nextRow][nextCol] != 0) {
                nextRow = (row + 1) % n;
                nextCol = col;
            }

            row = nextRow;
            col = nextCol;
        }
    }

    // ==================== 双偶阶幻方：对角线交换法 ====================
    public void generateDoublyEven() {
        if (n % 4 != 0) {
            throw new IllegalStateException("对角线交换法仅适用于4k阶");
        }

        // 第一步：顺序填充
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = i * n + j + 1;
            }
        }

        // 第二步：对主对角线和副对角线上的数字进行替换
        // 每个n/4×n/4的子矩阵对角线都要处理
        int subSize = n / 4;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 判断当前位置是否在对角线区域
                boolean onDiag = isOnDiagonalBlock(i, j, subSize);
                if (onDiag) {
                    grid[i][j] = n * n + 1 - grid[i][j];
                }
            }
        }
    }

    /**
     * 判断位置(i,j)是否位于需要交换的对角线块上
     * 双偶阶幻方有4个n/4×n/4的子矩阵位于主/副对角线上需要交换
     */
    private boolean isOnDiagonalBlock(int i, int j, int subSize) {
        // 将矩阵分为n/4 × n/4的子块，判断是否在"对角线子块"上
        int blockRow = i / subSize;
        int blockCol = j / subSize;
        int blocks = n / subSize; // = 4

        // 主对角线子块 (0,0), (1,1), (2,2), (3,3)
        // 副对角线子块 (0,3), (1,2), (2,1), (3,0)
        return blockRow == blockCol || blockRow + blockCol == blocks - 1;
    }

    // ==================== 单偶阶幻方：Strachey方法（n=4k+2） ====================
    public void generateSinglyEven() {
        if (n % 2 != 0 || n % 4 == 0) {
            throw new IllegalStateException("Strachey方法仅适用于单偶阶(4k+2)");
        }

        int half = n / 2;
        // 先构造4个奇阶幻方子方阵
        int[][][] subSquares = new int[4][half][half];

        // 用Siamese方法生成half阶幻方
        MagicSquare base = new MagicSquare(half);
        base.generateOdd();
        int[][] baseGrid = base.getGrid();

        // 填充四个子方阵，分别加上不同的偏移量
        // A(左上): +0, B(右上): +2*half*half, C(左下): +3*half*half, D(右下): +half*half
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                subSquares[0][i][j] = baseGrid[i][j];               // A
                subSquares[1][i][j] = baseGrid[i][j] + 2 * half * half; // B
                subSquares[2][i][j] = baseGrid[i][j] + 3 * half * half; // C
                subSquares[3][i][j] = baseGrid[i][j] + half * half;     // D
            }
        }

        // 按特定规则交换子方阵中的列
        int k = (n - 2) / 4;

        // 将A和D的前k列交换
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < k; j++) {
                int temp = subSquares[0][i][j];
                subSquares[0][i][j] = subSquares[3][i][j];
                subSquares[3][i][j] = temp;
            }
        }

        // 将A和D的中间一列（第k列）的部分元素交换
        // 交换A的第k列中从第k行到half-1行，与D对应位置
        for (int i = k; i < half; i++) {
            int temp = subSquares[0][i][k];
            subSquares[0][i][k] = subSquares[3][i][k];
            subSquares[3][i][k] = temp;
        }

        // 将B和C的最后k-1列交换
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < k - 1; j++) {
                int temp = subSquares[1][i][half - 1 - j];
                subSquares[1][i][half - 1 - j] = subSquares[2][i][half - 1 - j];
                subSquares[2][i][half - 1 - j] = temp;
            }
        }

        // 组装最终矩阵
        for (int i = 0; i < half; i++) {
            System.arraycopy(subSquares[0][i], 0, grid[i], 0, half);
            System.arraycopy(subSquares[1][i], 0, grid[i], half, half);
        }
        for (int i = 0; i < half; i++) {
            System.arraycopy(subSquares[2][i], 0, grid[i + half], 0, half);
            System.arraycopy(subSquares[3][i], 0, grid[i + half], half, half);
        }
    }

    // ==================== 通用生成入口 ====================
    public void generate() {
        if (n % 2 == 1) {
            generateOdd();
        } else if (n % 4 == 0) {
            generateDoublyEven();
        } else {
            generateSinglyEven();
        }
    }

    // ==================== 验证函数 ====================
    public boolean verify() {
        // 检查行和
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) sum += grid[i][j];
            if (sum != magicSum) return false;
        }
        // 检查列和
        for (int j = 0; j < n; j++) {
            int sum = 0;
            for (int i = 0; i < n; i++) sum += grid[i][j];
            if (sum != magicSum) return false;
        }
        // 检查主对角线
        int diag1 = 0, diag2 = 0;
        for (int i = 0; i < n; i++) {
            diag1 += grid[i][i];
            diag2 += grid[i][n - 1 - i];
        }
        return diag1 == magicSum && diag2 == magicSum;
    }

    // ==================== 输出 ====================
    public void printGrid() {
        int maxDigits = String.valueOf(n * n).length();
        String fmt = "%" + maxDigits + "d ";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf(fmt, grid[i][j]);
            }
            System.out.println();
        }
    }

    public int[][] getGrid() {
        int[][] copy = new int[n][n];
        for (int i = 0; i < n; i++) {
            copy[i] = Arrays.copyOf(grid[i], n);
        }
        return copy;
    }

    public int getMagicSum() {
        return magicSum;
    }

    // ==================== 主程序 ====================
    public static void main(String[] args) {
        System.out.println("=== 3阶奇阶幻方 ===");
        MagicSquare ms3 = new MagicSquare(3);
        ms3.generateOdd();
        ms3.printGrid();
        System.out.println("幻和 = " + ms3.getMagicSum());
        System.out.println("验证 = " + ms3.verify());

        System.out.println("\n=== 4阶双偶阶幻方 ===");
        MagicSquare ms4 = new MagicSquare(4);
        ms4.generateDoublyEven();
        ms4.printGrid();
        System.out.println("幻和 = " + ms4.getMagicSum());
        System.out.println("验证 = " + ms4.verify());

        System.out.println("\n=== 6阶单偶阶幻方 ===");
        MagicSquare ms6 = new MagicSquare(6);
        ms6.generateSinglyEven();
        ms6.printGrid();
        System.out.println("幻和 = " + ms6.getMagicSum());
        System.out.println("验证 = " + ms6.verify());

        System.out.println("\n=== 5阶奇阶幻方（通用入口） ===");
        MagicSquare ms5 = new MagicSquare(5);
        ms5.generate();
        ms5.printGrid();
        System.out.println("幻和 = " + ms5.getMagicSum());
        System.out.println("验证 = " + ms5.verify());
    }
}

算法复杂度分析

三种方法均只需线性扫描整个n²矩阵，无嵌套循环外的额外开销。对于n=1000的幻方，生成时间仅需毫秒级。

数学趣味延伸

• 幻和公式：对于n阶幻方，幻和恒为n(n²+1)/2。3阶幻和为15，4阶为34，5阶为65。
• 唯一性：3阶幻方在旋转和翻转意义下只有一个；4阶幻方则有7040个。
• 泛对角线幻方：若折断对角线（wrap-around）之和也等于幻和，则称为”泛幻方”，仅单偶阶不存在。

魔方阵是组合数学的瑰宝，从古代洛书到现代密码学都有应用。通过Java实现三种经典构造法，读者可以深入理解其代数结构，并探索更高阶的变体如乘法幻方、高维幻方。