我之前问过一个关于使用 Java 解决八皇后问题的问题。 我得到了一个回溯算法来解决这个问题。
我尝试使用这个算法,但我不知道我的代码有什么问题。它最多只能放置 7 个皇后。
这是皇后类:
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);
}
}
最佳答案
在 Java 中数组是 0-indexed ,这意味着第一项在索引 0 处。您似乎没有完全掌握这个关键事实,这导致您编写的代码中有许多 off-by-one errors。 .
这里有一个问题:
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 queens has been placed
在线查看它:ideone
关于java - 八皇后算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13398945/