クイーンズはスタックを使ってJavaでエクササイズを行います

Question

私はプログラマブルでは新しく、N Queensの問題を解決するこの課題があります。 私のコードに何が間違っているのか分かりません。私はかなりの時間を費やしました。 誰かが私を正しい方向に導いて助けてくれますか？

public static boolean isSafe(int[] col, int size, stack s) 
{  
    int x; 

    for(int i = 1; i<=size; i++) 
    { 
     if(s.get(i)==i || ((s.get(i-1) - s.get(i)) == (col[i-1] - col[i]))) 
      return false; 
    } 

    return true; 
} 

public static void solve(int size, stack s) 
{ 
    int[] column = new int[size]; 
    int x = 0; 

    s.push(0); 
    column[0] = 0; 

    for(int i = 0; i<size; i++) 
    { 
     for(int j = 0; j<size;j++) 
     { 
      if(isSafe(column,size) == true) 
      { 
       s.push(i); 
       column[i] = j; 
      } 
      else 
      { 
       x = s.pop(); 
       if(x+1<size) 
       { 
        column[i] = x+1; 
        s.push(x+1); 
       } 
       else 
       { 
        j=0; 
        column[i] = j; 
        s.push(i+1); 
       } 
      } 
     } 
    } 

    if(s.size() == size) 
     printBoard(column, size); 
} 

スタッククラス、プッシュ、ポップ、大きさを持って、機能を取得する（リターンはint型とプッシュ機能のためのパラメータがint型である）

私はバックトラックとのスタックを使用してそれを解決する必要があり、再帰はありません。

編集：ところで、私はボードが他の印刷された私は何を取得取得し、1に

if(s.size() == size) 
    printBoard(column, size); 

置き換えサイズの変数を変更した場合。

編集： 問題はプッシュとポップですが、アルゴリズムはかなり正しくありません。なぜなら、私はスタック内の要素が1つしかないからです。

Answer 1

2つの迅速な観測私はNクイーン問題に精通していないよ、とコメンターが述べたように、イムないあなたが直面している問題が何であるかを確認しますが、ここでは、次のとおりです。あなたisSafeで

1. （ ）メソッドでは、新しいスタックを初期化します（したがって空になります）。次に、if条件でチェックを実行してコンテンツを決定します。このメソッドは常にtrueを返します。mainメソッドで作成したスタックをこれに？

2. 非常にマイナーな観察が、あなたはいけないブール型の文が「== false」に必要がある場合を行う - （！isSafe（列、サイズは））十分である場合（通知は私が追加偽チェックのために！）

Answer 2

"N Queens"の問題は、8人のクイーンを1人のクイーンが1人も他のクイーンを捕まえることができないようにチェスボードに置かなければならないという "8クイーンズ"問題を思い起こさせます。これは任意の数のクイーンに拡張することができます（チェスボードが適切な大きさである限り）。パズルは再帰によく適しており、しばしば再帰に関する章で教えられます。パズルにはlinkがあります。

あなたはstackを使用できますが、recursionは使用できないとします。再帰は実際にはスタックを使って動作します（明示的に対話することはありません）。つまり、代わりにスタックを使用して再帰関数を記述することができます。このような状況では、スタックを使用して関数パラメータやその他の関連変数を追跡します。より具体的には、新しい再帰関数が呼び出されると、関数内の現在のローカル・データがすべてスタックにプッシュされます。再帰呼び出しを終了した後にデータを取得する必要がある場合、スタックの先頭のデータがポップアウトされ、再度使用されます。

問題を解決するために再帰関数を最初に記述してから、再帰的な解をスタックで反復的に「変換」する方法を理解する方が簡単かもしれません。反復的に解を書くことを試み、バックトラッキングが機能するためにどの情報を追跡する必要があるかを把握することも良い考えです。私はあなたもクイーンズの位置を格納するために1D配列を使用していることに気付いたが、2D配列を先に使ってパズルをよりよく視覚化すると便利かもしれない。これにより、プログラミングもより簡単になります。