java 八皇后算法

Eight Queens Algorithm

提问by Kareem

I've asked earlier a question about solving the eight queens problem using Java. I got a backtracking algorithm to solve the problem.

我之前问过一个关于使用 Java 解决八皇后问题的问题。我得到了一个回溯算法来解决这个问题。

I tried to use this algorithm but I don't know what's wrong with my code. It places up to 7 queens only.

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

Here's Queen Class:

这里是女王级：

    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);
    }
}

采纳答案by Mark Byers

In Java arrays are 0-indexed, meaning that the first item is at index 0. You seem to have not entirely grasped this crucial fact, which has resulted in you writing code with many off-by-one errors.

在 Java 中，数组是0-indexed，这意味着第一项在索引 0 处。您似乎还没有完全掌握这个关键事实，这导致您编写的代码有很多错一错误。

One problem is here:

一个问题在这里：

int row = 1;

It should be:

它应该是：

int row = 0;

---

---

A second problem is here:

第二个问题在这里：

if (column > BOARD_SIZE) {
    return true;
}

It should be this:

应该是这样的：

if (column >= BOARD_SIZE) {
    return true;
}

---

---

You haven't posted the rest of your code, but I'm willing to bet that there is a third error in your code when you call the placeQueensmethod. If I know what sort of person you are, then you probably did this:

您尚未发布其余代码，但我敢打赌，当您调用该placeQueens方法时，您的代码中存在第三个错误。如果我知道你是什么样的人，那么你可能是这样做的：

queen.placeQueens(1);

But it should be this:

但应该是这样的：

queen.placeQueens(0);

---

---

With all these changes it works as expected. The final result is:

通过所有这些更改，它可以按预期工作。最终结果是：

|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 queens has been placed

See it working online: ideone

查看它在线工作：ideone

回答by Arman Melkumyan

There are some hardcodes in the method isUnderAttack :

isUnderAttack 方法中有一些硬编码：

// check diagonal the place the usage of 8 with the BOARD_SIZE

// 用BOARD_SIZE检查对角线8的用法

use:

利用：

col_ < BOARD_SIZE   

instead of

代替

col_ < 8

and it could be better to make the BOARD_SIZE not static but make it as an input parameter, to make the code as more generic and do test for the boardSize = 4 or 12

最好使 BOARD_SIZE 不是静态的而是将其作为输入参数，以使代码更通用并测试 boardSize = 4 或 12

回答by Arman Melkumyan

I wrote a generic code, which is working for any count of Queens.

我写了一个通用代码，它适用于任何数量的皇后区。

The result is represented in 0 or 1. The 1 is a Queen, 0 - is empty square.

结果以 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;
}

output for the tested 4, 8, 11 count of queens:

__________________________
queens: 4
1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
__________________________
queens: 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
__________________________
queens: 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

测试的 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 1
__________________________
皇后：11
1 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 1 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

---

---