分治法搜索幻方所有解Java代码及解析

以下是分治法搜索幻方所有解Java代码及解析：

public class MagicSquare {
    
    private int[][] magicSquare; // 幻方矩阵
    private int n; // 矩阵大小
    private int count; // 解的个数

    // 构造函数
    public MagicSquare(int n) {
        this.n = n;
        this.magicSquare = new int[n][n];
        this.count = 0;
    }

    // 判断当前矩阵是否为幻方
    private boolean isMagicSquare() {
        int sum = 0;
        // 判断行
        for (int i = 0; i < n; i++) {
            sum += magicSquare[0][i];
        }
        for (int i = 1; i < n; i++) {
            int tempSum = 0;
            for (int j = 0; j < n; j++) {
                tempSum += magicSquare[i][j];
            }
            if (tempSum != sum) {
                return false;
            }
        }
        // 判断列
        for (int i = 0; i < n; i++) {
            int tempSum = 0;
            for (int j = 0; j < n; j++) {
                tempSum += magicSquare[j][i];
            }
            if (tempSum != sum) {
                return false;
            }
        }
        // 判断对角线
        int tempSum = 0;
        for (int i = 0; i < n; i++) {
            tempSum += magicSquare[i][i];
        }
        if (tempSum != sum) {
            return false;
        }
        tempSum = 0;
        for (int i = 0; i < n; i++) {
            tempSum += magicSquare[i][n - i - 1];
        }
        if (tempSum != sum) {
            return false;
        }
        return true;
    }

    // 分治法搜索所有解
    public void findAllSolutions() {
        divideAndConquer(0, 0, n - 1, n - 1);
    }

    // 分治法递归函数
    private void divideAndConquer(int startX, int startY, int endX, int endY) {
        if (startX > endX || startY > endY) {
            return;
        }
        if (startX == endX && startY == endY) {
            magicSquare[startX][startY] = 1;
            if (isMagicSquare()) {
                printMagicSquare();
                count++;
            }
            return;
        }
        int midX = (startX + endX) / 2;
        int midY = (startY + endY) / 2;
        // 左上角
        divideAndConquer(startX, startY, midX, midY);
        // 右上角
        divideAndConquer(startX, midY + 1, midX, endY);
        // 左下角
        divideAndConquer(midX + 1, startY, endX, midY);
        // 右下角
        divideAndConquer(midX + 1, midY + 1, endX, endY);
    }

    // 输出幻方矩阵
    private void printMagicSquare() {
        System.out.println("Solution " + (count + 1) + ":");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(magicSquare[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        MagicSquare ms = new MagicSquare(3);
        ms.findAllSolutions();
    }

}

上面的代码使用了分治法来搜索幻方矩阵的所有解。主要思路是将幻方矩阵分成四个子矩阵，递归地求解子矩阵，然后将其合并成一个完整的幻方矩阵。在递归过程中，当子矩阵大小为1时，将其填充为1，并判断是否为幻方矩阵。如果是，则输出解。

在判断幻方矩阵的过程中，使用了一个sum变量来记录每行、每列、每条对角线的和，然后逐个判断它们是否相等，以确定是否为幻方矩阵。

在main函数中，我们创建了一个3阶幻方矩阵的实例，并调用了findAllSolutions方法来搜索所有解。