回溯搜索
许多情况下完成约束传播过程后仍存在具有多个可能值的变量。在这种情况下，必须通过搜索来求解问题。首先介绍用于部分赋值的回溯搜索算法，$CSP$的回溯搜索不断选择未赋值变量，然后依次尝试该变量的域中的所有值，试图通过递归调用将每个值扩展为一个解。如果调用成功，则返回解，如果调用失败，则将赋值恢复到前一状态，然后尝试下一个值。如果所有值都不成功，则返回失败。
事实上，简单回溯算法的效率并不高，通过修改其中的细节可以得到更好的算法。简单回溯算法的几个关键问题是：1、应该如何决定赋值的顺序？2、在每步搜索中应该执行怎样的推断？3、在适当的时机只能回溯一步吗？4、保存和复用搜索的部分结果是否能够提升效率？
最简单的策略是使用静态排序：按列表顺序$\left\{ X_1,X_2,…,X_n \right\} $选择变量。第二简单的策略是随机选择。这两种策略都不是最优的。
最少剩余值（$MRV$）启发式算法：选择“合法”值最少的变量，也被称为“最受约束变量”或“失败优先”启发式算法，它总选择最有可能马上导致失败的变量，从而可以对搜索树剪枝，避免遍历其他变量进行无意义地搜索。$MRV$启发式算法通常比随机或静态排序表现得更好，有时会带来数量级上的效率差异，尽管结果可能因问题而异。
度启发式算法通过选择与其他未赋值变量的约束最多的变量来降低未来选择的分支因子。最少剩余值启发式算法通常效果更好，但度启发式算法可以打破僵局。
一旦选择了一个变量，算法必须决定按什么顺序检验它的值。最少约束值启发式算法对此非常有效。它优先选择那些为约束图中相邻变量留下最多选择的值，试图为后续变量赋值留下最大的灵活性。
由于每个变量最终都必须被赋值，通过选择那些有可能最先失败的变量，在统计意义上，需要通过回溯才能找到的成功赋值就会更少。对于值排序，关键在于只需要找到一个解；故先寻找最有可能的值是更有意义的。因此，变量选择是失败优先，而值选择是失败延后。
之前讨论了$AC$-$3$算法如何在搜索前缩减变量的域。但在搜索过程中，推断的作用可能更大：每次为某个变量选择某个值时，都有一个全新的机会推断其相邻变量的新的域缩减。推断的最简单形式之一是前向检验。当变量$X$被赋值时，前向检验过程为其建立弧一致性：对于每个通过约束与$X$连接的未赋值变量$Y$，从它的域中删除与 X 的取值不一致的值。
对许多问题来说，将$MRV$启发式算法与前向检验相结合，可以使搜索更有效。可以将前向检验看作一种以增量方式计算$MRV$启发式算法完成其工作所需信息的有效途径。尽管前向检验能够检测出许多不一致，但它无法检测到所有的不一致，问题在于，它向前看得不够远。维护弧一致性（$MAC$）算法能检测出这类不一致性。
前向检验的不足之处在于每次只处理一个变量引起的不相容性，也许该变量引起的不相容性又会导致更多的不相容性，前向检验方法并没有考虑后续的不相容性，因此，MAC 算法递归传播约束，将由该变量引起的后续所有不相容性都考虑进去。当变量$X_i$被赋值后，调用$AC$-$3$，但在初始化只包括所有与$X_i$相邻的未赋值变量$X_j$的弧$(X_j, X_i)$，而不是$CSP$中的所有弧。从这出发，$AC$-$3$以通常的方式进行约束传播，如果任何变量的域缩减为空集，则$AC$-$3$调用失败，并立即回溯。可以看到，$MAC$严格来说比前向检验更强大，因为前向检验所做的事情与$MAC$对其队列的初始弧所做的相同；但与$MAC$不同的是，当变量的域发生变化时，前向检验不会递归地传播约束。
当搜索的一个分支失败时，$Backtracking$-$Search$算法将采取一种非常简单的策略：退回到上一个变量，并为其尝试一个不同的值。这称为时序回溯，因为时间上最近的决策点会被重新访问，这种方法虽然简单但是由于短时会导致无用回溯，无法发生冲突的实际原因。
一种更智能的方法是回溯到有可能求解这一问题的变量——导致$X_i$的某个可能值变成不可能值的变量。为此，考虑记录与$X_i$的某些值冲突的赋值集合。该集合称为$X_i$的冲突集。回跳方法将回溯到冲突集中最近的赋值，通过修改$Backtrack$算法，可以很容易地实现上述方法，即在检验合法值时，同时维护冲突集。如果找不到合法值，算法应该返回失败指示和冲突集中最近的元素。
前向检验不需要额外工作就能提供冲突集：当前向检验根据赋值$X = x$从$Y$的域中删除一个值时，它应该将$X = x$添加到$Y$的冲突集中。如果 Y 的域中的最后一个值也被删除，那么$Y$的冲突集中的赋值也要被添加到$X$的冲突集中。也就是说，已经知道$X = x$导致了（$Y$中的）矛盾，因此应该为$X$尝试不同赋值。
但事实上，前向检验能检测出这个事件并阻止搜索到达这样的节点！可以证明，每个被回跳剪除的分支也会被前向检验剪枝。因此，在前向检验搜索中，或者在使用更强一致性检验的搜索（如$MAC$）中，简单的回跳是多余的，只需执行其中一项。但其背后的思想仍然值得借鉴，这引出了一种不同的、更深层次的冲突集概念：正是前面一组变量共同导致了$X_i$连同任何后续变量都不存在一致解。使用以这种冲突集概念定义的冲突集的回跳算法称为冲突导向回跳。
现在必须解释如何计算这些新的冲突集，方法其实很简单，搜索分支的“终端”失败总是因为某个变量的域变为空集，该变量对应一个标准冲突集。从冲突点开始回跳到最近的节点，最近结点的冲突集吸收上一节点的冲突集并检查是否需要回跳并重复。总结一下：设$X_j$表示当前变量，$conf(X_j)$表示它的冲突集。如果$X_j$的每个可能值都失败了，则回跳到$conf(X_j)$中最近的变量$X_i$，并使用下列公式重新计算$X_i$的冲突集：
$$
conf\left( X_i \right) \gets conf\left( X_i \right) \cup conf\left( X_j \right) -X_i
$$
当搜索遇到冲突时，智能回溯可以告诉计算出要退回多远，这样就不会浪费时间去改变那些无法求解问题的变量。但在后续的搜索中也希望不要再遇到同样的问题。当搜索得出一个矛盾时，可以知道这是冲突集的某个子集引起的。约束学习的思想是从冲突集中找出引起问题的最小变量集。这组变量及其相应值称为无用赋值。如果想要记录无用赋值，要么通过向$CSP$中添加一个新的约束禁止这种赋值组合，要么通过维护一个单独的缓存。
前向检验或回跳可以有效地利用无用赋值。约束学习是现代$CSP$求解器用以提高复杂问题求解效率的最重要技术之一。
局部搜索
局部搜索算法对于许多$CSP$的求解都非常有效。它们使用完整状态形式，即每一状态为所有变量赋值，搜索一次改变一个变量的值，通常该赋值会违反一些约束。然后随机选择一个发生冲突的变量，希望改变它的值，从而更接近问题的解。最明显的方法是选择与其他变量冲突数最少的值——最少冲突启发式算法。
对许多$CSP$来说，最少冲突法都相当有效。神奇的是，在$n$皇后问题上，如果不计入皇后的初始布局，最少冲突法的运行时间基本上与问题规模无关。它甚至可以在（初始赋值后）平均$50$步内求解百万皇后问题。这一不同寻常的现象是$20$世纪$90$年代大量研究局部搜索和难易问题间区别的动力。粗略地说，用局部搜索求解$n$皇后问题非常简单，因为解密集地分布在整个状态空间上。最少冲突法也适用于困难问题。
所有局部搜索技术都可以应用于$CSP$，有些技术已被证实相当有效。最少冲突启发式算法下的$CSP$地形图通常存在一系列平台区。可能有数百万个变量赋值都只存在一个冲突。平台区搜索——允许横向移动到另一个得分相同的状态——可以帮助局部搜索走出平台区。这种在平台区的漫游可以由一种叫作禁忌搜索的技术导引：维护一个最近访问过的状态的列表，并禁止算法返回那些状态。模拟退火也可以用于逃离平台区。
另一种技术称为约束加权，旨在集中搜索重要约束。每个约束都有一个数值权重，初始时都为 1。在每步搜
索中，算法找出使其所违反的约束的总权重最低的变量，并修改其值。然后，增加当前赋值所违反的每个约束的权重。这种做法有两个好处：它为平台区增加了地形因素，确保从当前状态进行改进是有可能的；它还引入了学习策略，随着时间推移，难以求解的约束会被分配更高的权重。
局部搜索的另一个优点是，当问题发生变化时，它可以用于在线设定的问题。
问题的结构
处理复杂的真实世界问题的唯一可能方法是将其分解为若干子问题。可以简单地通过寻找约束图的连通分量来确定独立性。为什么分解子问题很重要？假设每个$CSP_i$具有所有$n$个变量中的$c$个变量，其中$c$是一个常数。那么共有$n/c$个子问题，求解每个子问题最多需要$d^c$工作量，其中$d$是域的大小。因此，总的工作量为$O(d^cn/c)$，关于$n$是线性的；如果不进行问题分解，总的工作量为$O(d^n)$，关于 n 是指数级的。
完全独立的子问题很好，但很少见。幸运的是，其他一些图结构也很容易求解。例如，当任意两个变量都只由一条路径连接时，约束图是一棵树。可以证明任何树状结构的$CSP$都可以在变量个数的线性时间内求解。这里的关键是一种新的一致性概念——定向弧一致性或$DAC$。变量顺序为$X_1,X_2,…,X_n$的$CSP$称为定向弧一致的，当且仅当，$j> i$时，每个$X_i$相对于每个$X_j$都是弧一致的。
为了求解树状结构的$CSP$，首先选择任一变量作为树的根节点，然后选择变量顺序，每个变量必须在其父节点之后。这种排序称为拓扑排序。任何有$n$个节点的树都有$n$−$1$条边，所以可以在$O(n)$步内使得该图具有定向弧一致性，每一步都必须比较两个变量的最多$d$个可能的值，总时间为$O(n\cdot d^2)$。
一旦有了一个定向弧一致的图，就可以沿着变量列表选择任意剩余值。因为从父节点到其子节点的每条边都是
弧一致的，所以，对于父节点选择的任何值，子节点都存在一个可选的有效值。这意味着不必回溯，可以沿着变量线性移动。
既然有了关于树的高效算法，可以考虑更一般的约束图是否可以以某种方式简化为树结构。有两种方法可以做到这一点：删除节点或合并节点。
通过将节点固定为某个值并从其他变量的域中删除任何与被固定节点取值不一致的值来从图中删除节点，当然，在许多情况下为被固定节点选择的值可能是错误的，因此需要尝试每个可能的值。一般算法如下：
1、选择$CSP$变量的一个子集$S$，使得约束图在删除$S$后成为一棵树，$S$称为环割集；
2、对于满足$S$上所有约束的$S$中变量的每种可能赋值，$a.$从剩余变量的域中删除任何与$S$赋值不一致的值，并且$b.$如果剩余的$CSP$存在一个解，那么将其连同$S$的赋值一起返回。
如果环割集的大小为$c$，那么总运行时间为：$O(d^c\cdot (n$-$c)\cdot d^2)$；首先需要尝试$S$中变量的值的所有$d^c$种组合，对于每种组合，需要求解一个大小为$(n$−$c)$的树问题。如果约束图“几乎是一棵树”，那么$c$将会非常小，相比于直接使用回溯法，将省掉巨大的开销——对$100$个布尔变量的示例来说，如果能找到一个大小为$c = 20$的割集，时间开销可以从宇宙生命周期缩短到几分钟。然而，在最坏情况下，$c$可能高达$(n −2)$。寻找最小环割集问题是$NP$困难的，但有一些高效的近似算法。
将约束图简化为树的第二种方法基于构建约束图的树分解：将原始图转换为树，树中的每个节点由一组变量组成，树分解必须满足以下 3 个要求：
1、原始问题中的每个变量必须至少出现在一个树节点中；
2、如果两个变量在原始问题中由一个约束连接，那么它们必须同时出现（连同约束）在至少一个树节点中；
3、如果一个变量出现在两个树节点中，那么它必须出现在连接这两个节点的路径上的所有节点中。
前两个条件保证了所有变量和约束在树分解中都有表示。第三个条件似乎更具技术性，但保证了原始问题的任何变量无论在哪出现都具有相同的值：树中的约束表明一个树节点中的变量必须与其相邻节点中的相应变量具有相同的值。一旦有了一个树状结构图，可以应用树$CSP$在$O(n\cdot d^2)$时间内得到解，其中$n$是树节点的个数，$d$是最大域的大小。需要注意的是在树中域是一组值元组，而不只是单个值。
一个给定的图允许多种树分解，在选择分解时，目标是使子问题尽可能小。图的树分解的树宽为最大节点的大小减 1，图本身的树宽定义为其所有树分解的最小宽度。如果一个图的树宽为$w$，那么给定相应的树分解，该问题可以在$O(n\cdot d^{w+1})$时间内求解。因此，如果$CSP$的约束图树宽有界，则该$CSP$在多项式时间内是可解的。遗憾的是，找出树宽最小的分解是 一个 NP 困难问题，但有一些启发式方法在实践中效果很好。
时间为$O(d^c\cdot (n$-$c)\cdot d^2)$的割集调整和时间为$O(n\cdot d^{w+1})$我树分解哪种方法会更好？每当有一个大小为$c$的环割集时，也会有一个大小为$w< c+1$的树宽，并且在某些情况下它可能要小得多。所以从时间上考虑，应该选择树分解，但环割集方法的优点是，它可以在线性内存中执行，而树分解需要关于$w$的指数级内存。
在变量的值中，或在约束关系本身的结构中，也可能存在重要的结构。考虑有$d$种颜色的地图着色问题。对于每个一致解，实际上都有一组通过排列颜色名形成的$d!$个解。例如，在澳大利亚地图中，$WA$、$NT$和$SA$肯定具有不同颜色，但实际上，将 3 种颜色分配给 3 个区域有$3! = 6$种方法，这称为值对称。在求解问题时肯定是希望通过打破这种赋值对称性将搜索空间缩小$d!$倍。可以通过引入对称性破缺约束做到这一点。但是一般来说，要消除所有的对称性是$NP$困难的，但打破值对称已被证明在许多问题上都是重要和有效的。
