让 AI 写回溯算法，最让人不放心的往往不是递归会不会停，而是"得到一张填满的表"是否真的等于解出了题。N 皇后要行列对角线互不攻击；数独还要加九宫格约束和原题线索不可覆盖。本文用一组自包含验证程序把这件事钉死：约束检查器与求解器分离，正确性证据单独算账。
核心原则：求解器和检查器分开
很多 AI 生成的求解代码把"递归成功返回"直接当作"解正确"——这两件事之间可能隔着一个错误的终止条件。正确姿势是写一个独立的 check_answer：确认答案是满盘、每个单元约束成立（行列宫无重复）、所有原题线索保持原值。递归返回的结果必须过检查器才算数，这一条对人类写的代码同样成立。
N 皇后：构造保证加对角线校验
按行放置天然保证每行一枚，剩下校验列差与行差：
def dfs(cols):
row = len(cols)
if row == n:
out.append(tuple(cols)); return
for c in range(n):
if all(c != old and abs(c-old) != row-r
for r, old in enumerate(cols)):
dfs(cols+[c])
对角线冲突的判定是 abs(c-old) == row-r——列距等于行距即同对角线。验收锚点用已知解数量序列：n=1 到 8 的解数应为 [1,0,0,2,10,4,40,92]，这个数列写死在断言里，AI 的实现数量级对不上立刻现形。
数独：候选集与 MRV 的正确理解
约束建模用 27 个组（9 行、9 列、9 宫）推导每格的 peers 集合，候选值就是 1-9 减去 peers 已用值：
groups = [[9*r+c for c in range(9)] for r in range(9)]
groups += [[9*r+c for r in range(9)] for c in range(9)]
groups += [[9*(br+r)+bc+c for r in range(3) for c in range(3)]
for br in (0,3,6) for bc in (0,3,6)]
peers = [set(j for g in groups if i in g for j in g) - {i}
for i in range(81)]
MRV（最小剩余值）是变量排序启发式，不是剪枝——它决定先填哪格，不会删除任何合法候选，CSP 教材对此有明确区分。混用这两个概念是 AI 生成代码里常见的话术性错误。
求解前先验盘面：线索重复直接抛异常拒绝；还有一种更隐蔽的情况——线索合法但第一空格无候选，此时应返回"无解"而不是死循环。两个分支都要有测试覆盖：一个故意改坏的盘（重复线索）、一个合法但无解的盘。
唯一性是个单独的命题
"找到第一个解"和"解唯一"是两回事。验证唯一性必须继续枚举到找到第二个解或搜索穷尽——把首解当成唯一解写进文档，是逻辑上站不住的结论。这也是评估 AI 生成算法代码时的通用检查点：代码证明了什么、没证明什么，要说清楚。
速度证据的正确姿势
没有记录节点数和耗时，就不要报告"剪枝提速了百分之多少"。比较剪枝效果的前提条件苛刻且明确：固定候选值顺序和终止规则，只改变量选择策略；统一"求首解"还是"数全部解"的口径；记录访问节点定义、测试实例、解数量和运行环境。当前教学实现为清晰起见每次递归重算候选集，有额外开销——这是清晰的代价，写出来比藏着好。
给评审者的三问
评估 AI 写的算法代码，固定三问：一是约束对不对——拿检查器独立验证，不信"跑通了"；二是概念用对没有——MRV 当剪枝、首解当唯一解这类概念偷换要抓出来；三是证据链全不全——正确性证据和性能证据分开算账，没测的部分明确说没测。这套流程比任何"看起来挺对"的目测都可靠。
评论0