SwiftCSP 是一个完全使用 Swift 编写的约束满足问题求解器（没有 Cocoa 依赖）。它采用简单的回溯算法，并可选地使用标准启发式方法来提高某些问题的性能。在目前的发展阶段，它的速度相对较慢，但包含了一些解决实际问题的示例。它应该可以在所有 Swift 平台（iOS、OS X、Linux、tvOS 等）上运行。
约束满足问题 (Constraint Satisfaction Problem, CSP) 是由 变量 组成的问题，这些变量具有可能的取值（域），并且存在对这些取值的 约束。求解器通过从每个变量的域中选择满足约束的值来找到该问题的潜在解决方案。 欲了解更多信息，请查阅 Russell 和 Norvig 撰写的《人工智能：一种现代方法》（第三版）的第 6 章。
使用 cocoapod SwiftCSP，或者将 Sources 目录中的文件（CSP.swift、Constraint.swift 和 Backtrack.swift）包含到你的项目中。或者，你也可以通过 Swift Package Manager (SPM) 并指向此仓库来安装 SwiftCSP。 0.9.7 及以上版本需要 Swift 5。 使用 0.9.6 版本支持 Swift 4。 使用 0.9.5 版本支持 Swift 3。 使用 0.9.4 版本支持 Swift 2。 对于 Swift 1.2 支持，请在 CocoaPods 上使用 0.9 版本，或在 GitHub 上使用 0.9.1 版本。
项目中包含的单元测试也是众所周知的玩具问题，包括：
查看这些示例应该能让你很好地了解如何使用该库。此外，主项目包含的程序是一个很好的电路板布局问题的图形示例（也是 macOS 上 Cocoa Bindings 的一个很好的例子）。
你需要创建一个 CSP 的实例，并在初始化时设置它的 variables 和 domains。你还需要继承 Constraint 的标准子类之一：UnaryConstraint、BinaryConstraint 或 ListConstraint 并实现 isSatisfied() 方法。然后，你需要将你的 Constraint 子类的实例添加到 CSP。所有这些类都使用了泛型 - 特别是，你应该指定变量类型和域类型。
要解决你的 CSP，你需要调用函数 backtrackingSearch()。如果你的 CSP 规模较大，你可能需要在异步块或后台线程中执行此操作。你也可以尝试使用不太成熟的 minConflicts() 求解器。
再次建议查看单元测试，但这里简要概述了如何设置八皇后问题：
let variables: [Int] = [0, 1, 2, 3, 4, 5, 6, 7] // create the variables, just Ints in this case
var domains = Dictionary<Int, [Int]>() // create the domain (also of Int type)
for variable in variables {
domains[variable] = []
for i in variable.stride(to: 64, by: 8) {
domains[variable]?.append(i)
}
}
csp = CSP<Int, Int>(variables: variables, domains: domains) // initialize the previously defined CSP
// Note that we specified through generics that its variables and domain are of type Int
let smmc = EightQueensConstraint(variables: variables) // create a custom constraint
// note that once again we specified both the variables and domain are of type Int
csp?.addConstraint(smmc) // add the constraint
当继承 Constraint 子类时，你需要为父类的泛型指定类型，如下所示：
final class EightQueensConstraint: ListConstraint <Int, Int>
因此，我们有一个泛型父类的非泛型子类。
对于具有中等大小域空间的问题，目前的性能不太好。 分析表明，这很大程度上可能归因于 Swift 原生 Dictionary 类型的性能。 计划改进启发式方法，例如 MAC3（源代码中留有空间，欢迎贡献！），应该可以改善这种情况。 你可以在调用 backtrackingSearch() 时启用 MRV 或 LCV 启发式方法（已实现），以提高许多实例的性能。 在我的测试中，MRV 改进了许多搜索，而 LCV 实现仍然有改进空间，但在非常具体的问题中可能很有用。 请注意，这些启发式方法也可能降低某些问题的性能。
SwiftCSP 广泛使用了泛型。 看起来有很多不必要的尖括号，但它允许类型检查器确保变量与其域和约束相匹配。 由于 Swift 泛型的限制，Constraint 是一个类而不是一个协议。
欢迎贡献实现启发式方法、以其他方式提高性能或简化设计的代码。 只需确保所有单元测试仍然运行，并且新版本保持了将任何 Hashable 类型作为变量和任何类型作为 Domain 的灵活性。 也欢迎添加更多单元测试。 简单的 MinConflicts 求解器也已实现，但可以改进。
SwiftCSP 由 David Kopec 编写，并根据 Apache License 发布（请参阅 LICENSE）。 它最初是我编写的 Dart 库 constraineD 的一个端口，而 constraineD 本身是我多年前编写的 Python 库的一个端口。