一个带凹槽的玉米芯底座，若干由三到十颗玉米粒粘连成的拼块，要求把所有拼块刚好塞进底座，不重叠、不留空。这类问题的难度在组合爆炸。按经验写法是递归回溯，再靠旋转对称去重和单格孤立时提前剪枝两类优化兜着。有人换了个思路，用 CP-SAT 把它建成精确覆盖问题，一次建模交给求解器。
转变发生在问法上。回溯在搜下一块放哪，精确覆盖在问这个格子归谁。后者能用一组等式说清，交给工具比手写搜索稳。
建模只要两组等式
把每个"拼块加放置方式"设成一个 0 到 1 的变量，放置方式由枚举所有旋转和平移后的占位集合得到。然后加两条约束。
每个拼块的放置方式变量之和等于 1，一处且只一处。
for plist in by_piece:
m.Add(sum(v for v, _ in plist) == 1)按格子分组，覆盖该格的所有变量之和也等于 1，每格被覆盖一次且只一次。
for clist in by_cell:
m.Add(sum(clist) == 1)模型只有这两组等式，没有目标函数。对精确覆盖来说，可行解就是答案。求解之后按值为 1 的变量还原拼法。
为什么精确覆盖比回溯省心
回溯里那两个优化没有浪费。旋转对称去重搬到了枚举放置方式这一步，模型变量数直接少一截。孤立格提前剪枝不需要了，等式本身就保证每格恰好被覆盖一次，不可行的情况产生不出解。写搜索时花在剪枝上的功夫，换成模型之后变成了枚举时的去重。
搜索顺序、回溯深度、剪枝次序，全都不用自己管。求解器在这些事上比手写循环稳，代价是模型必须写对，等式错了它只会老实返回无解。
复现一遍的步骤
pip install ortools。- 枚举每个拼块在底座内的所有合法放置，旋转和平移后的占位集合都要。
- 为每个拼块加放置方式的组合建布尔变量。
- 加拼块约束，每种拼块的放置方式恰好选一个。
- 加格子约束，覆盖同一格的变量恰好选一个。
- 先校验拼块总格数是否等于底座格数，不等说明谜题构造有问题。
- 调
solver.solve(model)，按 OPTIMAL 或 FEASIBLE 取解。
同批材料还带了数独例子验证方法。9×9 的整数变量各取 1 到 9，已知格用上下界相同的方式固定，行、列、宫各加一条全不同约束，参考题很快就解出来。
CP-SAT 的适用边界
它只接受整数变量和整数系数，约束里出现小数或分数，要先按比例放大取整。它擅长可行性搜索和约束紧的组合问题，排程、打包、精确覆盖、数独这类都能枚举全解，把 enumerate_all_solutions 打开即可。
返回状态要分清。OPTIMAL 表示找到最优且已证明，FEASIBLE 只表示找到可行解，超时或内存不足返回 UNKNOWN。靠部分解收尾的场合，要先想清楚 UNKNOWN 时怎么处理。
选错工具的场景也有。纯线性目标和线性约束的问题交给线性规划类求解器，路径类问题有专门的路由库。官方建议把 CP-SAT 用在约束规划和可行性问题上。
常见问题
和回溯比哪个快。这一版只提到脚本跑出了解，没有给耗时，也没有做对照。这类问题换求解器的收益取决于实例规模，自己量一遍再下结论。
什么时候不该用它。需要连续变量、要最大化一个复杂目标、或者模型规模大到求解器迟迟不收敛的时候。把问题写成等式的能力，比换工具更稀缺。
这类建模还能用在哪。物料切板、值班排班、资源分配的可行解搜索，本质都是每样东西恰好用一次的变形。
解会很多吗。精确覆盖问题常有多个可行解，enumerate_all_solutions 打开后会全部吐出。拼图类问题通常只要第一个可行解，或者自己加约束去重。