n皇后问题的回溯法java
时间: 2023-12-31 20:23:59 浏览: 26
以下是使用回溯法解决n皇后问题的Java代码示例:
```java
public class NQueens {
private int[] queens; // 皇后所在列的索引
private int n; // 皇后数量
private List<List<String>> solutions; // 存储所有解决方案
public List<List<String>> solveNQueens(int n) {
queens = new int[n];
this.n = n;
solutions = new ArrayList<>();
backtrack(0);
return solutions;
}
private void backtrack(int row) {
if (row == n) {
addSolution();
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 || Math.abs(row - i) == Math.abs(col - queens[i])) {
return false;
}
}
return true;
}
private void addSolution() {
List<String> solution = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
if (queens[i] == j) {
sb.append("Q");
} else {
sb.append(".");
}
}
solution.add(sb.toString());
}
solutions.add(solution);
}
}
```
使用回溯法解决n皇后问题的基本思路是,在每一行放置一个皇后,并检查是否与之前的皇后冲突。如果没有冲突,则继续放置下一行的皇后,直到所有皇后都放置完毕。如果找到一个解决方案,则将其添加到结果列表中。