public static void queen(int[] result, int row, int count, int[] column, int[] upLeft, int[] upRight){ if(row == column.length){ count++; System.out.println("第" + count + "个解是" + Arrays.toString(result)); else{ for (int i = 0; i < column.length; i++) { if(column[i] == 0 && upLeft[i-row+7] == 0 && upRight[i+row] == 0){ result[row] = i;column[i] = upLeft[i-row+7] = upRight[i+row] = 1;queen(result,row+1,count,column,upLeft,upRight); column[i] = upLeft[i-row+7] = upRight[i+row] = 0;}}}}这段代码找到了n皇后问题的一个解,该如何优化让它找出其他所有解
时间: 2024-01-29 09:04:42 浏览: 95
对于找出 N 皇后问题的所有解,可以在原来的基础上进行一些修改。首先,需要将 count 从参数列表中移除,并将其作为一个全局变量。其次,需要在找到一个解后,不仅仅输出,而是将其存储在一个解集合中。最后,在回溯过程中,需要遍历所有的可能情况,而不是只找到一个解后就返回。
下面是修改后的代码:
```java
public class NQueens {
private List<List<String>> solutions = new ArrayList<>();
private int count;
public List<List<String>> solveNQueens(int n) {
int[] result = new int[n];
int[] column = new int[n];
int[] upLeft = new int[2 * n - 1];
int[] upRight = new int[2 * n - 1];
count = 0;
queen(result, 0, column, upLeft, upRight);
return solutions;
}
public void queen(int[] result, int row, int[] column, int[] upLeft, int[] upRight) {
if (row == result.length) {
count++;
List<String> solution = new ArrayList<>();
for (int i = 0; i < result.length; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < result.length; j++) {
if (result[i] == j) {
sb.append("Q");
} else {
sb.append(".");
}
}
solution.add(sb.toString());
}
solutions.add(solution);
} else {
for (int i = 0; i < result.length; i++) {
if (column[i] == 0 && upLeft[row + i] == 0 && upRight[row - i + result.length - 1] == 0) {
result[row] = i;
column[i] = upLeft[row + i] = upRight[row - i + result.length - 1] = 1;
queen(result, row + 1, column, upLeft, upRight);
column[i] = upLeft[row + i] = upRight[row - i + result.length - 1] = 0;
}
}
}
}
}
```
在修改后的代码中,我们将解存储在了一个解集合 solutions 中,并且在回溯过程中遍历了所有可能的情况。最后,返回了所有的解。
阅读全文