1

我一直在尝试编写一个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

4 回答 4

4

直接回答：无需将整个网格推入堆栈，您可能希望将网格表示为 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]);
}

于 2009-07-26T15:02:56.900 回答
0

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

于 2009-07-26T14:56:11.497 回答
0

N = 8 时没有理由达到 2298 的堆栈深度！

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

你的最大筹码量应该是 8。

于 2009-07-26T15:13:51.920 回答
-3

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

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

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

于 2009-07-26T14:46:41.450 回答