使用Java算法解决八皇后问题,并且使用二维数组
时间: 2024-01-14 21:02:49 浏览: 127
JAVA解决八皇后算法
八皇后问题是指在一个8x8的棋盘上放置8个皇后,使得每个皇后都不会同时攻击到其他皇后。其中,攻击包括在同一行、同一列或同一对角线上。这是一个经典的回溯算法问题,可以使用二维数组来实现。
首先,我们创建一个8x8的二维数组来表示棋盘,用数字1表示皇后的位置,数字0表示空格。然后,从第一行开始,逐行放置皇后,直到所有皇后都放置完毕或无法放置。如果当前行不能放置皇后,则回溯到上一行,重新尝试放置皇后。
以下是Java代码实现:
```java
public class EightQueens {
private static final int SIZE = 8;
private int[][] board = new int[SIZE][SIZE];
// 检查当前位置是否可以放置皇后
private boolean isSafe(int row, int col) {
int i, j;
// 检查列
for (i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}
// 检查左上角对角线
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
// 检查右上角对角线
for (i = row, j = col; i >= 0 && j < SIZE; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}
return true;
}
// 递归放置皇后
private boolean solve(int row) {
if (row == SIZE) {
return true; // 所有皇后都已放置
}
for (int col = 0; col < SIZE; col++) {
if (isSafe(row, col)) {
board[row][col] = 1; // 放置皇后
// 递归放置下一行的皇后
if (solve(row + 1)) {
return true;
}
board[row][col] = 0; // 回溯
}
}
return false; // 无法放置皇后
}
// 打印棋盘
private void printBoard() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
EightQueens eq = new EightQueens();
if (eq.solve(0)) {
eq.printBoard();
} else {
System.out.println("无解");
}
}
}
```
在以上代码中,`isSafe()`函数用来检查当前位置是否可以放置皇后,`solve()`函数用来递归放置皇后,`printBoard()`函数用来打印棋盘。在`main()`函数中,我们创建`EightQueens`对象并调用`solve()`函数来解决八皇后问题,如果有解,则调用`printBoard()`函数打印结果。
阅读全文