スタックオーバーフローを避けるためにN Queensのコードを最適化する

Question

何らかのスタッキングと再帰を使用してnクイーン問題を解決するためにJavaクラスを作成しようとしていますが、答えはグリッド（2次元配列） （最大再帰の深さは2298に達しました） Javaでより多くのヒープスペースを割り当てるのと同じような複雑な作業をすることによって、この死んだものを回避する方法があるのだろうかと疑問に思っています？可能な場合）またはマルチスレッドを使用して（チュートリアル/例に私を指摘）...またはコードを最適化する方法についてアドバイスをしてください... 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

、コマンド-ssと-ossはbスタックサイズを変更するために使用されます。

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

引数は、kbytesまたはmbytesで表示したいスタックサイズです。オーバーフローしなくなるまで、いくつかの値を増やして試してみてください。

Answer 2

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

Answer 3

ダイレクト答え：グリッド全体をスタックにプッシュする必要はなく、各ローでクイーンの位置を示す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]); 
} 

Answer 4

N = 8のために2298年のスタックの深さに到達する理由はありません！

正しいアルゴリズムは、それぞれがクイーンの第1位（クイーン/列）の行位置を表す8個の整数の配列でクイーンを表現することです。

あなたの最大スタックサイズは8