1

再帰とバックトラッキングを使用して N-Queens 問題の 1 つの解決策を見つける方法を作成しました。ここでやりたいことは、このメソッドを変更して、考えられるすべてのソリューションを見つけられるようにすることです。すべての解を格納するために 2D 整数配列を使用し、解が見つかるたびにインクリメントするカウンターを追加する必要があると仮定します。しかし、解決策を見つけたらこの方法を継続し、他のすべての可能な解決策を見つけるためにバックトラックを続ける方法について頭を悩ませているようには思えません。私がしなければならないことは、「return true;」を取り除くことだと思います。解決策が見つかったときに発生しますが、解決策が見つかったかどうかをメソッドに再帰的に判断させる方法がわかりません....これが私が今持っている1つの解決策のバージョンです:

public boolean placeQueens(int x, int y) {
    if (!underAttack(x, y)) {
        queen[x] = y;
        board[x][y] = true;
        if (x + 1 == boardSize
                ||placeQueens(x + 1, 0)) {
            return true;
        }
        queen[x] = 0;
        board[x][y] = false;
    }
    if (y + 1 == boardSize) {
        return false;
    }
    return placeQueens(x, y + 1);
}

編集：方法を修正しました。結果は以下のとおりです。まだ面倒かもしれませんが、うまくいきます！見つかった各ソリューションを出力する代わりに、配列に追加しました。私がまだqueen[]変数を持っている理由は、ソリューション配列をボードの状態から独立させることができるようにするためです。そして、私がまだ board[][] 変数を持っている理由は、underAttack() メソッドを (特に勾配の計算で) 書くのがずっと簡単になるからです.... とにかく、皆さんの助けに本当に感謝しています!

public void placeQueen(int x) {
    if (x == N) {            
        for (int i : queen) {
            solution[counter][i] = queen[i];
        }
        counter++;            
        return;
    }
    for (int y = 0; y < N; y++) {
        if (!underAttack(x, y)) {                
            queen[x] = y;
            board[x][y] = true;
            placeQueen(x + 1);
            queen[x] = 0;
            board[x][y] = false;
        }
    }
}
4

2 に答える 2

0

NQueens の疑似コードは次のとおりです。

void Nqueens(int row,int columns[],int n) {

if(row<n) {

for(int col=0;col<n;col++) {

  if(safe(row,col,columns)) {

     columns[i] = k;
     NQueens(row+1,columns);
  }

}



}

else {

   printf("solution: \n");

   for(int i =0;i<n;i++) {

       printf("(%d,%d)\n",i,columns[i]);
   }

}

}
于 2013-11-28T07:11:57.673 に答える