引言

如果你看懂了上一篇的回溯基本法，那这篇更是小菜一碟，我将尝试在 read more 之前讲明白它。

相比基本法每次尝试是从$D_l$依次取一个然后验证，如果为假则剪枝，否则即等待成立，Walker 则从另一个角度出发，每次从$S_l$取完最小元素$x_l$后，直接更新下次的 $S_{l+1}$，把不符合条件从集合中删掉，然后接着往下走直到$l>n$。回溯时则直接令$S_l\leftarrow S_l \backslash x_l$ 去除$x_l$，然后接着选下一个。

分析

仔细分析下两个方法的执行顺序有些不同，一个是先选再去除明显为假的，另一个是先去除明显为假再选，别看只是变换了顺序，但在一些具体实现上效率差别可大了，比如在 n 皇后中，可以通过把这次放置皇后的攻击范围从下一层候选集中抹掉，这样下一层的$S_l$只要不为空，必然是可以选的等待成立，以此类推。这个攻击范围的抹掉又可以通过位运算来实现，而且利用递归的优势，回溯不需要做任何操作。因为这题的位运算版本网上太多了，所以就不在这里列出了。