java优化N Queens代码以避免堆栈溢出

Question

我一直在尝试编写一个java类，使用某种堆栈和递归来解决n queens问题，答案存储在网格（二维数组）中，但我遇到了一个死墙，在n=8时递归的堆栈溢出（最大递归深度达到2298） 因此，我一直在想，是否有某种方法可以通过在java中分配更多堆空间这样的复杂操作（如果可能的话？）或者使用多线程（给我指出一个教程/示例）。。。或者请就如何优化代码提供建议。。。 提前谢谢

    public void resoudre(){

        this.gridPile.push(copyGrid(grid));
        try{
            int row = gridPile.size()-1;
            if(gridPile.size()==0)row = 0;
            chooseGridSpace(this.grid, locateFirstAvailable(grid, row));
            if(gridPile.size() == this.taille){
                gridSolutions.push(copyGrid(grid));
                grid = gridPile.pop();
                boolean erronous = true;
                while(erronous){
                    try{
                        MakeNextUnavailable(grid, gridPile.size());
                        erronous = false;
                    }
                    catch(UnavailabilityException r1){
                        try{
                            grid = gridPile.pop();
                        }
                        catch(java.util.EmptyStackException r2){
                            return;
                        }
                    }
                }
            }

        }
        catch(InvalidPositionException e1){
            this.grid = gridPile.pop();
            boolean error = true;
            while(error){
                try{
                    MakeNextUnavailable(grid, gridPile.size());
                    error = false;
                }
                catch(UnavailabilityException er){
                    try{
                        this.grid = gridPile.pop();
                    }
                    catch(java.util.EmptyStackException err){
                        return;
                    }
                }
            }
        }
        catch(java.lang.ArrayIndexOutOfBoundsException e2){
            return;
        }
        this.resoudre();
    }

    private static void chooseGridSpace(int[][] grid, Position a){
        grid[a.getLigne()][a.getColonne()] = 1;
        fillNotAvailable(grid, a);
    }

Answer 1

在Java中，命令-ss和-oss都可以用来更改堆栈大小

$java -ss156k (native) 
$java -oss600k (Java) 

参数是您想要的堆栈大小，以KB或MB为单位。尝试使用一些增加的值，直到不会溢出为止

Answer 2

读取代码时，程序似乎正在使用堆栈<&燃气轮机；而不是Java递归。因此，它可能耗尽了Java堆空间，而不是Java堆栈空间。如果是这种情况，您可以使用-Xms和-Xmx选项来增加初始堆大小和最大堆大小

Answer 3

直接回答：不需要将整个网格推到堆栈上，您可能希望将网格表示为8个整数的数组，表示每行的皇后位置

真正的问题：您的代码太长太复杂。保持简单！皇后问题通常由<；每行10行。这很简单：

public static boolean isSolution(final int[] board)
{
    for (int i = 0; i < board.length; i++) {
        for (int j = i + 1; j < board.length; j++) {
            if (board[i] == board[j]) return false;     // same column "|"
            if (board[i]-board[j] == i-j) return false; // diagonal "\"
            if (board[i]-board[j] == j-i) return false; // diagonal "/"
        }
    }
    return true;
}

public static void solve(int depth, int[] board)
{
    if (depth == board.length && isSolution(board)) {
        outputSolution(board);
    }
    if (depth < board.length) {  // try all positions of the next row
        for (int i = 0; i < board.length; i++) {
            board[depth] = i;
            solve(depth + 1, board);
        }
    }
}

添加一些输出代码和主程序，就完成了！

public static void outputSolution(final int[] board)
{
    System.out.println("--- Solution ---");
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i]; j++) System.out.print(" ");
        System.out.println("Q");
    }
}

public static void main(String[] args)
{
    int n = 8;
    solve(0, new int[n]);
}

Answer 4

对于N=8，没有理由达到2298的堆叠深度

正确的算法是用8个整数的数组表示皇后，每个整数表示第i个皇后的行位置（每列皇后）

最大堆栈大小应为8