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))，您可能需要修改第二个solveQueens函数以尝试为每行最多放置一个皇后。换句话说，较长的solveQueens函数将尝试每行的所有可能列，然后继续下一行。

还有一点是，board第二个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);
    }
}

第二个修改后的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，你将不得不使用(abs(i - k) == abs(j - l))代替(i - k) == (j - l)。原始代码将失败的一个例子是当i = 0, j = 3, k = 3, l = 0（一个皇后在第 0 行第 3 列，第二个皇后在第 3 行第 0 列），所以(i - k) == 0 - 3 == -3和(j - l) == 3 - 0 == 3，即使这两个皇后彼此对角线，最里面的if将无法检测到它。使用abs(i - k) == abs(j - l)会将行距离 ( i - k) 和列距离 ( j - 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 回答