按固定顺序填充数独为何比随机顺序填充效率高得多？

这个问题其实戳中了回溯法解决约束满足问题（CSP）的核心痛点：变量选择顺序对算法效率的影响能差出好几个数量级！你的观察完全正确，固定顺序（按宫→行→列的自然顺序）填充时回溯次数极少，而随机顺序会导致迭代爆炸，背后有三个关键原因：

1. 局部约束的提前「闭合」，避免后期大规模回溯 #

看你的shuffleBoxesCreateCheckingLists代码，固定顺序下是按「3x3宫→宫内行→宫内列」的顺序生成boxes数组的：先填满左上角的宫，再填右上角，以此类推，每个宫内按行优先填充。这种顺序的核心优势是：

• 你会先完整填满一个局部区域（比如一个宫），这个区域的约束（1-9不重复）会被彻底满足，后续填充其他区域时，不会再和这个已完成的区域产生冲突（除非代码逻辑错误，但你的校验逻辑是正确的）。
• 当填充到一个宫的最后几个格子时，可选值已经被宫的约束压缩到1-2个，几乎不需要尝试就能填上，直接跳过无效迭代。

而随机顺序填充时，你会零散地填充不同宫、行、列的格子，局部约束永远无法提前闭合。比如你先填了第1行第1列，又填了第9行第9列，再填第5行第5列——这些格子的约束关联分散，很多冲突要等到填充到它们所在宫/行/列的其他格子时才会暴露。这时候你需要回溯到很早的步骤，重置中间所有已填充的格子，自然导致迭代次数爆炸。

2. 回溯的「深度代价」天差地别 #

固定顺序填充时，回溯几乎只会发生在当前正在填充的局部区域：比如你填一个宫的第8个格子时发现冲突，最多回溯到这个宫的第1个格子，不会影响之前已经完成的宫。因为之前的宫已经完全满足约束，和当前填充的格子没有冲突。这种浅深度的回溯代价极低，迭代次数自然少。

而随机顺序填充时，回溯可能跳转到非常早的步骤：比如你填充到第80个格子时发现冲突，可能需要回溯到第10个格子甚至更早——因为第10个格子的选择埋下了后续一系列冲突的隐患。每次回溯都要重置中间70多个格子，这就导致主循环反复执行「尝试→冲突→回溯→重置」的无效流程，最终迭代次数突破6000万次。

3. 可选值的「动态剪枝」效率差异 #

你的代码里每个filledBox的values数组是随机打乱的，但固定顺序填充时，局部约束会自动对可选值进行动态剪枝：

• 填充一个宫的第9个格子时，宫已经有8个不同的值，可选值只有1个，直接就能填上，不需要尝试其他值。
• 填充一行的第9个格子时，行的约束也会把可选值压缩到1个，进一步减少尝试次数。

而随机顺序填充时，很多格子在填充时可选值还有3-5个，但这些选择可能在后期导致冲突，你需要反复尝试不同的组合，自然会产生大量无效迭代。

本质：约束满足问题的启发式选择 #

这种差异本质上是CSP中变量选择启发式的作用。固定顺序填充（按局部区域填充）属于「最少剩余值（MRV）」启发式的变体——它优先处理约束密集的局部区域，提前排除大量不可能的路径；而随机顺序完全没有利用任何启发式，让算法在搜索空间里盲目探索，最终陷入指数级的无效回溯。

内容的提问来源于stack exchange，提问作者piterm21