定义
之前的搜索部分讨论了通过搜索状态空间进行问题求解的思想：状态空间是一个由节点表示状态，边表示动作的图。领域特定的启发式算法可以估计从给定状态到达目标的代价，但从搜索算法的角度来看，每个状态都是原子的，即不可分割的——一个没有内部结构的黑盒。对于每个问题，需要领域特定的代码来描述状态之间的转移。
接下来要讨论的是通过对每个状态使用因子化表示来打破黑盒：因子化表示为一组变量，每个变量都有自己的值。当每个变量的值都满足对该变量的所有约束时，问题就解决了。以上述方式描述的问题称为约束满足问题（$constraint$ $satisfaction$ $problem$，$CSP$）。
$CSP$搜索算法利用了状态结构的优势，并且使用通用的而不是领域特定的启发式算法来求解复杂问题。其主要思想是，通过识别违反约束的变量/值组合来一次性消除大部分搜索空间。$CSP$的另一个优势是可以从问题描述中推导出行动和转移模型。
$CSP$问题由三个部分组成：
$\mathcal{X}$：变量集合$\left\{ X_1,X_2,…,X_n \right\} $；
$\mathcal{D}$：域集合$\left\{ D_1,D_2,…,D_n \right\} $，与每个变量一一对应，域$D_i$由变量$X_i$的一组允许的值$\left\{ v_1,v_2,…,v_k \right\} $组成；
$\mathcal{C}$：约束集合$\left\{ C_1,C_2,…,C_n \right\} $，用来规定允许的值的组合，约束$C_i$由$< scope,rel>$对组成，前者说明对象，后者说明关系。
$CSP$要处理变量赋值（assignment）问题，即$\left\{ X_1 = v_i,X_2 = v_j,…\right\} $。不违反任何约束的赋值称为一致或合法赋值。完整赋值是指每个变量都已被赋值；$CSP$的解是一致完整赋值。部分赋值是指某些变量还未赋值，而部分解是一致部分赋值。一般来说，$CSP$求解是$NP$完全问题，尽管$CSP$的一些重要子类已经可以非常高效地求解。
为什么要将问题形式化为$CSP$呢？第一个原因是$CSP$可以自然地表示各种问题，将一个问题形式化为$CSP$通常很容易；第二个原因是多年的研究工作使得$CSP$求解器快速而高效；第三个原因是相比于原子的状态空间搜索器，$CSP$求解器可以快速消除大面积搜索空间。
在原子的状态空间搜索中，只能知道某个状态是否为目标状态吗，使用$CSP$形式化一旦发现某个部分赋值违反了约束，可以马上放弃对该部分赋值的进一步改进。此外，可以看出为什么某个赋值不是解——可以看出哪些变量违反了约束——从而把注意力集中在关键变量上。因此，许多原子状态空间搜索难以求解的问题形式化为$CSP$后都可以快速求解。
最简单的$CSP$所涉及的变量具有离散有限域，8 皇后问题就可以看作是一个有限域$CSP$。离散域也可以是无限的，例如整数集或字符串集。对于无限域必须使用隐式约束，而不是显式的值元组。对于整数变量的线性约束存在特殊的求解算法，但可以证明，不存在求解整数变量上一般非线性约束的算法——这个问题是不可判定的。
连续域约束满足问题是真实世界中的常见问题，在运筹学领域得到了广泛研究。最著名的一类连续域$CSP$是线性规划问题，其约束必须为线性等式或不等式。线性规划问题可以在关于变量个数的多项式时间内求解。此外人们还研究了具有不同类型约束和目标函数的问题——二次规划、二阶锥规划等。这些问题构成了应用数学的一个重要领域。
除了检查$CSP$中变量的类型以外，检查约束的类型也是很有用。最简单的类型是一元约束，它限制单个变量的值。二元约束关系到两个变量，二元$CSP$只存在一元约束和二元约束。也可以继续定义高阶约束。例如，三元约束。包含任意个数变量的约束称为全局约束，这个名称很传统，但容易混淆，因为它不需要包含问题中的所有变量）。最常见的全局约束之一是$Alldiff$，它表示约束中涉及的所有变量必须具有不同的值。
如果引入足够多的辅助变量，每个有限域约束都可以简化为一组二元约束。这意味着可以将任意一个$CSP$转换为只有二元约束的$CSP$，这将使算法设计变得更加简单。将$n$元$CSP$转换为二元$CSP$的另一种方式是对偶图变换：创建一个新图，原图中的每个约束用新图中的一个变量表示，原图中的每对共享变量的约束用新图中的一个二元约束表示。
实践中会更加偏向于$Alldiff$这样的全局约束，而不是一组二元约束，这有两个原因。首先，使用$Alldiff$描述问题更简单而且更不容易出错。其次，可以为全局约束设计相比于基元约束更有效的专用推理算法。
前文描述的约束都是绝对约束，违反这些约束的可能解将被排除。许多真实世界的$CSP$包含偏好约束，偏好约束规定哪些解是首选的。偏好约束通常可以编码为个别变量赋值的代价。通过这样的形式化，带偏好约束的$CSP$可以用基于路径的或局部的优化搜索方法求解。通常称这样的问题为约束优化问题（$constrained$ $optimization$ $problem$，$COP$）。线性规划是一类$COP$。
约束传播
原子的状态空间搜索算法只有一种方式：通过扩展节点来访问后继节点。$CSP$算法有不同选择。它可以通过选择一个新的变量赋值来生成后继，或者执行一种称为约束传播的特定类型推断：使用约束减少一个变量的合法值的数量，这反过来又可以减少另一个变量的合法值，以此类推。其思想是，通过这一过程，当选择下一个变量赋值时，需要考虑的选项会减少。约束传播可以与搜索交替进行，也可以作为搜索开始前的预处理步骤。有时这种预处理就可以求解整个问题，所以根本不需要搜索。
约束传播的核心思想是局部一致性，如果将每个变量看作图中的一个节点，将每个二元约束看作一条边，则增强图中每一部分局部一致性的过程会导致整个图中不一致的值被删除。局部一致性有几种不同类型，接下来依次进行介绍。
最简单的是节点一致性，如果单个变量的域中的所有值都满足该变量的一元约束，则该变量是节点一致的。在求解过程开始时，通过缩减具有一元约束的变量的域，可以很容易地消除$CSP$中的所有一元约束。
如果$CSP$中某一变量的域内的所有值都满足该变量的二元约束，那么该变量就是弧一致的。更正式地说，对于变量$X_i$、$X_j$，如果对于当前域$D_i$中的每个值，$D_j$中都存在一些值满足弧$(X_i, X_j)$上的二元约束，则称$X_i$相对于$X_j$是弧一致的。如果每个变量相对所有其他变量都是弧一致的，那么这个图就是弧一致的。
最流行的增强弧一致性的算法为$AC$-$3$。为了使每个变量保持弧一致，$AC$-$3$算法将维护一个弧队列。初始时，队列包含$CSP$中的所有弧。（每个二元约束都有两条弧，每个方向各一条。）然后$AC$-$3$从队列中弹出任意一条弧$(X_i, X_j)$并使$X_i$相对于$X_j$弧一致。如果$D_i$保持不变，算法就会处理下一条弧。但是如果$D_i$得以修正（域变小），那么将所有的弧$(X_k, X_i)$添加到队列中，其中$X_k$是$X_i$的邻居。这样做的原因是，即使之前已经处理过$X_k$，$D_i$的变化也可能会进一步缩减$D_k$。
如果$D_i$变为空集，那么表示整个$CSP$不存在一致解，$AC$-$3$可以马上返回失败。否则，继续检查，不断尝试缩减变量的域，直到队列中没有弧。此时，算法得到了一个与原始$CSP$等价的$CSP$（同解），但弧一致$CSP$搜索起来会更快，因为它的变量的域更小。在某些情况下，它可以完全求解问题（通过将每个域的大小缩减为 1），而在其他情况下，它可以证明解不存在（通过将某些域的大小缩减为 0）。
$AC$-$3$的算法复杂性可以如下分析。假设$CSP$有$n$个变量，每个变量的域大小不超过$d$，带有$c$个二元约束（弧）。每个弧$(X_k, X_i)$最多只能插入队列$d$次，因为$X_i$最多有$d$个值要删除。对弧一致性的检查可以在$O(d^2)$时间内完成，因此最坏情况下的时间复杂性为$O(c\cdot d^3)$
弧一致性利用弧（二元约束）将域（一元约束）收紧。为了求解$CSP$问题，需要更强的一致性概念。
路径一致性使用隐式约束（通过观测变量的三元组推断）将二元约束收紧。考虑两个变量的集合$\left\{ X_i,X_j \right\} $和第三个变量$X_m$，如果对于每个满足$\left\{ X_i,X_j \right\} $上约束（如果有的话）的赋值$\left\{ X_i = a,X_j = b \right\} $，都存在$X_m$的一个赋值满足$\left\{ X_i,X_m\right\} $和$\left\{ X_m,X_j \right\} $上的约束，则称$\left\{ X_i,X_j \right\} $相对于$X_m$是路径一致的。这一名称是指从$X_i$途经$X_m$到$X_j$的路径的整体一致性。
可以用$k$一致性的概念定义更强的传播形式。如果对于$CSP$的任意$(k −1)$个变量的集合以及这些变量的任意一致赋值，任意第$k$个变量都存在一个一致赋值，则称该$CSP$是$k$一致的。$1$一致性表示，给定空集，可以使任何单变量集合满足一致性，这就是节点一致性。$2$一致性等价于弧一致性。对于二元约束图，$3$一致性等价于路径一致性。
如果一个$CSP$是 k 一致的，也是$(k −1)$一致的，$(k −2)$一致的……一直到$1$一致的，则称它是强$k$一致的。假设有一个包含$n$个节点的$CSP$，并且是强$n$一致的(即当$k = n$时，强$k$一致)，那么可以这样求解该问题：首先，为$X_1$选择一个一致值。然后因为图是$2$一致的，所以保证能为$X_2$选出一个一致值，因为它是$3$一致的，所以能为$X_3$选出一个值，以此类推。对于每个变量$X_i$，只需在它的域的$d$个值中搜索，就可以找到一个与$X_1, …, X_{i−1}$一致的值。总运行时间只有$O(n^2\cdot d)$。
当然，世界上没有免费的午餐：约束满足问题通常是$NP$完全的，任何建立$n$一致性的算法在最坏情况下的时间复杂性都是$n$的指数级。更糟的是，$n$一致性所需的空间复杂性也是$n$的指数级。在实践中，确定适当的一致性检查层级基本上是一门经验科学。比较常见的是计算$2$一致性，其次是计算$3$一致性。
全局约束涉及任意个数的变量，实际问题中经常出现全局约束，可以通过专用算法处理这些约束，这些算法比目前介绍的一般方法更加高效。例如，$Alldiff$约束规定所有相关变量必须取不同的值，对$Alldiff$约束进行不一致性检测的一种简单形式如下所示：如果约束中涉及$m$个变量，而且它们一共具有$n$个可能的不同值，且$m> n$，那么约束不可能满足。
这将导出以下简单算法。首先，删除约束中任意一个单值变量（域中只有一个值的变量），并且从其余变量的域中删除该变量的值。只要还存在单值变量，就重复上述过程。如果在任一点上产生了空集，或者存在比剩余取值数更多的变量，则检测到了不一致性。因，对高阶约束进行简单一致性处理有时比对等价的二元约束集应用弧一致性更高效。
另一种重要的高阶约束是资源约束，有时也称为$Atmost$约束。通过检验当前域的最小值之和可以检测不一致性。如果当前某个变量的域中的最大值加上所有其他变量的域的最小值超过约束，则可以通过删除该最大值来保持一致性。
对于大规模的、具有整数值的资源有限问题，将每个变量的域表示为一个大的整数集然后通过一致性检查方法逐渐缩减这个集合通常是不可能的。相反，域由上界和下界表示，通过边界传播处理。例如，在航班调度问题中，假设存在两趟航班，$F_1$和$F_2$，其中飞机的容量分别为$165$和$385$。$F_1$和$F_2$航班上乘客数量的初始域为：
$$
D_1=\left[ 0,165 \right] ,D_2=\left[ 0,385 \right]
$$
假设有附加约束，两趟航班所搭载的总乘客数必须是 420：$F_1+F_2=420$ 。通过传播边界约束，可以将域缩减为：
$$
D_1=\left[ 35,165 \right] ,D_2=\left[ 255,385 \right]
$$
如果对于任意变量$X$和它的上下界值，任意变量$Y$，都存在满足$X$和$Y$之间约束的 Y 的值，则称$CSP$是边界一致的。这种边界传播在实际的约束问题中得到了广泛应用。
