1

ある種のスタッキングと再帰を使用して n クイーン問題を解決する Java クラスを作成しようとしましたが、答えはグリッド (2 次元配列) に格納されますが、再帰のスタック オーバーフローであるデッドウォールにぶつかりました。 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 行未満の 2 つの関数によって解決されます。次のように簡単です。

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

コードを読むと、プログラムがJava再帰ではなくStack<..>を使用しているように見えます。したがって、Javaスタックスペースではなく、Javaヒープスペースが不足している可能性があります。その場合は、-Xmsおよび-Xmxオプションを使用して、初期ヒープサイズと最大ヒープサイズを増やすことができます。

于 2009-07-26T14:56:11.497 に答える
0

N = 8 の場合、スタックの深さが 2298 に達する理由はありません!

正しいアルゴリズムは、それぞれが i 番目のクイーン (列ごとのクイーン) の行位置を表す 8 つの整数の配列によってクイーンを表すことです。

最大スタック サイズは 8 にする必要があります。

于 2009-07-26T15:13:51.920 に答える
-3

Javaでは、コマンド-ssと-ossの両方を使用してスタックサイズを変更できます。 

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

引数は、必要なスタックサイズ（キロバイトまたはメガバイト）です。オーバーフローしなくなるまで、値を増やしてみてください。

于 2009-07-26T14:46:41.450 に答える