帮我用JAVA语言解决回溯法求解n皇后问题,给出具体代码,给出具体实现实例展示
时间: 2023-12-31 12:07:14 浏览: 24
好的,下面是用JAVA语言实现回溯法求解n皇后问题的代码:
```java
public class NQueens {
private int[] queens; // 皇后所在的列
private int n; // n皇后问题的规模
public NQueens(int n) {
this.n = n;
queens = new int[n];
}
// 判断当前位置是否能放置皇后
private boolean isSafe(int row, int col) {
for (int i = 0; i < row; i++) {
if (queens[i] == col || queens[i] - i == col - row || queens[i] + i == col + row) {
return false; // 判断列、撇、捺是否有冲突
}
}
return true;
}
// 回溯求解n皇后问题
private boolean backtrack(int row) {
if (row == n) {
return true; // 找到了一组解
}
for (int col = 0; col < n; col++) {
if (isSafe(row, col)) {
queens[row] = col; // 在当前行放置皇后
if (backtrack(row + 1)) {
return true; // 找到了一组解
}
}
}
return false; // 未找到解
}
// 输出解
public void printSolution() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (queens[i] == j) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
NQueens nQueens = new NQueens(8);
if (nQueens.backtrack(0)) {
nQueens.printSolution();
} else {
System.out.println("未找到解");
}
}
}
```
上面的代码实现了回溯求解n皇后问题的功能,其中`isSafe`方法用于判断当前位置是否能放置皇后,`backtrack`方法实现了回溯求解的过程,`printSolution`方法用于输出解。在`main`方法中创建了一个`NQueens`对象,并调用`backtrack`方法求解,如果找到了解,则调用`printSolution`方法输出解,否则输出未找到解。
下面是一个实现实例展示,求解8皇后问题的解:
```
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . . .
. . Q . . . . .
. . . . . . Q .
. . . Q . . . .
```
在这个解中,每一行中只有一个皇后,每一列中也只有一个皇后,而且每一个对角线上也只有一个皇后,满足n皇后问题的要求。