别自己写回溯，Claude 用 CP-SAT 解玉米谜题
Solving a corn puzzle with CP-SAT
在 RC 的一个无聊周五，我拿起了一个 3D 打印的玉米拼图。作为软件工程师，我本想用递归回溯算法暴力求解，结果 Claude 直接甩给我一个 Python 脚本，第一行就引入了 Google 的 OR-Tools CP-SAT 库。这让我意识到自己犯了蠢：工业级约束求解器早已存在，何必重复造轮子？CP-SAT 将问题建模为变量和约束，高效地处理了类似精确覆盖（Exact Cover）的难题。随后，我和 Zaki、Tommy 一起用同样的工具轻松解决了数独问题。这次经历让我明白，面对特定类型的逻辑难题，调用成熟的求解器远比手写算法明智。
当看到脚本的第一行时，我意识到自己太蠢了：它直接导入了一个工业级的库来解决这类问题，而不是使用回溯算法。
HN 评论区
16- rurban
CP-SAT 本质上不过是一种被美化且经过优化的递归回溯搜索。文献中并没有更好的方案，他们称之为 DPLL。
它只是评估数据和约束条件，优先搜索更明显的路径，并更早地剪除非法路径。此外还有一些整数技巧，以及一个学习到的约束缓存。俄罗斯人在尝试高效解决象棋问题时发现了这些。IBM 和 Ken Thompson 只是单纯堆硬件，而俄罗斯人则做出了算法上的突破。现在的 LLM 也是如此。美国那边只是疯狂堆硬件，而中国则在优化算法。
- sashank_1509
好吧，就这个具体案例而言，一个只有 10 个块的谜题，递归回溯器速度会一样快，而且更重要的是，它更容易理解和实现。
如果这是一个有上千个块的谜题，我依然敢打赌，带有良好启发式策略的递归回溯器会胜过 CP-SAT，即便是在数独问题上，带有良好启发式策略的回溯法也能击败 CP-SAT。我不明白为什么 Claude 会立刻跳到使用 CP-SAT。
- emil-lp
这里的 CP 指的是 Constraint Problem，或者 CSP（约束满足问题）。
https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...