0

だから私はn-queens問題を解決しようとしています。私は有効なバックトラッキングの実装を持っていると思いますが、ボードが有効かどうかをチェックする方法がオフになっていると思います (非常に非効率的です) が、その理由はわかりません。誰でもその理由を理解できますか/より良い方法を提供できますか?

/** Given an N x N chess board, find placements for N queens on the board such that
* none of them are attacking another queen (two queens are attacking each other if
* they occupy the same row, column, or diagonal).
* Print out the row, col coordinates for each queen on a separate line, where the
* row and column numbers are separated by a single space. */
static void solveQueens(int n) {
    boolean[][] board = new boolean[n][n];
    board = solveQueens(board, n);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board.length; j++) {
            if (board[i][j]) {
                System.out.printf("%s %s\n", i, j);
            }
        }
    }
}
/** Returns a solved board for the n-queens problem, given an empty board. */
static boolean[][] solveQueens(boolean[][] board, int queensLeft) {
    if (queensLeft == 0) {
        return board;
    }
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board.length; j++) {
            if (board[i][j]) { continue; }
            board[i][j] = true;
            if (isValid(board)) {
                return solveQueens(board, queensLeft - 1);
            } else {
                board[i][j] = false;
            }
        }
    }
    return null;
}
/** True iff BOARD is a valid solution, with no queens attacking each other. */
static boolean isValid(boolean[][] board) {
    boolean occupied = false;
    //Horizontal
    for (int i = 0; i < board.length; i++) {
        for (boolean queen : board[i]) {
            if (queen && occupied) {
                return false;
            }
            if (queen) {
                occupied = true;
            }
        }
        occupied = false;
    }
    //Vertical
    for (int i = 0; i < board.length; i++) {
        for (int j = board.length - 1; j >= 0; j--) {
            boolean queen = board[j][i];
            if (queen && occupied) {
                return false;
            }
            if (queen) {
                occupied = true;
            }
        }
        occupied = false;
    }
    //Diagonals 
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board.length; j++) {
            if (board[i][j]) {
                for (int k = 0; k < board.length; k++) {
                    for (int l = 0; l < board.length; l++) {
                        if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return true;
}
4

1 に答える 1

1

各正方形にクイーンを配置しようとするのは非常に非効率的2^(n*n)ですが ( )、2 番目の関数を変更して、solveQueens各行に多くても 1 つのクイーンを配置することをお勧めします。つまり、より長いsolveQueens関数は行ごとにすべての可能な列を試し、次の行に移動します。

もう 1 つのポイントは、board2 番目の関数の変数がそのsolveQueens場で変更されるため、実際にそれを返す必要がないことです。true代わりに、またはfalse値を返すだけで、解決策があるかどうかを示すことができます。

したがって、最初のsolveQueens関数は次のように変更できます。

static void solveQueens(int n) {
    boolean[][] board = new boolean[n][n];
    // boolean return value from second solveQueens function
    boolean solved = solveQueens(board, n);
    if (solved) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j]) {
                System.out.printf("%s %s\n", i, j);
            }
        }
    } else {
        System.out.printf("No solution for board of size %d\n", n);
    }
}

そして、2 番目の変更されたsolveQueens関数は、各行を再帰的に下に移動し、各行に対してすべての可能な列を試行します。

static boolean solveQueens(boolean[][] board, int row, int n) {
    // we have a queen for each row, done
    if (row >= n) {
        return board;
    }
    // for the current row, try placing a queen at column 0
    // if that fails, try placing a queen at column 1
    // if that fails, try placing a queen at column 2, and so on
    for (int j = 0; j < board.length; j++) {
        board[row][j] = true;
        if (isValid(board)) {
            // placing at (row, j) is valid, try next row
            boolean boardSolved = solveQueens(board, row + 1, n);
            if (boardSolved) {
                // board is solved, yay
                return boardSolved;
            }
        }
        // cannot place queen at (row, j) with current board configuration.
        // set board[row][j] back to false
        board[i][j] = false;
    }
    // tried every column in current row and still cant solve, return false
    return false;
}

関数のこの部分についてisValid:

//Diagonals 
for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board.length; j++) {
        if (board[i][j]) {
            for (int k = 0; k < board.length; k++) {
                for (int l = 0; l < board.length; l++) {
                    if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) {
                        return false;
                    }
                }
            }
        }
    }
}
return true;

の代わりにifを使用する必要があります。元のコードが失敗する例は、、、、(クイーンが行 0 列 3 にあり、2 番目のクイーンが行 3 列 0 にある) であり、これら 2 つのクイーンが互いに対角であるにもかかわらず、最も内側はそれを検出できません。を使用すると、行の距離 ( ) と列の距離 ( ) が絶対値に変換されるため、機能します。(abs(i - k) == abs(j - l))(i - k) == (j - l)i = 0j = 3k = 3l = 0(i - k) == 0 - 3 == -3(j - l) == 3 - 0 == 3ifabs(i - k) == abs(j - l)i - kj - l

したがって、次の行を変更するだけです。

if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) {

に：

if ((abs(i - k) == abs(j - l)) && board[k][l] && !(k == i && l == j)) {

そしてisValid機能は問題ないはずです。

それが役立つことを願っています!

于 2013-12-15T09:24:56.280 に答える