约束传播

将数字确定后产生的约束传递到相关格子,自动缩小候选范围的算法方法。

约束传播 (Constraint Propagation) 是当某个数字被确定后,立即更新受影响的行、列、宫中候选数的方法。本质上与人类更新笔记相同,但计算机可以瞬间无遗漏地传播所有影响。

在求解器中的作用

约束传播能显著提高回溯法的效率。每次试填数字后传播约束,如果出现候选数为 0 的格子则立即回溯 (早期剪枝)。候选数变为 1 的格子自动确定。

与人类解法的对应

人类发现唯一候选数并更新笔记的过程,可以说是约束传播的手动版本。数字应用的自动候选排除功能,就是在实时执行约束传播。