每日算法 — 使用java实现九宫格幻方：回溯构造与幻方判定算法

可莉爸爸 AI算法

幻方是一种将数字填入正方形格子中的数学游戏，要求每行、每列以及两条对角线上的数字之和均相等。九宫格幻方（3×3幻方）是最经典的形式，蕴含着深厚的数学美感。本文将用Java实现九宫格幻方的回溯构造算法、快速判定算法，并探讨其唯一性证明。

一、幻方数学原理

1.1 幻和公式

对于 n×n 的幻方，填入 1 到 n² 的不重复整数。所有数字之和为：

S_total = n²(n²+1)/2

由于有 n 行，每行之和（称为幻和）为：

M = S_total / n = n(n²+1)/2

对于九宫格幻方（n=3）：

M = 3×(9+1)/2 = 15

1.2 九宫格幻方的唯一性

3×3幻方使用1~9的数字，幻和为15。通过分析可知：
– 数字5必须位于中心（否则无法满足四条线的幻和要求）
– 偶数必须位于四角，奇数位于四边中点
– 本质上只有一种基本形式，其余为其旋转或镜像

经典九宫格幻方：

8 1 6
3 5 7
4 9 2

二、核心算法设计

2.1 回溯构造算法

对于一般 n×n 幻方，回溯法是通用解法：

  1. 按行优先顺序依次填入数字
  2. 每次填入前检查当前行/列/对角线是否已超出幻和
  3. 若当前部分和已超过幻和，立即剪枝回溯
  4. 全部填满后验证所有约束

剪枝策略：
– 行剪枝：当前行已填数字之和 > 幻和，剪枝
– 列剪枝：当前列已填数字之和 > 幻和，剪枝
– 对角线剪枝：主对角线或副对角线之和 > 幻和，剪枝
– 数字去重：使用位掩码记录已用数字，O(1)查重

2.2 幻方判定算法

给定一个 n×n 矩阵，判定是否为幻方：

  1. 计算第一行之和作为基准幻和 M
  2. 验证其余每行之和是否等于 M
  3. 验证每列之和是否等于 M
  4. 验证主对角线之和是否等于 M
  5. 验证副对角线之和是否等于 M
  6. 验证所有数字是否恰好为 1 到 n² 各出现一次

时间复杂度：O(n²)

2.3 快速生成算法（仅适用于奇数阶）

对于奇数阶幻方，Siamese方法可在 O(n²) 时间内直接构造：

  1. 将1放在第一行中间
  2. 后续数字放在当前位置的右上方
  3. 若右上方已出界或被占用，则放在当前位置的正下方

三、Java完整实现

import java.util.ArrayList;
import java.util.List;

/**
 * 九宫格幻方算法实现
 * 包含回溯构造、幻方判定与Siamese快速生成
 */
public class MagicSquare {

    /**
     * 判定给定矩阵是否为幻方
     * @param matrix n×n矩阵
     * @return true如果是幻方
     */
    public static boolean isMagicSquare(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) return false;

        // 计算幻和（第一行之和）
        int magicSum = 0;
        for (int j = 0; j < n; j++) {
            magicSum += matrix[0][j];
        }

        // 检查每行
        for (int i = 1; i < n; i++) {
            int rowSum = 0;
            for (int j = 0; j < n; j++) {
                rowSum += matrix[i][j];
            }
            if (rowSum != magicSum) return false;
        }

        // 检查每列
        for (int j = 0; j < n; j++) {
            int colSum = 0;
            for (int i = 0; i < n; i++) {
                colSum += matrix[i][j];
            }
            if (colSum != magicSum) return false;
        }

        // 检查主对角线
        int diag1 = 0;
        for (int i = 0; i < n; i++) {
            diag1 += matrix[i][i];
        }
        if (diag1 != magicSum) return false;

        // 检查副对角线
        int diag2 = 0;
        for (int i = 0; i < n; i++) {
            diag2 += matrix[i][n - 1 - i];
        }
        if (diag2 != magicSum) return false;

        // 检查数字是否为1~n²的排列
        boolean[] used = new boolean[n * n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = matrix[i][j];
                if (val < 1 || val > n * n || used[val]) {
                    return false;
                }
                used[val] = true;
            }
        }

        return true;
    }

    /**
     * 回溯法构造n阶幻方
     * @param n 阶数
     * @return 所有解的列表
     */
    public static List<int[][]> constructByBacktrack(int n) {
        List<int[][]> solutions = new ArrayList<>();
        int[][] grid = new int[n][n];
        boolean[] used = new boolean[n * n + 1];
        int magicSum = n * (n * n + 1) / 2;

        backtrack(grid, used, 0, 0, n, magicSum, solutions);
        return solutions;
    }

    /**
     * 回溯递归
     * @param row 当前行
     * @param col 当前列
     */
    private static void backtrack(int[][] grid, boolean[] used,
                                   int row, int col, int n, int magicSum,
                                   List<int[][]> solutions) {
        if (row == n) {
            // 找到一个解
            int[][] copy = new int[n][n];
            for (int i = 0; i < n; i++) {
                System.arraycopy(grid[i], 0, copy[i], 0, n);
            }
            solutions.add(copy);
            return;
        }

        int nextRow = (col == n - 1) ? row + 1 : row;
        int nextCol = (col == n - 1) ? 0 : col + 1;

        for (int num = 1; num <= n * n; num++) {
            if (used[num]) continue;

            // 尝试填入num
            grid[row][col] = num;

            // 剪枝：检查当前行/列/对角线是否超出幻和
            if (!isPartialValid(grid, row, col, n, magicSum)) {
                grid[row][col] = 0;
                continue;
            }

            used[num] = true;
            backtrack(grid, used, nextRow, nextCol, n, magicSum, solutions);
            used[num] = false;
            grid[row][col] = 0;
        }
    }

    /**
     * 部分有效性检查（剪枝）
     */
    private static boolean isPartialValid(int[][] grid, int row, int col,
                                           int n, int magicSum) {
        // 检查当前行（如果该行已填满）
        boolean rowFull = true;
        int rowSum = 0;
        for (int j = 0; j < n; j++) {
            if (grid[row][j] == 0) rowFull = false;
            rowSum += grid[row][j];
        }
        if (rowFull && rowSum != magicSum) return false;
        if (!rowFull && rowSum >= magicSum) return false; // 未填满但已超和

        // 检查当前列（如果该列已填满）
        boolean colFull = true;
        int colSum = 0;
        for (int i = 0; i < n; i++) {
            if (grid[i][col] == 0) colFull = false;
            colSum += grid[i][col];
        }
        if (colFull && colSum != magicSum) return false;
        if (!colFull && colSum >= magicSum) return false;

        // 检查主对角线（仅当在左下-右上对角线上且已填满）
        if (row == col) {
            boolean diagFull = true;
            int diagSum = 0;
            for (int i = 0; i < n; i++) {
                if (grid[i][i] == 0) diagFull = false;
                diagSum += grid[i][i];
            }
            if (diagFull && diagSum != magicSum) return false;
            if (!diagFull && diagSum >= magicSum) return false;
        }

        // 检查副对角线
        if (row + col == n - 1) {
            boolean diagFull = true;
            int diagSum = 0;
            for (int i = 0; i < n; i++) {
                if (grid[i][n - 1 - i] == 0) diagFull = false;
                diagSum += grid[i][n - 1 - i];
            }
            if (diagFull && diagSum != magicSum) return false;
            if (!diagFull && diagSum >= magicSum) return false;
        }

        return true;
    }

    /**
     * Siamese方法快速生成奇数阶幻方
     * 时间复杂度O(n²)
     */
    public static int[][] generateBySiamese(int n) {
        if (n % 2 == 0) {
            throw new IllegalArgumentException("Siamese方法仅适用于奇数阶");
        }

        int[][] grid = new int[n][n];
        int row = 0;
        int col = n / 2;

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

            // 尝试右上方
            int newRow = (row - 1 + n) % n;
            int newCol = (col + 1) % n;

            if (grid[newRow][newCol] != 0) {
                // 已被占用，放在正下方
                row = (row + 1) % n;
            } else {
                row = newRow;
                col = newCol;
            }
        }

        return grid;
    }

    /**
     * 打印矩阵
     */
    static void printMatrix(int[][] matrix) {
        int n = matrix.length;
        int width = String.valueOf(n * n).length();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf("%" + width + "d ", matrix[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        System.out.println("=== 九宫格幻方算法演示 ===\n");

        // 1. 快速生成3阶幻方
        System.out.println("Siamese方法生成3阶幻方：");
        int[][] magic3 = generateBySiamese(3);
        printMatrix(magic3);
        System.out.println("是否为幻方: " + isMagicSquare(magic3));
        System.out.println("幻和: " + (3 * (9 + 1) / 2) + "\n");

        // 2. 快速生成5阶幻方
        System.out.println("Siamese方法生成5阶幻方：");
        int[][] magic5 = generateBySiamese(5);
        printMatrix(magic5);
        System.out.println("是否为幻方: " + isMagicSquare(magic5));
        System.out.println("幻和: " + (5 * (25 + 1) / 2) + "\n");

        // 3. 回溯法求解3阶幻方所有解
        System.out.println("回溯法求解3阶幻方所有基本解：");
        List<int[][]> solutions = constructByBacktrack(3);
        System.out.println("共找到 " + solutions.size() + " 个解");

        // 只打印前3个
        for (int k = 0; k < Math.min(3, solutions.size()); k++) {
            System.out.println("解 " + (k + 1) + ":");
            printMatrix(solutions.get(k));
            System.out.println();
        }

        // 4. 非幻方判定测试
        int[][] notMagic = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println("测试非幻方: " + isMagicSquare(notMagic));
    }
}

四、算法复杂度分析

算法 时间复杂度 空间复杂度 适用场景
幻方判定 O(n²) O(n²) 验证任意矩阵
Siamese生成 O(n²) O(n²) 奇数阶快速构造
回溯构造 O((n²)!) 最坏 O(n²) 寻找所有解
剪枝回溯 远低于阶乘 O(n²) 实际效率极高

对于3阶幻方，回溯法可在毫秒级找到全部8个解（包含旋转和镜像）。

五、数学扩展

  1. 4阶幻方数量：共有7040个基本解，约2.75亿个变体解
  2. 5阶幻方数量：超过2.75亿个基本解
  3. 双偶阶幻方（n=4k）：可用对称交换法构造
  4. 单偶阶幻方（n=4k+2）：构造最为复杂，可用Strachey方法

六、总结

本文实现了九宫格幻方的完整算法体系：

  • 幻方判定算法：O(n²) 时间验证矩阵是否满足幻方约束
  • 回溯构造算法：通过行/列/对角线剪枝高效搜索所有解
  • Siamese快速生成：O(n²) 时间直接构造奇数阶幻方
  • 数学唯一性分析：3阶幻方本质上只有1种基本形式

幻方问题展示了组合数学与搜索算法的完美结合。回溯法的剪枝策略是核心优化手段，将指数级复杂度大幅降低到可接受范围。

Tagged with: