苏州市吴中区住房和城乡建设局官方网站,wordpress高端教程,主机开通成功网站建设中,wordpress 新闻页面按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。给你一个整数 n #xff0c;返回所有不同的 n 皇后问题 的解决方案。每一种解法包…按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位
示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。 示例 2
输入n 1
输出[[Q]] 不能同行不能同列不能同斜线 先检查将要摆放的位置是否满足这三个条件如果满足则在这个位置放Q
bool isValid(int x,int y,vectorstring chessboard,int n) {// 检查当前列是否有皇后for (int i 0; i x; i) { // 这是一个剪枝if (chessboard[i][y] Q) return false;}// 检查 45左上角 度角是否有皇后for(int ix-1,jy-1;i0 j0;i--,j--) {if (chessboard[i][j] Q) return false;}// 检查 135右上角 度角是否有皇后for(int ix-1,jy1;i0 jn;i--,j) {if (chessboard[i][j] Q) return false;}return true;
}// n 为输入的棋盘大小x 是当前递归到棋盘的第几行了
void backtracking(int n, int x, vectorstring chessboard) {......for(int y0;yn;y) {if(isValid(x, y, chessboard, n)false) continue;chessboard[x][y] Q; // 放置皇后backtracking(n, x 1, chessboard);chessboard[x][y] .; // 回溯撤销皇后}
}
如果搜到了树的叶子节点 表明找到了皇后们的合理位置了
if(x n) {result.push_back(chessboard);return;
} C代码
class Solution {
public:vectorvectorstring result;bool isValid(int x,int y,vectorstring chessboard,int n) {// 检查当前列是否有皇后for (int i 0; i x; i) { // 这是一个剪枝if (chessboard[i][y] Q) return false;}// 检查 45左上角 度角是否有皇后for(int ix-1,jy-1;i0 j0;i--,j--) {if (chessboard[i][j] Q) return false;}// 检查 135右上角 度角是否有皇后for(int ix-1,jy1;i0 jn;i--,j) {if (chessboard[i][j] Q) return false;}return true;}// n 为输入的棋盘大小x 是当前递归到棋盘的第几行了void backtracking(int n, int x, vectorstring chessboard) {if(x n) {result.push_back(chessboard);return;}for(int y0;yn;y) {if(isValid(x, y, chessboard, n)false) continue;chessboard[x][y] Q; // 放置皇后backtracking(n, x 1, chessboard);chessboard[x][y] .; // 回溯撤销皇后}}vectorvectorstring solveNQueens(int n) {vectorstring chessboard(n,string(n,.));backtracking(n,0,chessboard);return result;}
};
时间复杂度: O(n!)空间复杂度: O(n)
参考和推荐文章、视频
代码随想录 (programmercarl.com)https://www.programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html#%E6%80%9D%E8%B7%AF这就是传说中的N皇后 回溯算法安排| LeetCode51.N皇后_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Rd4y1c7Bq/?spm_id_from333.788vd_sourcea934d7fc6f47698a29dac90a922ba5a3回溯算法基本框架
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}
