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

以下是一个简单的分治法搜索幻方所有解的 Java 代码：

public class MagicSquareFinder {
    private int n;
    private int[][] magicSquare;
    
    public MagicSquareFinder(int n) {
        this.n = n;
        magicSquare = new int[n][n];
    }
    
    public void findMagicSquares() {
        int[] unusedNumbers = new int[n*n];
        for (int i = 0; i < n*n; i++) {
            unusedNumbers[i] = i+1;
        }
        findMagicSquaresHelper(0, 0, unusedNumbers);
    }
    
    private void findMagicSquaresHelper(int row, int col, int[] unusedNumbers) {
        if (row == n) {
            if (isMagicSquare()) {
                printMagicSquare();
            }
        } else {
            for (int i = 0; i < unusedNumbers.length; i++) {
                magicSquare[row][col] = unusedNumbers[i];
                if (isValidPartialSolution(row, col)) {
                    int[] newUnusedNumbers = removeNumber(unusedNumbers, unusedNumbers[i]);
                    if (col == n-1) {
                        findMagicSquaresHelper(row+1, 0, newUnusedNumbers);
                    } else {
                        findMagicSquaresHelper(row, col+1, newUnusedNumbers);
                    }
                }
            }
        }
    }
    
    private boolean isMagicSquare() {
        int magicSum = n*(n*n+1)/2;
        for (int i = 0; i < n; i++) {
            int rowSum = 0;
            int colSum = 0;
            for (int j = 0; j < n; j++) {
                rowSum += magicSquare[i][j];
                colSum += magicSquare[j][i];
            }
            if (rowSum != magicSum || colSum != magicSum) {
                return false;
            }
        }
        int diag1Sum = 0;
        int diag2Sum = 0;
        for (int i = 0; i < n; i++) {
            diag1Sum += magicSquare[i][i];
            diag2Sum += magicSquare[i][n-i-1];
        }
        if (diag1Sum != magicSum || diag2Sum != magicSum) {
            return false;
        }
        return true;
    }
    
    private boolean isValidPartialSolution(int row, int col) {
        int magicSum = n*(n*n+1)/2;
        if (col == n-1) {
            int rowSum = 0;
            for (int i = 0; i < n; i++) {
                rowSum += magicSquare[row][i];
            }
            if (rowSum != magicSum) {
                return false;
            }
        }
        if (row == n-1) {
            int colSum = 0;
            for (int i = 0; i < n; i++) {
                colSum += magicSquare[i][col];
            }
            if (colSum != magicSum) {
                return false;
            }
        }
        if (row == col) {
            int diag1Sum = 0;
            for (int i = 0; i < n; i++) {
                diag1Sum += magicSquare[i][i];
            }
            if (diag1Sum + unusedSum(row, col) < magicSum) {
                return false;
            }
        }
        if (row == n-col-1) {
            int diag2Sum = 0;
            for (int i = 0; i < n; i++) {
                diag2Sum += magicSquare[i][n-i-1];
            }
            if (diag2Sum + unusedSum(row, col) < magicSum) {
                return false;
            }
        }
        return true;
    }
    
    private int unusedSum(int row, int col) {
        int sum = 0;
        for (int i = 0; i < n*n; i++) {
            int num = i+1;
            boolean used = false;
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (magicSquare[r][c] == num) {
                        used = true;
                        break;
                    }
                }
            }
            if (!used) {
                if (row == n-1 || col == n-1 || row == col || row == n-col-1) {
                    sum += num;
                }
            }
        }
        return sum;
    }
    
    private int[] removeNumber(int[] arr, int num) {
        int[] newArr = new int[arr.length-1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != num) {
                newArr[index++] = arr[i];
            }
        }
        return newArr;
    }
    
    private void printMagicSquare() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(magicSquare[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

这个代码使用递归来搜索幻方的所有解。它的基本思想是在每个格子中填充一个数字，然后检查当前的局部解是否有效。如果是有效的，就继续搜索下一个格子。如果到达了最后一个格子，并且当前的解是幻方，就输出这个解。

为了检查当前的局部解是否有效，我们需要检查当前行、当前列、当前对角线等是否满足幻方的要求。我们还需要计算未使用数字的和，以便判断是否有可能形成幻方。

这个代码可能不是最优的，但它是比较容易理解的，并且可以找到所有幻方的解。