采用Java语言,编写关于回溯法解决n皇后问题的完整代码
时间: 2023-06-27 17:05:10 浏览: 81
N_queen.zip_n queen问题_queen
下面是Java语言编写的回溯法解决n皇后问题的完整代码:
```java
public class NQueens {
private int[] queens; // 存放皇后的位置
private int n; // 皇后个数
private int count; // 解的个数
public int solve(int n) {
this.n = n;
queens = new int[n];
count = 0;
backtrack(0);
return count;
}
private void backtrack(int row) {
if (row == n) { // 找到一组解
count++;
return;
}
for (int col = 0; col < n; col++) { // 遍历每一列
if (isValid(row, col)) { // 如果该位置可以放置皇后
queens[row] = col;
backtrack(row + 1); // 继续放下一行皇后
}
}
}
private boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) { // 遍历已放置的皇后
if (queens[i] == col || // 同一列
i - queens[i] == row - col || // 左上到右下的对角线
i + queens[i] == row + col) { // 左下到右上的对角线
return false;
}
}
return true;
}
}
```
使用方法:
```java
NQueens nQueens = new NQueens();
int count = nQueens.solve(8); // 求解8皇后问题的解的个数
System.out.println(count); // 输出92
```
阅读全文