首页 > 编程学习 > 回溯之N皇后问题

回溯之N皇后问题

发布时间:2022/10/5 17:33:52

问题及要求:
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-queens

解决思路
首先这道题难度还是比较大的,因为一般角度来思考的话你会觉得情况太多而无从下手,所以这道题是需要回溯的思想,回溯就是深搜算法中衍生的一种思想,就是当你一条路走不通时,你需要返回上一级继续寻找其他的路径,这个返回上一级就是回溯思想的核心,其实还和递归有一样的成分在其中。你只需要这点就可以了。
好了,现在回到这道题上,需要在n*n的棋盘上放n个皇后,并且要求皇后之间不能在同一行,同一列,同一斜线上,那么这时可以先在棋盘的(0,0)位置放一个皇后,然后第二行再依次放判断哪个位置可以放一个皇后,如果第二行四个位置都不满足那么就说明已经走不通了,就更不需要接着考虑第三行了,这时就需要返回上一行(第一行),再在第一行的第一列放一个皇后(0,1),再重复上述操作,直到行到第四行,就可以找到一个满足要求的情况。

拿4*4来说满足要求的有两种情况如下图所示:
在这里插入图片描述
在这里插入图片描述
如下图所示红蓝斜线的判断公式不一样,一个是横纵坐标之和相同,一个是横纵坐标之差相同。
在这里插入图片描述

代码实现:

class Solution {
public:void dfs(vector<vector<pair<int,int>>>& res,vector<pair<int,int>>& sol,int currow,int n){if(currow==n){//所有行皇后的位置都已确定,保存这种解决方案,能走完最后一行说明之前都是满足的res.push_back(sol);}for(int i=0;i<n;i++){ //列if(isvalid(sol,currow,i)){         //此位置放一个皇后会不会和之前存的坐标相冲突//如果不冲突保存当前坐标sol.push_back(make_pair(currow,i));  //solution里存的只是当前满足的坐标dfs(res,sol,currow+1,n);       //递归下一行sol.pop_back();                //走到这里证明当前行不满足}}                  //因为如果一行中的每列的位置都不满足,那么就会返回到上一行,这是for循环决定的}bool isvalid(vector<pair<int,int>>& sol,int currow,int col){//不在同一列,不在同一斜线上for(auto& e: sol){if(e.second == col||e.first+e.second==currow+col||e.first-e.second==currow-col){   //这个式子你只需要看在一列上的或者在一斜线上的点的坐标关系return false;}}return true;}vector<vector<string>> solveNQueens(int n) {//判断是否在同一斜线上,横纵坐标和一样或者横纵坐标差一样vector<vector<string>> ret;         //用来保存最终结果,如题要求的那样vector<vector<pair<int,int>>> res;  //用来保存最终满足的所有坐标组,例如上面的4*4就有两组坐标集合vector<pair<int,int>> sol;          //用来保存当前的可能坐标dfs(res,sol,0,n);                            for(auto& e:res){                   vector<string> retstr(n,string(n,'.'));  //针对每个可能的坐标组初始化要求如题for(auto& pos: e){retstr[pos.first][pos.second] = 'Q';  //遍历坐标组中满足的坐标来把retstr中的元素变为字符Q,一个Q就代表一个皇后}ret.push_back(retstr);            }return ret;                  //返回所有可能的集合}
};

总结:
在这里运用c++里的pair就很好的解决了存储以及处理坐标的问题,pair的使用频率还是很高的,尤其是遇到键值对的问题,所以合理使用会让程序变得很简单。回溯的核心就是要找到什么时候可以回退到上一层,找到了的话解决问题也就会变得简单。


本文链接:https://www.ngui.cc/el/1524706.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000