n-ферзей, проверка допустимой доски

Итак, я пытаюсь решить проблему с n ферзями. Я думаю, что у меня есть правильная реализация обратного отслеживания, но я думаю, что мой метод проверки правильности доски отключен (а также крайне неэффективен), но я не понимаю, почему. Может ли кто-нибудь понять, почему / предложить лучший метод?

/** 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;
}

backtracking n-queens
person BrandonM    schedule 15.12.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вместо того, чтобы пытаться разместить ферзя на каждом поле, что очень неэффективно (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, и даже если эти 2 ферзя расположены по диагонали друг к другу, самый внутренний if не сможет его обнаружить. Использование abs(i - k) == abs(j - l) превратит расстояние между строками (i - k) и расстоянием между столбцами (j - l) в абсолютные значения и, следовательно, будет работать.

Так что просто измените эту строку:

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

to:

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

и функция isValid должна быть в порядке.

Надеюсь, это поможет!

person yanhan    schedule 15.12.2013
comment
Да, это исправлено! Большое спасибо! - person BrandonM; 15.12.2013