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

i've been trying to write a java class to solve the n queens problem using some sort of stacking and recursion, the answers are stored in grids(two dimensionnal arrays), but i've hit a dead wall which is stack overflow for recursion at n=8 (max recursion depth reached 2298) So i've been wondering if there is some way to bypass this dead by doing something complex like allocating more heap space in java(if possible?) or using multi thread(point me out to a tutorial/examples)... or please do advice on how to optimize the code... Thanks in advance

我一直在尝试编写一个java类来解决使用某种堆叠和递归的n皇后问题,答案存储在网格(二维数组)中,但是我已经遇到了一个死墙,它是用于递归的堆栈溢出在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);
    }

4 个解决方案

#1

Direct answer: There's no need to push whole grids onto the stack, and you might want to represent the grid as array of 8 integers denoting the Queen position at each row.

直接回答:没有必要将整个网格推到堆栈上,您可能希望将网格表示为8个整数的数组,表示每行的Queen位置。

Real problem: Your code is too long and too complicated. Keep it simple! The queen's problem is usually solved by 2 functions of <10 lines each. Is is as simple as:

真正的问题:你的代码太长太复杂了。把事情简单化!女王的问题通常由2个函数解决,每个函数<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);
        }
    }
}

Add some output code and a main program, and you're finished!

添加一些输出代码和一个主程序,你就完成了!

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]);
}

#2

Reading the code, it looks like your program is using a Stack<..> and not Java recursion. Therefore it is probably running out of Java heap space rather than Java stack space. If that is the case, you can use the -Xms and -Xmx options to increase the initial and maximum heap sizes.

阅读代码,看起来你的程序正在使用Stack <..>而不是Java递归。因此,它可能耗尽Java堆空间而不是Java堆栈空间。如果是这种情况,您可以使用-Xms和-Xmx选项来增加初始和最大堆大小。

#3

No reason to reach stack depth of 2298 for N = 8!

对于N = 8,没有理由达到2298的堆栈深度!

The correct algorithm is to represent the queens by an array of 8 integers, each representing the row position of the ith queen (queen per column).

正确的算法是用8个整数的数组来表示皇后,每个整数代表第i个皇后(每列皇后)的行位置。

Your max stack size should be 8.

您的最大堆栈大小应为8。

#4

In Java, the commands -ss and -oss can both be used to change the stack size.

在Java中,命令-ss和-oss都可用于更改堆栈大小。

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

The argument is the stack size you would like in kbytes or mbytes. Experiment with some increased values until you don't overflow.

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

#1