logo标签列表

八皇后算法

javabacktracking
5

我之前提出了一个关于使用Java解决八皇后问题的问题。

我得到了一个回溯算法来解决这个问题。

我尝试使用这个算法，但是我不知道我的代码有什么问题。它仅能放置7个皇后。

这是Queen类：

    public class Queen {
    //Number of rows or columns
    public static final int BOARD_SIZE = 8;

    boolean[][] board;
    //Indicate an empty square
    public static final boolean EMPTY = false;
    //Indicate a square which containing a queen
    public static final boolean QUEEN = true;
    //Number of moves
    public static final int MOVES = 4;
    //Horizontal moves
    int[] horizontal;
    //Vertical moves
    int[] vertical;

    public int queens = 0;

    public Queen() {
        //Constructor creates an empty board
        board = new boolean[BOARD_SIZE][BOARD_SIZE];
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                board[row][col] = EMPTY;
            }
        }

        horizontal = new int[MOVES];
        vertical = new int[MOVES];
        // up right
        horizontal[0] = -1;
        vertical[0] = 1; 
        // down left
        horizontal[1] = 1;
        vertical[1] = -1;
        // up left
        horizontal[2] = -1;
        vertical[2] = -1;
        // down right
        horizontal[3] = 1;
        vertical[3] = 1;
    }

    public boolean placeQueens (int column) {
        if (column > BOARD_SIZE) {
            return true;
        }
        else {
            boolean queenPlaced = false;
            int row = 1;

            while (!queenPlaced && row < BOARD_SIZE) {
                if (isUnderAttack(row, column)) {
                    ++row;
                }// end if
                else{
                    setQueen(row, column);
                    queenPlaced = placeQueens(column + 1);
                    if (!queenPlaced) {
                        removeQueen(row,column);
                        ++row;
                    }// end if
                }// end else
            }// end while
            return queenPlaced;
        }// end else
    }

    private void removeQueen(int row, int column) {
        board[row][column] = EMPTY;
        System.out.printf("queen REMOVED from [%d][%d]\n", row, column);
    --queens;
    }

    private void setQueen(int row, int column) {
        board[row][column] = QUEEN;
        System.out.printf("queen PLACED in [%d][%d]\n", row, column);
        ++queens;
    }

    public boolean isUnderAttack(int row, int col) {
        boolean condition = false;
        // check row
        for (int column = 0; column < BOARD_SIZE; column++) {
            if ((board[row][column] == true)) {
                condition = true;
            }
        }

        // check column
        for (int row_ = 0; row_ < board.length; row_++) {
            if (board[row_][col] == true) {
                        condition = true;
            }
        }

        // check diagonal
        for (int row_ = row, col_ = col; row_ >= 0 && col_ < 8; row_ += horizontal[0], col_ += vertical[0]) {
            if (board[row_][col_] == true) {
                condition = true;
            }
        }
        for (int row_ = row, col_ = col; row_ < 8 && col_ >= 0; row_ += horizontal[1], col_ += vertical[1]) {
            if (board[row_][col_] == true) {
                condition = true;
            }
        }
        for (int row_ = row, col_ = col; row_ >= 0 && col_ >= 0; row_ += horizontal[2], col_ += vertical[2]) {
            if (board[row_][col_] == true) {
                condition = true;
            }
        }
        for (int row_ = row, col_ = col; row_ < 8 && col_ < 8; row_ += horizontal[3], col_ += vertical[3]) {
            if (board[row_][col_] == true) {
                condition = true;
            }
        }

        return condition;
    }

    public void displayBoard () {
        int counter = 0;
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                if (board[row][col] == true) {
                    System.out.printf("|%s|", "x");
                    counter++;
                }
                else {              
                    System.out.printf("|%s|", "o");
                }
            }
            System.out.println();
        }

        System.out.printf("%d queens has been placed\n", counter);
    }
}
我刚刚在Python中创建了高效的回溯解决方案此处，它可以在几十秒内找到1-8皇后问题的所有解决方案，并且在几分钟内找到9皇后问题的所有解决方案。 - Arty
3个回答
5

在Java中，数组是从0开始计数的，这意味着第一个项目的索引为0。您似乎没有完全掌握这个关键事实，这导致您编写的代码有许多偏移一错误。

问题在这里：

int row = 1;

应该是：

int row = 0;
一个第二个问题在这里：
if (column > BOARD_SIZE) {
    return true;
}

应该是这样的：
if (column >= BOARD_SIZE) {
    return true;
}
您还没有发布您的代码的其余部分，但我敢打赌在调用placeQueens方法时，您的代码中存在第三个错误。如果我了解您的人品，那么您可能会这样做：
queen.placeQueens(1);

但应该是这样的：
queen.placeQueens(0);

所有这些更改后，它按预期工作。最终结果如下：

|x||o||o||o||o||o||o||o|
|o||o||o||o||o||o||x||o|
|o||o||o||o||x||o||o||o|
|o||o||o||o||o||o||o||x|
|o||x||o||o||o||o||o||o|
|o||o||o||x||o||o||o||o|
|o||o||o||o||o||x||o||o|
|o||o||x||o||o||o||o||o|
8皇后已放置

在线查看效果：ideone

3
你做得差不多了。你已经正确地写出了递归算法，这是该问题最难的部分。只需记住使用从0开始的索引即可。 - Mark Byers
0

method isUnderAttack 中有一些硬编码：

// 检查对角线 使用 8 和 BOARD_SIZE 的位置

用法：

col_ < BOARD_SIZE

而不是

col_ < 8

而且最好将 BOARD_SIZE 设定为输入参数而非静态变量，以使代码更通用，并测试 boardSize = 4 或 12。

-1
我编写了通用代码，适用于任意数量的皇后。
结果用0或1表示。 1表示皇后，0表示空方格。
static int[][] setupEightQueens(int queensNum) {
    if (queensNum <= 0)
        return new int[][] { {} };
    int[][] chessField = new int[queensNum][queensNum];
    int n = chessField.length;
    int startJ = 0;
    for (int i = 0; i < n; i++) {
        for (int j = startJ; j < n; j += 2) {
            chessField[j][i] = 1;
            i++;
        }
        i--;
        startJ++;
    }
    return chessField;
}

测试4、8、11皇后问题的输出：

__________________________
皇后数量：4
1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
__________________________
皇后数量：8
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
__________________________
皇后数量：11
1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0

如果 (queensNum <= 0) 这看起来不像是有效的语法。 - CertainPerformance
我已经纠正了它。当n=4时的测试结果是不正确的。这就是为什么我们需要添加一个函数来检查可能与其他皇后相交的情况。 - Arman Melkumyan
仍然不正确 - 请查看您在答案中的代码，它说if (queensNum &lt;= 0)。 - CertainPerformance
请再检查一遍。 - Arman Melkumyan
1
你的4皇后问题的结果显然也是不正确的。 - Turksarama
1
我发现结果4不正确。我需要使用一个函数返回并重新放置皇后在新的位置。但算法的主要目标是通过跳到ntext.next元素来减少遍历列和行数组项的步骤，像这样j+=2，然后立即执行i++以进入下一行，并且当您使用startJ时，它是皇后可能的初始位置。这种方式可以减少遍历的步骤。但是你需要检查isUnderAttack。-如果为真。然后重置并从lastStartColumnInIndex和row = 0开始。 - Arman Melkumyan
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接