SwiftCSP
SwiftCSP 是用纯 Swift 编写的约束满足问题求解器（不使用 Cocoa）。它使用简单的回溯算法和可选的标准启发式算法来提高某些问题的性能。在目前的发展阶段，它的运行速度相当慢，但包含解决实际问题的示例。它应该在所有 Swift 平台上运行（iOS、OS X、Linux、tvOS 等）。
约束满足问题（CSP）是由变量组成的问题，这些变量有可能的值（域）和限制条件。求解器通过从每个变量的域中选择符合约束条件的值来找到该问题的潜在解决方案。有关更多信息，您应该查阅 Norvig 和 Russell 合著的《人工智能：一种现代方法》（第三版）的第 6 章。
安装
使用 Cocoapod 的 SwiftCSP或将文件（CSP.swift、Constraint.swift 和 Backtrack.swift）包含在源目录中，或通过指向此存储库通过 Swift 包管理器（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 绑定的一个绝佳示例）。
用法
您需要在初始化时创建 CSP 的一个实例并设置其 variables 和 domains。您还需要将 Constraint 的某个规范子类（如 UnaryConstraint、BinaryConstraint 或 ListConstraint）子类化，并实现 isSatisfied() 方法。然后，您将需要在 CSP 中添加您 Constraint 子类实例。所有这些类都使用泛型——具体来说，您应该指定变量的类型以及域的类型。
要解决您的 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 的原生字典类型。计划改进启发式算法，如 MAC3（已在源代码中留出空间供它们使用，欢迎贡献力量！）并应该会改善情况。在调用 backtrackingSearch() 时可以启用 MRV 或 LCV 启发式算法（已实现）以改善大多数情况下的性能。在我的测试中，MRV 改进了许多搜索，而 LCV 的实现仍有改进空间，但在特定问题上可能很有用。请注意，这些启发式算法也可能在某些问题中降低性能。
泛型
SwiftCSP 大量使用泛型。看起来有很多不必要的尖括号，但它允许类型检查器确保变量与它们的域和约束相匹配。由于 Swift 泛型的限制，Constraint 是类而不是协议。
欢迎贡献
实现启发式算法、以其他方式提高性能或简化设计等方面的贡献都深受欢迎。只需确保所有单元测试仍能运行，并且新版本仍保持任何 Hashable 类型作为变量和任何类型作为 Domain 的灵活性。欢迎提供额外的单元测试。还实现了一个简单的 MinConflicts 求解器，但它可以进一步完善。
著作权与许可
SwiftCSP 由 David Kopec 编写，并使用 Apache 许可证发布（参见 LICENSE）。它最初是我编写的一个 Dart 库的移植，而该库本身是对多年前我编写的一个 Python 库的移植。