《算法的乐趣》第六十节

本节介绍数独求解算法的数学模型与实现。模型将每个单元格定义为统一结构，用fixed标志区分是否已确定数字，未确定时保存候选数集合；整体用81格二维矩阵加已确定计数器表示……

本节介绍数独求解算法的数学模型与实现。模型将每个单元格定义为统一结构，用fixed标志区分是否已确定数字，未确定时保存候选数集合；整体用81格二维矩阵加已确定计数器表示，计数达81即得解。

算法从首个未确定单元格开始，逐个试用候选数：每试一个数，就将其设为确定，并从同行、同列、同小九宫的相关20格中排除该数；若出现空候选列表则判为非法并回溯，否则检查相关格是否出现唯一候选数，若有则一并确定并继续排除，此过程递归进行。为保证回溯，每次试数前复制新状态。对比测试显示，26个提示数的题目平均递归深度不到9级，最难题也仅16级，远低于纯穷举的55级。

随后讨论若干话题：证明数独唯一解至少需17个提示数；合法终盘共6670903752021072936960种，考虑对称后为3546146300288种，可衍生出天文数字般的题目；因卡拉设计的“世界最难”数独难度评价10.7、本算法回溯16级，所谓农民三天破解的新闻实为改动了D2格数字，使题目由唯一解变为295个解。