java 八皇后问题 递归
时间: 2024-03-17 16:38:50 浏览: 19
Java八皇后问题是一个经典的回溯算法问题,目标是在一个8x8的棋盘上放置8个皇后,使得它们互相之间不能攻击到对方。在这个问题中,皇后可以攻击同一行、同一列以及同一对角线上的其他皇后。
递归是解决八皇后问题的常用方法之一。下面是一个简单的Java代码示例:
```java
public class EightQueens {
private static final int SIZE = 8;
private static int[] queens = new int[SIZE];
public static void main(String[] args) {
solve(0);
}
private static void solve(int row) {
if (row == SIZE) {
printQueens();
return;
}
for (int col = 0; col < SIZE; col++) {
if (isValid(row, col)) {
queens[row] = col;
solve(row + 1);
}
}
}
private static boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
return false;
}
}
return true;
}
private static void printQueens() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (queens[i] == j) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println();
}
System.out.println();
}
}
```
在这段代码中,我们使用一个一维数组`queens`来表示每一行皇后所在的列数。`solve`方法是递归的核心部分,它尝试在当前行的每一列放置皇后,并递归地调用下一行。`isValid`方法用于判断当前位置是否可以放置皇后,它检查同一列、同一对角线上是否已经存在皇后。当放置完最后一行的皇后时,我们就找到了一个解,通过`printQueens`方法打印出棋盘。