动态回溯：
?? ?寻路算法?? 深度寻路算法
?? ?动态回溯基本思想：
?? ??? ? 1.针对问题来一个解空间：各种方式来描述空间
?? ??? ??? ? 深度寻路算法中：要找起点 到 终点的路径? 要找到终点， 二维数组描述地图，用下标描述地图上的每一个点
???????????? 判断终点与 事先设定的 是否吻合
??? ??? ?2.确定易于搜索的解空间结构，并构造相应的判断函数
?? ?? ?? 3.用深度优先搜索方式来解决问题并在搜索过程中有合适的回溯方式（栈结构）
动态回溯 = 问题的解空间(二维数组描述) + 深度优先遍历 + 判断结果的结构 + 回溯
?? ?动态回溯一般适合解决哪些问题：
?? ??? ?1. 寻路 2. 货物装载 3. 0-1背包问题 4. 图的着色问题（铺格子）
?? ??? ?5. 电路排版问题 6. 旅行者售货员问题 7. N皇后问题
N皇后问题：8皇后 国际象棋
?? ?棋盘? 8*8? 能放下 8 个皇后（任意两个皇后都不能互相触及，不能被吃掉，其他皇后只能放在白色格子的地方) 有多少种放法？
??? 皇后可以走直线，也可以走斜线 米字格
??? 遇到不合适的就往前回退，退到合适为止，如果退到第一个位置就重新摆，摆到另一个的地方
???
4 皇后问题 ?棋盘? 4*4 能放下 4 个皇后
假设第一个位置如图，只有两种方式：①先竖着再横着 遍历列 ②先横着再竖着 遍历行
两种方式都可以选择，但是 皇后不可能在同一行上 或者 在同一列上
利用递归的方法依次查找，回溯再查找
这里采用 遍历列 的方式：首先，找到第一列的第一个合适位置后，第一列就舍弃了(同一行或者同一列不可能还有皇后)，进入第二列查找，从第二列的第一个位置开始判断能不能放皇后，找到合适位置放置皇后，把第二列舍弃，进入第三列，如果此时第三列无解，则回到第二列，寻找第二个合适位置，如果第二列没有合适位置，则回到第一列寻找下一个可以放置皇后的位置 . . .
???????????????????????????? ? ? ? ??? ? 遍历列??????????????????????????????????????????????????????????????????????????????????? 遍历行
确定方向后一个个去试即可，最终一定能找到
关于四皇后问题 遍历行 的方式参考：N皇后问题_hust_tank的博客-CSDN博客_n皇后问题
一行一行地摆放，在确定一行中的那个皇后应该摆在哪一列时，需要当前列是否合法，如果合法，则将皇后放置在当前位置，并进行递归，回溯。每行都摆满皇后时，则产生了一种解法，将所有解法收集并返回 下面代码采用 遍历列 的方式，遍历行 的方式只要把 i，j 位置交换即可
#include <iostream>
using namespace std;
//皇后的个数
#define N 8
//有cnt种解法
int cnt = 0;
//N皇后问题求解 参数:传入列数 传入数组
void Queen(int j, int Q[N][N]);
//遍历数组
void travel(int Q[N][N]);
//判断 i j 位置是否能放皇后 能 返回true 不能 返回false
bool isOkPos(int i, int j, int Q[N][N]);
int main() {
int Q[N][N] = { 0 };//解空间
Queen(0, Q);
cout << "解法种数为:" << cnt << endl;
while (1);
return 0;
}
//N皇后问题求解 从第0列到最后一列说明已经放好了
void Queen(int j, int Q[N][N]) {
if (N == j){//结束条件:N个皇后都已经放置好了-> 一个皇后都没有 放置好一个皇后 放置好两个皇后 放置好N个皇后...
travel(Q);//放置好后遍历数组
cnt++;//每次有4个皇后放好的情况解法+1
return;
}
//一个个放置-> 从某个位置开始放置-> i行 j列 i不在第四行就需要放皇后
for (int i = 0; i < N; i++) {
if (isOkPos(i, j, Q)) {//是否满足放置皇后的位置-> 如果可以放置就放置
Q[i][j] = 1;//放
Queen(j + 1, Q);//递归去放下一个位置-> 下一列
Q[i][j] = 0;//撤销 回退-> 不满足要求没有return-> 原来位置不能放皇后 把原来位置置为0 重新找下一个位置
}
}
//遍历数组
void travel(int Q[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << Q[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
//判断 i j 位置是否能放皇后 传入坐标和数组 能 返回true 不能 返回false
bool isOkPos(int i, int j, int Q[N][N]) {
int s, t;//t j 水平 s i 垂直
//一个个判断
for (s = i, t = 0; t < N; t++) {//横向判断
if (Q[s][t] == 1 && t != j) return false;//只要遇到有一个为1就不能放
}
for (t = j, s = 0; s < N; s++) {//竖向判断
if (Q[s][t] == 1 && s != i) return false;
}
//左上
for (s = i - 1, t = j - 1; s >= 0 && t >= 0; s--, t--) {
if (Q[s][t] == 1) return false;//已经排除当前位置为1的情况
}
//左下
for (s = i + 1, t = j - 1; s < N && t >= 0; s++, t--) {
if (Q[s][t] == 1) return false;
}
//右上
for (s = i - 1, t = j + 1; s >= 0 && t < N; s--, t++) {
if (Q[s][t] == 1) return false;
}
//右下
for (s = i + 1, t = j + 1; s < N && t < N; s++, t++) {
if (Q[s][t] == 1) return false;
}
//如果前面全部都没有返回-> 返回真 可以放在当前位置
return true;
}
4皇后问题
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
解法种数为:2
8皇后问题
解法种数为:92?