回溯法

约束问题可以由变量、每个变量允许的取值，以及必须满足的关系描述。回溯搜索从尚未赋值开始，每次选一个变量并尝试一个值，形成更完整的部分赋值；全部变量都有值且满足约束时，便得到一个解。

普通深度优先遍历只规定先向深处探索，回溯还要保存哪些选择已经试过，以及返回后怎样恢复父状态。实现可以复制状态，也可以记录并撤销修改；不能让一个失败分支留下的赋值污染随后尝试的其他分支。

参考：[1]

如果当前赋值已经违反约束，继续给其他变量赋值也不能修复这项既有冲突，便可立即回退，不必等到整个候选解都填满。固定一个变量选择顺序，还能避免仅因赋值先后不同而重复搜索同一个完整组合。

前向检查会在作出新赋值后，从相关未赋值变量的候选域中移除已不兼容的值；若某个域变空，便知道当前分支无法完成。回退时也必须恢复这些域，不能只撤销显式选中的变量而遗留剪枝造成的状态变化。

参考：[1]

剪枝需要有可靠依据：被删掉的分支确实不可能得到所需解，才能保留完整搜索的正确性。变量或取值的启发式排序可以让有希望的候选先被探索，但“先试谁”与“某个分支是否允许彻底删去”是不同决定。

在有限候选空间内，若保留所有必要分支并完整枚举，方法能找到解或确认没有解；设置超时提前停止则通常只能说明尚未找到。局部检查和前向传播改善很多实际实例，却不保证最坏运行从指数级变成多项式级。

参考：[1]