《算法的乐趣》第五十九节

本节介绍数独游戏的规则与计算机求解方法。数独是在9×9的格子中填入1～9，使每行、每列及每个3×3小九宫格内数字不重复，已给出的数字称为提示数。

本节介绍数独游戏的规则与计算机求解方法。数独是在9×9的格子中填入1～9，使每行、每列及每个3×3小九宫格内数字不重复，已给出的数字称为提示数。求解技巧分为直观法和候选数法：直观法直接依规则推断，适合简单题目；候选数法为每个空格建立候选数列表并逐步排除，适合复杂题目。

计算机求解通常采用穷举遍历解空间并剪枝，但回溯深度大、判断频繁，效率较低。本章提出的算法基于候选数法：先为每个空格建立候选数列表并按提示数排除，再对未确定的空格试数，试数时动态维护其相关20格（同行、同列、同宫格的20个格）的候选数列表，一旦出现唯一候选数就确定该格并继续排除。这样可减少试数与回溯次数，且全程无需合法性检查，填满81格即得正确解。