java n皇后问题找出所有解
时间: 2023-08-13 18:13:33 浏览: 45
N 皇后问题是指在 N×N 的棋盘上放置 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) {
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);
} else {
for (int i = 0; i < n; i++) {
if (isValid(row, i)) {
queens[row] = i;
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;
}
}
```
该算法使用回溯法,逐行放置皇后,并检查每个皇后是否与之前的皇后冲突。如果所有皇后都没有冲突,则将解添加到解集中。最后返回所有解。