风起于青萍之末
浪成于微澜之间
🎥个人主页
🔥个人专栏
🎥前期回顾-环形链表
目录
回溯算法的简介
N皇后问题
思路
代码测试
N皇后
思路
判断一竖列是否有皇后
判断对角线是否有皇后
代码测试
回溯算法的简介
| 回溯是递归的副产品，只要有递归就会有回溯 ，所以回溯法也经常和DFS混在一起 |
回溯的介绍：在搜索解空间时会采用 尝试 与 回退 的策略
回溯算法实际上一个 类似枚举的搜索 尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 回溯 返回，尝试别的路径。回溯法是一种深度优先搜索，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 回溯点
剪枝的介绍：
回溯法的基本行为是 搜索，搜索过程使用 剪枝 函数来为了避免无效的搜索
(1)使用约束函数，剪去不满足约束条件的路径
(2)使用限界函数，剪去不能得到最优解的路径
DFS的介绍：
DFS是一种遍历或搜索图、树等数据结构的算法，当然这个图、树未必要存储下来(隐式处理就是回溯法)常见的是通过某种关系构造出的搜索树，搜索树一般是排列型搜索树和子集型搜索树
排列型就是每次枚举选哪个
子集型就是对于每一个元素选或不选
DFS 从起始节点开始，沿着一条路径尽可能探入地搜索直到无法继续为止，然后回溯到前一个节点，继续探索其他路径，直到遍历采整个图
DFS 使用栈或递归来管理节点的遍历顺序
N皇后问题
题目链接：N皇后问题
题目描述#
在 N x N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击(即任意 2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 度角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法
输入描述#
输入中有一个正整数 N <= 10，表示棋盘和皇后的数量
输出描述#
为一个正整数，表示对应输入行的皇后的不同放置数量
输入输出样例#输入
5输出
10
思路
算法思想：排列型回溯
假设我们是4 x 4棋盘，然后判断皇后在棋盘的攻击范围：
<1>
因为我们是 4x4 的棋盘所以我们要放置4个皇后，所以皇后放置第一行第一列是不行的
<2>
我们发现：
<1>棋盘每行都 必然有且仅有 一个皇后
<2>棋盘的 第一行第一列 放皇后是 不行 的
<3>每放置一个皇后就将对应的米字型区域设置为 禁区，后面的皇后就不能放在 禁区 里，回溯的时候将 禁区 取消掉
<4>为了正确维护 禁区，不能使用 bool 数组来表示 禁区，需要使用 int 数组，表示这个位置被多少个皇后占用了，当占用数为 0 时表示 禁区 解除
于是我们可以采取逐行放置策略：从第一行开始，在每行放置一个皇后，直至最后一行结束
代码测试
#include<bits/stdc++.h> using namespace std; const int N = 10; int vis[N][N]; //表示多少个皇后被占用了 int n,ans; //设置全局变量初始化为0 void dfs(int dep) //dep表示当前的搜索深度 { if(dep == n+1) //从第一行开始，在每行放置一个皇后，直至最后一行结束 { ans++; return; } for(int i = 1;i<=n;i++) { //当前的位置已经被占用了 if(vis[dep][i])continue; //修改状态,米字形式方阵 for(int _i = 1;_i<=n;_i++)vis[dep][i]++,vis[_i][i]++; for(int _i = dep,j = i;_i>=1&&j>=1;_i--,j--)vis[_i][j]++; for(int _i = dep,j = i;_i<=n&&j>=1;_i++,j--)vis[_i][j]++; for(int _i = dep,j = i;_i>=1&&j<=n;_i--,j++)vis[_i][j]++; for(int _i = dep,j = i;_i<=n&&j<=n;_i++,j++)vis[_i][j]++; dfs(dep+1);//搜索下一层 //恢复（回溯）棋盘，减少位置占用 for(int _i = 1;_i<=n;_i++)vis[dep][i]--,vis[_i][i]--; for(int _i = dep,j = i;_i>=1&&j>=1;_i--,j--)vis[_i][j]--; for(int _i = dep,j = i;_i<=n&&j>=1;_i++,j--)vis[_i][j]--; for(int _i = dep,j = i;_i>=1&&j<=n;_i--,j++)vis[_i][j]--; for(int _i = dep,j = i;_i<=n&&j<=n;_i++,j++)vis[_i][j]--; } } int main() { cin>>n; dfs(1);//从第一个位置开始搜索 cout<<ans<<endl; return 0; }
N皇后
题目链接：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"]]提示：
1 <= n <= 9
思路
回溯+剪枝+坐标系
以下我们用3 x 3的棋盘进行模拟
我们发现：
<1>皇后放在第一行第一列是凑不出 3 的，这种放法是不可行的，所以我们要进行剪枝
<2>棋盘在米字行禁区的需要剪枝
判断一竖列是否有皇后
我们可以定义一个 bool 类型的数组，判断我们这一列是否有皇后
如果为 true 则这一列有皇后，为 false 则这一列没有皇后
判断对角线是否有皇后
我们给将棋盘放在直角坐标系中，对角线的方程为：y = x + b转换一下就是y - x = b
我们发现 (纵坐标 - 横坐标） 是一个常数，于是我们可以定义一个 bool 类型的数组
将这个常数存放在 bool 的数组里面
如果 常数 的坐标是 true 则代表这条对角线有皇后，是 false 则代表这条对角线没有皇后
如果 y - x = b(b是负数)，我们可以采用下面这个式子：y - x + n = b + n 整体向上平移
这一侧的对角线已经分析完毕，还有一侧对角线就留给大家去分析
递归深度就是 row 控制棋盘的行，每一层里 for 循环的 col 控制棋盘的列，一行一列，确定了放置皇后的位置
每次都是要从新的一行的起始位置开始搜，所以都是从 0 开始
代码测试
class Solution { bool checkCol[10],checkDig1[20],checkDig2[20]; //checkCol一竖列，checkDig1主对角线，checkDig2副对角线 vector<vector<string>> ret; //最终棋盘 vector<string> path; //每个棋盘 int n; public: vector<vector<string>> solveNQueens(int _n) { n = _n; path.resize(n); //分配空间 for(int i = 0;i<n;i++) path[i].append(n,'.'); //初始化n个. dfs(0); //从起始位置开始搜索 return ret; } void dfs(int row) { if(row == n) { ret.push_back(path); //每一行放置合法皇后 return; } for(int col = 0;col<n;col++) //尝试在这一行放皇后 { //剪枝 if(!checkCol[col]&&!checkDig1[row-col+n]&&!checkDig2[row+col]) { path[row][col] = 'Q'; checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col] = true;//用过了就占用现场 dfs(row+1);//从下一行开始搜索 //回溯 path[row][col] = '.'; checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col] = false;//不用就收拾现场 } } } };
