https://www.bilibili.com/video/BV1HY411R7Tc/?spm_id_from=333.337.search-card.all.click&vd_source=d84f08a0531e04d6d41c38180cce9fb5

https://www.bilibili.com/video/BV1Ls411W7PB?p=65&spm_id_from=pageDriver&vd_source=d84f08a0531e04d6d41c38180cce9fb5

https://www.bilibili.com/video/BV18X4y1k74c?p=48&vd_source=d84f08a0531e04d6d41c38180cce9fb5

https://www.bilibili.com/video/BV1iG411L73B/?spm_id_from=333.337.search-card.all.click&vd_source=d84f08a0531e04d6d41c38180cce9fb5

四课全开，不信还不会

以https://www.bilibili.com/video/BV1HY411R7Tc/?spm_id_from=333.337.search-card.all.click&vd_source=d84f08a0531e04d6d41c38180cce9fb5

为蓝本，记笔记

回溯法(1)

幽默，我也不知道这图片上传到哪里l了

image-20240526211253362

image-20240526211951135

1
2
3
4
5
6
7
8
9
void backtrack(int t) {
    if (t > n) output(x);
    else {
        for (int i = f(n, t); i <= g(n, t); i++) {
            x[t] = h(i);//当前解
            if (constraint(t) && bound(t)) backtrack(t + 1);
        }
    }
}

N皇后问题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	bool Queen::Place(int k)//检查前k行是否合法
{
    for (int j = 1; j < k; j++)//逐行检查
        if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k]))
            return false;
    return true;
}
void Queen::Backtrack(int t)//对第t行放置皇后
{
    if (t > n) sum++;//层数大于n时候，统计解的个数
    else {
        for (int i = 0; i <= n; i++) {
            x[t] = i;
            if (Place(t)) Backtrack(t + 1);//如果可以放置
            //继续找下一行的位置
        }
    }
}

回溯法(2)