N皇后问题递归解法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了N皇后问题递归解法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1632字,纯文字阅读大概需要3分钟。
内容图文
![N皇后问题递归解法](/upload/InfoBanner/zyjiaocheng/1023/822d334955c248509d0861b6d23c2f2b.jpg)
N 皇后问题 递归解法
参考B站小甲鱼数据结构与算法视频
代码中有详细注释
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
// 初始化一个棋盘
char[][] chess = new char[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
chess[i][j] = '.';
// 从第0行开始,递归搜索每一行可以放皇后的位置(0 --> n-1)
NQueens(n, chess, 0, result);
return result;
}
private void NQueens(int n, char[][] chess, int row, List<List<String>> result) {
// 需要一个临时棋盘
char[][] tempChess = new char[n][n];
// 初始化临时棋盘
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
tempChess[i][j] = chess[i][j];
// 递归出口
if (row == n) { // 所有行都搜索完了(0 --> n-1)
List<String> temp = new ArrayList<>();
for (char[] line : tempChess)
temp.add(new String(line));
result.add(temp);
return;
}
// 遍历row行的每一个位置判断是否可以放置皇后
for (int col = 0; col < n; ++col) {
if (isSafe(n, tempChess, row, col)) { // 如果安全
for (int j = 0; j < n; ++j)
tempChess[row][j] = '.'; // 那么这一行的其余位置全部放'.'
tempChess[row][col] = 'Q'; // 而这个位置放一个皇后
NQueens(n, tempChess, row + 1, result); // 然后递归地搜索下一行
}
}
}
private boolean isSafe(int n, char[][] chess, int row, int col) {
// 因为是从上往下一行一行地放,所以只要检查正上、左上、右上
// 判断列是否有危险
for (int i = 0; i < row; ++i) if (chess[i][col] == 'Q') return false;
// 判断左上对角线是否有危险
for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) if (chess[i][j] == 'Q') return false;
// 判断右上对角线是否有危险
for (int i = row, j = col; i >= 0 && j < n; --i, ++j) if (chess[i][j] == 'Q') return false;
// 都没有危险则安全
return true;
}
}
内容总结
以上是互联网集市为您收集整理的N皇后问题递归解法全部内容,希望文章能够帮你解决N皇后问题递归解法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。