强制

强制

大师

相关技巧

这是猜测吗?强制链的争议

当强制链被用作证明技巧时,它们并不是猜测。你暂时检查从选定起点出发的每一个分支,对每个分支进行逻辑传播,只保留所有分支都支持的结论,或由矛盾所强制的结论。与猜测的关键区别在于承诺。猜测会选择一个分支并当作它是真的继续下去。强制链则比较从起点出发的所有相关分支,只有当比较证明了某些东西时才采取行动。强制链不如基于模式的技巧优雅,但当每个分支都被准确检查时,它们的结论是可证明正确的。

单元格强制链

从一个双值单元格{A,B}开始。为每个分支传播蕴含关系。比较结果。矛盾:一个分支无效,因此单元格必须是另一个候选数。收敛于填数:两个分支都强制同一个数字进入同一个远处的单元格。收敛于删减:两个分支都从同一个单元格中删减同一个候选数。

区域强制链(数字强制链)

从一个数字在一个宫中的2-3个位置开始。将每个位置作为一个分支进行探索。同样是三种推理类型。当双值格具有影响深远的蕴含关系时,单元格强制很有效。当一个数字的位置具有强大的级联效应时,区域强制很有效。

强制网:扩展分支数量

单元格强制网:具有3-6个候选数的格。区域强制网:一个数字在一个宫中有4-6个位置。分支更多,代价更高,但能找到强制链无法找到的删减。逻辑完全相同。只是分支数量不同。

传播引擎

每个分支通过唯一候选数、隐性唯一候选数、锁定候选和显性数对进行传播,迭代直到稳定。一个假设可以在整个棋盘上引发数十个中间步骤的连锁反应。当两个分支通过完全不同的路径得出相同结论时,这种收敛就以确定性证明了该结论。

三种推理类型

矛盾:某个分支产生了无效状态。该假设为假。最常见。位置收敛:所有分支都将同一个数字强制填入同一个单元格。较少见但具有决定性。排除收敛:所有分支都从同一个单元格中排除同一个候选数。最微妙的一种。

何时使用强制技巧

最后的逻辑手段。在基于模式的技巧和更简洁的链都失败后使用。先尝试有2-3个分支的强制链。有3-6个分支的强制网代价更高,通常留到后面使用。两者都是第12级(极限)。对于计算机求解器而言,有界强制是一种强大的证明引擎,但并不自动完备。只有当搜索被允许扩展到足以覆盖所需假设时,完备性才会出现,而这已接近穷举回溯。在实践中,强制最好被描述为一种受控的逻辑搜索,而不是保证任何固定深度的求解器都能解出每一个有效谜题。

关于优雅与完备性的哲学思考

基于模式的技巧揭示结构关系,更为优雅。但存在一些有效谜题需要强制级别的逻辑。强制技巧是安全网,能接住所有基于模式的技巧无法处理的谜题。最令人满意的做法:先尝试所有基于模式的技巧,只有当谜题确实需要时才诉诸强制。

总结

强制链和强制网是最强大的逻辑技巧之一,属于第12级(极限)。它们从选定的起点探索每一个分支,传播后果并比较结果。推理通过矛盾、位置收敛或排除收敛得出。它们是在暴力回溯之前的最后手段;如果不受实际限制地扩展,它们会成为完备的搜索证明,但有界的人类风格强制仍是一种有针对性的高级技巧。

相关技巧