约束满足问题(CSPs)在数据库检索(Database Retrieval)、集成电路设计、计算机视觉、定理证明、机器人规划、机器学习等诸多研究领域具有广泛的应用背景。正是因为CSP问题是一类十分普遍的问题以及近年来引人注目的复杂性理论研究促使我们从算法和复杂性两个角度来研究它。 本文工作的重点是针对那些属于NP-Complete的CSP问题(如SAT、K-着色和Hamilton圈问题等)。我们除提出了求解此类型问题的一系列目前最有效算法之外，还讨论了此类问题的难易分布和相变规律。 局部搜索算法和基于回溯的搜索算法是求解CSP问题的两种基本算法。本文结合CSP问题的特点并借助于分治策略将它们有机地结合起来而形成一种快速、完备的求解算法—多级重排搜索算法(MSRA)。MSRA算法在与一般D-P算法的性能比较中所表现出的优势是十分明显的。此外，我们找到了N-皇后问题一个特殊解(或构造解，它区别于历史上所出现的其他解)，并且分析了该问题的特殊性。 之后，本文详尽分析了MSRA算法的平均时间复杂性并且用实验结果进一步证实了所得结论。 考虑到NP-Complete理论通常只关心问题在最坏情况下的复杂性而极少为具体的问题求解算法提供有价值的指导，本文主要从实验分析的角度来研究CSP问题的难解性。由于算法要面对的是一个个具体的问题例，而我们又可将这些具体的问题例以某种方式将其划归若干问题子类，这样，我们就可以通过分析所谓问题例的“难度”(Hardness)及其分布情况来研究CSP的内在规律。在这里，问题例的“难度”指的是该问题例所属问题子类的平均复杂性最小上界。已有研究结果表明CSP问题确实存在“相变”现象，即问题例的“难度”相对于特定序参量(通常指约束条件个数与变量个数之比值)而言分布上的突变现象。这在本文中不仅得到了进一步证实而且更准确地确定了各种CSP问