递归算法求解八皇后问题
时间: 2023-11-08 14:04:00 浏览: 27
下面是基于Java语言的递归算法求解八皇后问题的代码实现:
```java
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
boolean[] col = new boolean[n];
boolean[] diagonal = new boolean[2*n-1];
boolean[] anti_diagonal = new boolean[2*n-1];
List<String> cur = new ArrayList<>();
queens(n, 0, col, diagonal, anti_diagonal, cur, res);
return res;
}
private void queens(int n, int row, boolean[] col, boolean[] diagonal, boolean[] anti_diagonal, List<String> cur, List<List<String>> res) {
if (row == n) {
res.add(new ArrayList<>(cur));
return;
}
for (int j = 0; j < n; j++) {
if (col[j] || diagonal[row+j] || anti_diagonal[row-j+n-1]) {
continue;
}
char[] cur_row = new char[n];
Arrays.fill(cur_row, '.');
cur_row[j] = 'Q';
cur.add(new String(cur_row));
col[j] = true;
diagonal[row+j] = true;
anti_diagonal[row-j+n-1] = true;
queens(n, row+1, col, diagonal, anti_diagonal, cur, res);
cur.remove(cur.size()-1);
col[j] = false;
diagonal[row+j] = false;
anti_diagonal[row-j+n-1] = false;
}
}
}
```
这里的 `queens` 函数用于递归求解八皇后问题,`solveNQueens` 函数用于返回所有的解决方案。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)