回溯法
通过试错探索解答的算法。遇到死路时回退到之前的状态尝试其他选择。
回溯法 (Backtracking) 是基于深度优先搜索的问题求解算法。在数独求解器中，向空格试填数字，如果产生约束冲突则回退到之前的状态尝试其他数字。由于系统地探索所有组合，只要解存在就一定能找到。
在数独求解器中的作用
选择候选数最少的格子
若从只有两个候选数的格子开始，即便第一次猜错，也只剩一条分支需要尝试。这一选择很大程度上决定了搜索量。
试填其中一个候选数
填入的是「暂定的一手」而非确定的数字，并记录下来以便日后撤销。
用约束传播填上能够确定的格子
因这次试填而只剩一个候选数的格子会被连锁填入，若存在矛盾便会在早期显现。
是否产生了矛盾
是
把盘面回退到该次试填之前，在同一格改试别的候选数。这就是回溯法。
否
若仍有空格，则回到第一步选择下一个格子。
所有格子填满时，解便完成
步骤 1 至 4 构成循环。回退时只撤销最近一次试填，因此在此之前确定的部分不会白费。每次试填之间越多地插入约束传播，矛盾就暴露得越早，需要尝试的分支也越少。
当仅靠约束传播无法解决谜题时，回溯法作为最终手段发挥作用。从候选数最少的格子开始试填，产生矛盾时回退。与约束传播结合使用可以大幅缩小搜索空间。
与人类解法的区别
人类倾向于避免回溯 (猜测)，只使用能逻辑确定的步骤来求解。这是由工作记忆的限制决定的。同时记忆和管理多个假设状态对人类来说非常困难。数独的难度设计以「人类能否不猜测就解出」为标准。